PARTGAME Editorial

editorial
, , , ,
1

PARTGAME Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Prakhar Neema
Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra

DIFFICULTY:

Easy-Medium

PREREQUISITES:

None

PROBLEM:

Alice and Bob are playing a game. In this game, there are N piles of stones, say $A_1,A_2,…A_N$In his move, the player can select any of the piles, discard the rest of the (N-1) piles, and partition the selected pile into N piles containing at least 1 stone. The player who cannot make a move loses. Determine the winner of the game if Alice moves first

Quick Explanation

Winning state can be define here as:

x \; mod \;n(n-1) = {\{0\; or >=n \}}

All other states are losing state. So just iterate through the array and check if there is a winning state then Alice would win the game else Bob would win.

Explanation

The first step for a player would be to check if there exists a pile choosing which he can win the game, i.e a pile which can be split into n piles \{p1, p2, p3....pn\} such that p_i < n \; \forall \;i. Thus the question reduces to choosing a pile that satisfies the above condition. We will perform this check for each pile so now for a pile having x stones we want to check whether it satisfies our condition or not. This can have three cases:

  • Case 1: 1 \le x < n: Here we can clearly see that the player cannot split the given pile into piles since x is less than n.
  • Case 2: n \le x \le n(n-1): Here it is easy to see that the player can divide the pile into n piles each having less than n stones.
  • Case 3: n(n-1) + 1 \leq x < n(n-1) + n: Here no matter how he divides the piles there will always be a pile having at least n stones. so he will lose.
  • Case 4: n(n-1) + n \leq x \leq 2n(n-1) : We can see that player 1 can lead to all losing states by putting 1 stones in (n-1) piles and n(n-1) + 1 stones in the n_{th} pile.

Thus using similar pattern analysis we can reach our initial claim in quick explanations.

A little more Mathematical proof:

Claim: x \;mod\; n(n-1) = \begin{cases} {1 \le r \le n(n-1) ..... Losing \;State }\\ n \le r \le n(n-1) .....Winning\; State \end{cases}

Proof by Contradiction

Assuming k = qn(n-1) + r is the smallest winning state where 1 \le r\leq(n-1). Here k can be represented as a sum of n losing states. Now all smaller losing states are such that 1 \leq rem \leq (n-1). This implies:

\sum_{i=1}^{i=n}1 \leq \sum_{i=1}^{i=n} rem_i \leq \sum_{i=1}^{i=n} (n-1)
=> n \leq r \leq n(n-1).....Contradiction

Proving for the 2nd part. Assuming k is a losing state and n \leq r \leq n(n-1). This implies that k cannot be represented as sum of n losing states. Now observe that r can be constructed as follows:

Assume k' = qn(n-1) + rem' as 1st division. Divide remaining (r - rem') among remaining (n-1) part. This reduces to the problem that sum such that n \leq sum \leq n(n-1) can be constructed using n items, each of which holds 1 \leq item \leq (n-1) which again makes a contradiction.

TIME COMPLEXITY:

Here we simply need to perform a mod operation on each elements of the array. The mod operation would take O(1) time and iterating through the array would take O(N) time. Thus in total the time complexity would be O(N).

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

5 Likes
2

soo easy I can’t believe only 9 people in div3 solved this

3

lol, “easy-medium” really?

4

Why not? I am actually not sure if you find the label too difficult or too easy – that’s how accurate it feels to me. If you think it’s too hard, then simply working through n = 3 should’ve given enough of an insight into the structure of the problem. If you think it’s too easy, then I must tell you that I originally thought of a multiplicative pattern, which was completely wrong. So yeah, the solution may be simple, but it doesn’t make the problem itself simple.

5 Likes
5

Why can k be represented as sum of n losing states?

6

Because it is always possible to find the solution of the equation:
\sum_{i=1}^n r_i = s, \ 1 \leq r_i \leq (n-1) \ and \ n \leq s \leq n(n-1)
(We can assign the values of r_i greedily for any s in the range.)
Now assign, A_1 = qn(n-1) + r_1 and A_i = r_i, \ 2\leq i \leq n.
Hence, \sum_{i=1}^n A_i = qn(n-1) + \sum_{i=1}^n r_i = qn(n-1) + rem' = k'

1 Like