jd_sal's blog

By jd_sal, history, 4 years ago,

Hello all,

This is a problem from the recent contest Codeforces Round #643 Div 2 named Game with Array (Problem D).

First claim of the editorial is that the answer is "NO" if S<2*N. I find it difficult to reach this conclusion during the contest.

As I can see that a lot of people were able to solve this problem during the contest, so I would like to hear your exact thought process/intuition/reasoning which you used during the contest. It would be great if you explain in detail.

Thank you.

• 0

 » 4 years ago, # |   +1 Just Imagine an array consisting of all 1's except for the last element. Now our last element must be (total_given_sum-1's_so_far) and our (k is size_of_array). Eg 4 7; - 1 1 1 4 will be the array as per our algo. - k=3 but total_1's will be equal to k so answer is "NO". - So, we can conclude that if total_1's is + 1 >= last_element. We wil never get answer. 
 » 4 years ago, # |   +1 Hi, during the contest I looked at solutions for smaller $N$, like $N \leq 2$. When $N$ is small, it's easy to construct a solution by hand. Then I noticed as I made $N$ incrementally larger, the terms must get smaller and smaller towards $1$. And eventually no solution will exist when $N$ is too large, in particular when $S<2N$.