Power Sum POWSUM Solution Codechef

Power Sum POWSUM Solution

You are given a sequence A of N integers such that every element is a non-negative power of 2. A sequence is called good if its sum is a non-negative power of 2. You would like to turn A into a good sequence.

To achieve this, you can perform the following operation on A:

  • Pick a non-empty subsequence of A, pick a positive integer X such that X≤230, and multiply every element of this subsequence by X.

Find the minimum number of operations required to turn A into a good sequence. Also, find one sequence of operations which does this. If there are multiple possible answers, you may find any of them.

Input Format

  • The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
  • The first line of each test case contains a single integer N.
  • The second line of each test case contains N space-separated integers A1,A2,…,AN.

Output Format

For each test case, print the answer in the following format:

  • First, print one line containing an integer M, denoting the minimum number of moves required.
  • Then, print 2M lines describing M operations.
    • Each operation is described by 2 lines.
    • On the first line, print two space-separated integers K and X, denoting the size of the subsequence and the multiplier for this operation.
    • On the second line, print K distinct space-separated integers denoting the indices of the elements chosen to be multiplied in this operation. These K integers can be printed in any order.

Constraints

  • 1≤T≤1000
  • 1≤N≤100
  • 1≤Ai≤220

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1

2
4
4 8 4 32
3
2 2 4

Sample Output 1

1
3 2
1 2 3
0

Explanation

  • Test case 1: Multiplying the 1st, 2nd and 3rd elements by 2 turns the array into [8,16,8,32], whose sum is 64=26.
  • Test case 2: The array is already good.

SOLUTION

Program: Power Sum POWSUM Solution in C++

#include <bits/stdc++.h>
using namespace std;
int main() {
	int t;
	cin>>t;
	while(t--){
	    int i,n,s=0,j=1,b;
	    cin>>n;
	    int a1[n],a2[n];
	    for(int i=0;i<n;i++){
	        cin>>a1[i];
	        a2[i]=a1[i];
	        s=s+a1[i];
	    }
	    sort(a1,a1+n);
	    b=ceil(log2(s));
	    auto c=find(a2,a2+n,a1[0]);
	    j=((pow(2,b)-s)+a1[0])/a1[0];
	    if((s & s-1)==0){
	        cout<<0<<endl;
	    }
	    else{
	        cout<<1<<endl;
	        cout<<1<<" "<<j;
	        cout<<endl;
	        cout<<(distance(a2,c))+1<<endl;
	    }
	}
	return 0;
}

Program: Power Sum POWSUM Solution in Java

import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
	Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        for(int t=0;t<T;t++){
            int n=sc.nextInt();
            int a[]=new int[n];
            long sum=0;
            for(int i=0;i<n;i++){
                a[i]=sc.nextInt();
                sum+=a[i];
            }
            int k= (int) (Math.log10(sum)/Math.log10(2));
            if((int)Math.pow(2,k)==sum){
                System.out.println(0);
            }
            else{
                long res= (long)(Math.pow(2,++k)) - sum;
              
                    for(int i=0;i<n;i++) {
                        if (res % a[i]==0){
                            System.out.println(1);
                            System.out.println(1 +" "+ ((res/a[i])+1));
                            System.out.println(i+1);
                            break;
                        }
                    }
                
            }
        }
	}
}

Program: Power Sum POWSUM Solution in Python

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int, input().split(' ')))
    upper_value = 1
    while upper_value < sum(arr):
        upper_value *= 2
    s = upper_value - sum(arr) + min(arr)
    multiplier = s/min(arr)
    if multiplier == 1:
        print(0)
    else:
        print(1)
        print(1, int(multiplier))
        print(arr.index(min(arr)) + 1)

January Long Challenge 2022 Solution

Leave a Comment

fifteen + eighteen =