SPOJ (Ambitious Manager)

This is an interesting math problem.

For the solution, you just have to observe and prove that, b_i > b_i-1 + b_i-2+ ... + b₁ for all i > 1. The question is, how one might observe this fact. That's when 'numerical experimentation' can help you. Just write down some (say, 10) random values of a_i on paper and calculate the corresponding values of b_i and you will see it.

This can be proved with induction.

For the base case, note that, b₂ > b₁ because, b₂ = a₂ + 2*a₁ = a₂ + 2*b₁. (a_i > 0 for all i)

In fact, from the definition of b_i it is clear that,
b_i = a_i + 2*b_i-1.

Now, lets assume that, b_n-1 > b_n-2+ ... + b₁ for some n > 2
b_n = a_i + 2*b_i-1
therefore, b_n > a_i + 2*(b_i-2+ ... + b₁) (by the induction hypothesis)

This poof leads to the following conclusion:
Let, b_i be the maximum number such that b_i ≤ N. We must take this value, otherwise it will be impossible to build N from the rest of the values.

So, you have to take the maximum b_i not exceeding N and replace N with N-b_i, as long as it is possible. If, you reach 0, you are done. Just print the positions of the taken numbers. Otherwise print a -1.

Note that, there will never be multiple solutions.
In fact, for any sequence S of integers such that, S_i > S_i-1 + S_i-2 + ... + S₁. Every subset of S yields a different sum.

To see this, consider two different subsets A and B. Without loss of generality, assume that, sum(A) ≥ sum(B), where, sum(X) is the sum of the elements of subset X. Let, k be the largest index such that, S_k is included in A but not in B. According to the proof described above, S_k will always be greater than the sum of all S_i, where k > i and S_i is included in B. So, sum(A) != sum(B) (i.e. A > B)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
#include<ctype.h>

#include<vector>
#include<set>
#include<map>
#include<string>
#include<stack>
#include<queue>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long LL;
typedef pair<int,int> pii;

#define FOR(A,B) for(int A = 0; A < (B); ++A)
#define REP(A,B,C) for(int A = (B); A <= (C); ++A)
#define CLR(X,Y) memset(X,(Y),sizeof(X))


int main()
{
   LL a[55], b[55];
   int T; scanf("%d",&T);
  
   while(T--)
   {
       LL n;
       int k; cin>>n>>k;
              
       FOR(i,k)
       {
           cin>>a[i];
          
           if(i==0) b[i] = a[i];
           else b[i] = (b[i-1]<<1)+a[i];
       }   
              
       vector<int> ans;
      
       for(int i = k-1; i >= 0; --i)
       {
           if(b[i]<=n)
           {
               ans.push_back(i+1);
               n -= b[i];  
           }  
       }
      
       if(n > 0)
       {
           puts("-1");  
       }
       else
       {           
           for(int i = ans.size()-1; i >= 0; --i)
           if(i<ans.size()-1) printf(" %d",ans[i]);
           else printf("%d",ans[i]);
          
           puts("");  
       }
   }
  
   return 0;
}

this blog is inspired by: http://one-problem-a-day.blogspot.com