POWSUM - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Prasant Kumar
Tester: Taranpreet Singh
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Easy

PREREQUISITES:

Binary Representation

PROBLEM:

You are given a sequence of A on N integers such that every element is a non-negative power of 2. A sequence is called \text{good} if its sum is a non-negative power of 2. Find the minimum number of operations required to turn A into a \text{good} sequence.

An operation is defined as: Pick a non-empty subsequence of A, pick a positive integer X (X \leq 2^{30}), and multiply every element of this subsequence by X.

Find any sequence of minimum operations that turns A into \text{good} sequence.

QUICK EXPLANATION:

  • Required number of operations is either 0 or 1.
  • If the sequence is already \text{good}, the answer is 0.
  • If the sequence is not \text{good}, we require only 1 operation.
  • Let S be the sum of the sequence (where S is not a power of 2) and r be the smallest integer such that S < 2^r. In one operation, we choose the smallest number of the sequence (M), and multiply it with X = \frac{2^r - (S - M)}{M}.

EXPLANATION:

If the sequence is already \text{good}, we need 0 operations.

If the sequence is not \text{good}, we can make it good using exactly one operation. How?
Let S be the sum of the sequence. We know that S is not a power of 2. After some number of operations, let us assume that we achieve a sum of 2^r, thus, making the sequence \text{good}.
S>2^r: This is because, in each operation we multiply some subsequence with a positive integer. This would increase the value of the elements of that subsequence and thus the overall sum.
This means that we have to increase S at least to 2^r such that 2^{r-1} < S <2^r. For this, we need to add 2^r - S to the sequence.
Let M denote the smallest element of the sequence.

Claim: 2^r - S is a multiple of M.
Proof: An important thing to note is that all numbers of the sequence are powers of 2.

Let p be the number of trailing zeroes in the binary representation of M (M = 2^p) and q be that of S. Also, the number of trailing zeroes in the binary representation of 2^r is r. Since M is the smallest element of the sequence, p \leq q. Similarly, since 2^r>S, r>q.
This means that the number of trailing zeroes in the binary representation of 2^r-S is also q.

A binary number with q trailing zeroes is divisible by 2^q. This implies that 2^r-S is divisible by 2^q. Also, since p\leq q, 2^r-S is divisible by 2^p, which is nothing but M. Hence proved, 2^r-S is divisible by M.

To convert S to 2^r, we can simply multiply M by \frac{2^r - (S - M)}{M}. This would take only one operation and make the sum of sequence equal to 2^r. The chosen subsequence in the operation only consists of M.

TIME COMPLEXITY:

We have to traverse the array to find the minimum element and the sum of elements. Thus, the time complexity is O(N) per test case.

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int sf=2e5+10; // size for fac and inverse fac.
int M=1e9+7; // modulus, change it if different.
// dont copy others template you will get plagiarized.
int fac[sf],invFac[sf];
int power(int a,int b){
	int ans=1;
	while(b>0){
		if(b&1){
			ans*=a;
			ans%=M;
		}
		a*=a;
		a%=M;
		b/=2;
	}
	return ans;
}
int findInv(int a){
	return power(a,M-2);
}
void preFac(){ // pre process
	fac[0]=invFac[0]=1;
	for(int i=1;i<sf;i++){
		fac[i]=(fac[i-1]*i)%M;
		invFac[i]=findInv(fac[i]);
	}
}
int nCr(int n,int r){  // call only if preprocess is done
	return ((fac[n]*invFac[r])%M * invFac[n-r])%M;
}
int msb(int n){ // change 63 to 31 if 32 bit integer is used and use __builtin_clz(n)
	return 63 - __builtin_clzll(n);
}

// => pre-process
// => change size of array, modulus if required.
// -------------------------------------------------------------------------------------------------------------------------------------------



