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.
`int res = 1;
for (int i = 0; i < n && arr[i] <= res; i++)
res = res + arr[i];`
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 .
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)
What that means is, if we are given numbers in the range [1 to i], then we can form all numbers in the range [1,i*(i+1)/2]. So, for every b[i], we calculate the sum of (1,b[i]-1). Let the maximum number we can create from these numbers is M. The next number we want is M+1, which we can create using b[i]. If b[i+1]> M+1, then it’s impossible to create it and thus ans would be M+1.
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 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
:B