I did this problem using the same idea. However I got WA in the last 2 subtasks.
int n , k;
cin >> n >> k;
vector<ll> temp(k);
rep( i , 0 , k )cin >>temp[i];
sort( all( temp ) );
ll x = ( n*( n + 1 ) ) / 2 ;
ll last = 0;
for ( ll a : temp )
{
last += a;
x = ((a)*( a + 1 )) / 2;
x -= last;
if ( a > x )break;
}
++x;
if ( x % 2 )printf( "Chef" );
else printf( "Mom" );
printf( "\n" );
I couldn’t solve the problem in the competition and read the tutorial so as to implement its solution. Although, I had some difficulty in understanding the solution, I was able to write its code. The solution fails and gives WA for task # 0,1,2 and 5. What could be the bug in my code?
I checked your solution just now and find that your logic is all correct except for the part that you are not taking care of overflow that will surely occur during the third subtask. Use of long long instead of int will solve this problem.
from the time i first solved this problem to this date, i am not able to understand why am i getting run time error, when i try to delete those dynamic arrays, i get wrong answers, really need ur help coders.here is my solution CodeChef: Practical coding for everyone
@ashrko619: here is AC submission of your code. You missed the case that, if your for loop is executed fully, updated x will be “sum(1 to N)-last”. Hope it helps
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…
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?
try reading the link given for better clarity at the last of the editorial. basically at any moment if you can form sum (s) using numbers preceding a number (x), but (x > s+1), then you can’t form (sum+1). As, by using the previous numbers, you can only form sum (s), and if you take (x), does not matter which number you add to it (or even if you don’t add any), it will always be greater than (s+1), and hence you will not be able to form (s+1)