jd_sal's blog

CF #643 Div2 D — Game with Array
By jd_sal, history, 5 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it 
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.
→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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$$$.

→ Reply