CLPERM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sunny Aggarwal
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM

PRE-REQUISITES:

Maths

PROBLEM:

K numbers denoted by array B from set S = [1,2,…N] are removed. Find the minimum number X such that X cannot be formed by picking a set of numbers from S.
1 ≤ N ≤ 109
1 ≤ K ≤ 5*105

EXPLANATION:

If the minimum X is odd, second player wins, else first player wins.
So, we just need to find X.

If k == 0, then all numbers from 1 to (N * (N + 1)) / 2 are possible to form.
Consider a special case, X = 1 if 1 has been removed from set [1…N].

Based on this observation, we can first sort the array B in ascending order.
Fact: Let’s say all numbers from 1 to i are available, then we can form every number till (i * (i + 1)) / 2.

Let’s consider last reachable number till now is M. So now we want to form numbers M + 1, M + 2 and so on.
We have generated all numbers till M now and now we want to generate M + 1 and the new number that available number we get is say Bi + 1, we can’t generate M + 1, if Bi + 1 > M + 1. In such a case X will be M + 1.
Or else, we know that all numbers between Bi + 1 and Bi+1 - 1(both inclusive) are available. So, we know that all numbers from M + 1 to M + S are also available, where S = sum of all numbers between Bi + 1 and B_{i+1} - 1(both inclusive).

We do this for all unavailable numbers in sorted traversal to get the maximum unachievable sum M.

Complexity: O(K log K)

You might want to read this, for better clarity.

SOLUTIONS:

Setter’s solution
Tester’s solution

2 Likes

http://www.codechef.com/viewsolution/5717014
This problem can be solved with (sqrt(n) ) complexity too.

`int res = 1;
for (int i = 0; i < n && arr* <= res; i++)
    res = res + arr*;`

This is the method for finding the smallest number which cannot be represented as sum of elements in an array which is sorted . Now in this problem you can use it . Its O(n) so without modifications it cannot pass subtask 3 . But one thing to notice is when the value of res crosses N , then the this loop will not stop intil i<n . So you can add a break when res reaches N and make the value of res as n * (n+1)/2 - sum of those K numbers + 1. So the complexity of this method becomes O(sqrt N ) as when i reaches about sqrt (n) then value of res will be approximately N .

4 Likes

I understand your explanation but can you please make it a bit more clear what you mean to say.

and now we want to generate M + 1 and
the new number that available number
we get is say Bi + 1, we can’t
generate M + 1, if Bi + 1 > M + 1.

This part is particulary unclear.

1 Like

don’t you think complexity of program would be O(K log K) in sorting the missing number.

this link will help you

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*;
	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( "

" );

What’s wrong here ?

Hello everyone,

Here is the author’s commented solution for this problem.

Hope you find it useful …

1 Like

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?

CODE LINK

Thanks.

Regards,
Ankit.

Hello ankit,

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.

http://www.codechef.com/viewsolution/5901687

Here is the Ac version of your solution. I just got Ac with your code :slight_smile: :B

Hope you find my words useful to you

@ma5termind, yea I missed considering the case of having large numbers.
Thanks.

This post was flagged by the community and is temporarily hidden.

How can we be sure that if (Bi)+1 to B(i+1)-1 are available then M+1 to M+S are possible

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 http://www.codechef.com/viewsolution/5924420

@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

Can we have someone to proofread the editorials please?! Use of ambiguous English leads to incomprehensible logic no matter how easy it is!

1 Like

I think to find maximum unachievable sum, instead of keeping track of range between every missing number

we can do

SumOfAll(natural)Numbers upto (Present missing number - 1) - Sum of all previous missing numbers.

e.g 3 7 10 are missing numbers

to find sum at missing number 10
we can find 9 * (9+1)/2 - (3 + 7)

Is it correct

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*>res
That part is quite clear…
But the fact that :
the new res = res + arr* if arr* <= 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*;
       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*<=res;i++)
        res+=b*;
    //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