signed main(){
	ios_base::sync_with_stdio(0) , cin.tie(0);
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		int mini=1e9,ind;
		int sum=0;
		int arr[n];
		for(int i=0;i<n;i++){
			cin>>arr[i];
			if(arr[i]<mini){
				mini=arr[i];
				ind=i;
			}
			sum+=arr[i];
		}
		if((sum&(sum-1))==0){
			cout<<0<<endl;
		}else{
			int next=1ll<<(msb(sum)+1);
			int dif=next-sum;
			cout<<1<<endl;
			cout<<1<<" "<<(dif/mini + 1)<<endl;
			cout<<ind+1<<endl;
		}
	}
	return 0;
}

Tester's Solution
import java.util.*;
import java.io.*;
class POWSUM{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        int[] A = new int[N];
        for(int i = 0; i< N; i++)A[i] = ni();
        int sum = 0;
        for(int x:A)sum += x;
        if((bit(sum)) == 1)pn(0);
        else{
            pn(1);
            int total = (Integer.highestOneBit(sum)<<1)-sum;
            for(int i = 0; i< N; i++){
                if(total%A[i] == 0){
                    pn("1 "+(total/A[i]+1));
                    pn(1+i);
                    return;
                }
            }
            hold(false);
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new POWSUM().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n;

void solve()
{
    cin>>n;
    int a[n];

    int sum = 0;
    int minm = INT_MAX;
    int min_index = 0;
    for(int i = 0; i<n; i++){
        cin>>a[i];
        if(minm > a[i]){
            minm = a[i];
            min_index = i+1;
        }
        sum += a[i];
    }

    if((sum & (sum-1)) == 0){
        cout<<0;
        return;
    }

    int no_of_bits = (int)log2(sum) + 1;
    int target = 1<<no_of_bits;
    int needed = target - (sum - minm);
    int x = needed/minm;
    cout<<1<<endl;
    cout<<1<<' '<<x<<endl;
    cout<<min_index;
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}
11 Likes

great explanation

1 Like

A more interesting, and difficult, problem is to identify a subsequence to achieve the desired result with a minimum multiplying factor. Short of brute force, I do not know to solve this alternative problem.

1 Like

how to think that it could be only in one step ?

1 Like
#include<bits/stdc++.h>
using namespace std;
//fors
#define loop(i,b) for(int i=0;i<b;i++)
#define ones(n)   __builtin_popcount(n)

main()
{
	int t;
	cin>>t;
	while(t--)
	{
	   int n;
	   cin>>n;
	   int ar[n];
	   int mn = 1e9,sum=0,ind=-1;
	   loop(i,n){
	      cin>>ar[i];
	      if(mn>ar[i]){
	         ind = i;
	         mn = ar[i];
	      }
	      sum+=ar[i];
	   }
	   if(ones(sum)==1){
	      cout<<0;
	   }
	   else{
	      sum -= mn;
	      int pw = log2(sum) + 1;
	      int x = (pow(2,pw) -sum)/mn;  
	      cout<<1<<"\n"<<1<<" "<<x<<"\n"<<ind;
	   }
	   cout<<"\n";
	}
	cerr<<"time taken: "<<(float)clock()/CLOCKS_PER_SEC<<endl;
}

Can anybody tell me whats wrong with this ?
What I am doing here is saying if the sum is not a power of 2 then I am just taking the minimum element from the array and multiplying it by the required amount to make it a power of 2

hii, you are calculating the value of x worng , you are forgetting the min element that is already present in the sequence. You can figure it out… I Think.

and use long long

First thanks for replying @code123rocks,
And well i subtracted the min element(sum -= mn) and long long would’nt be necessary because the sum would never reach it a[i] <= 2^20 and n= 100 that means 10485760 is max the sum could go which is much less than the limit of int

Well I got it while printing the index i was assuming 0 based indexing but we have to use 1 based indexing.

Can you please explain this with a test case. Not able to get the point.

1st Sample test case output must be :

1
1 5
1 

instead of

1
3 2
1 2 3

because we need minimum no. of operations…