CLPERM - Editorial

IN The basic O(N) solution for the problem that given a sorted array of no.s,find the smallest no. which cannot be formed by any subset of no.s from the array.

If we asssume that the smallest unachievable sum is res till arr[i-1] then it is the answer if arr[i]>res
That part is quite clear…
But the fact that :
the new res = res + arr[i] if arr[i] <= res is not clearly proven… How can we say that the new res cannot also be formed by some elements from index 0…i-1 from the array…
If we can say that it cannot be achieved by any subset from 0…i-1 then it is definitely the new res…

Can anybody explain that part with some proof.

This

@darkshadows:
Links to solution don’t work.
Also, editorialist’s English is shitty.
:frowning:

#include
#include
using namespace std;

int main()
{
std::cout.sync_with_stdio(false);
unsigned long long int t;
cin>>t;

while(t--)
{
   unsigned long long int n,k;
   cin>>n>>k;
   unsigned long long int res=1;

        unsigned long long int a[k],b[n-k];
       for(unsigned long long int i=0;i<k;i++) cin>>a[i];
       sort(a,a+k);

       unsigned long long int i=1,j=0,x=0;

       while(i<=n)
       {
           if(a[j]==i)
              {
                i++;
                j++;
              }

           else
           {
               b[x]=i;
               i++;
               x++;
           }
       }
       sort(b,b+n-k);
       for(i=0;i<n-k&&b[i]<=res;i++)
        res+=b[i];
    //cout<<res<<endl;
    if(res%2==0)
        cout<<"Mom"<<endl;
    else
        cout<<"Chef"<<endl;

}
return 0;

}

I am getting run-time error(SIGSEGV) in task 3 only can you tell me why?

why i am getting WA for sub tasks 1 and 3 here is my code link https://www.codechef.com/viewsolution/18591109