CHSERVE - Editorial



Problem Link :

Division 1

Division 2

Author : Abdul Ahad

Tester : Misha Chorniy

Editorialist : Anand Jaisingh

Pre-Requisites :


Problem :

Just some implementation behind a story

Explanation :

Putting up an explanation for this problem is harder than solving the problem. Now, let N = the number of turns that have already been played, we know N= P1+P2 .

Let’s keep the serves 0 indexed and not 1 indexed from now.So, we want to know who will serve the N^{th} turn. 1 indexed this is the (N+1)^{st} turn. Now, Just try and see a pattern, chef served for the first K occasions, i.e all serves in [0,K-1], the opponent for the next K turns i.e in [k,2 \cdot K -1], then chef again for the next K turns and so on. So, the player who is going to serve changes at each multiple of K.

We can notice that for each interval of the form [x \cdot K, (x+1) \cdot K -1] the value of floor(y) for each y in the interval is the same. For the first such interval, chef serves and the all integers in the first range give 0 on floored division by K, for the second such interval it’s 1, for the 3^{rd} such interval its 2, and so on.

So, if floor(P1+P2=N/K) is even, the serve falls in Chef’s interval, else it falls in the opponents interval. That’s it.

Time Complexity : O(T).

My Code : Link


Video solution in C++, Python and Java: