Problem Link
Author: aryansanghi
Solution
For two 1 \times 1 squares, let’s say they are a part of a “path” if you can reach from one square to other square without crossing an edge. For a path, if an edge has been added to one of its square, then a player can take all it’s squares in one turn if he wishes. A path is completed if you can’t add any edge to it
Now, the paths can either be a closed loop or a linear path. Let’s prove some observations:
Observation 0:
In any turn of the game, exactly one path will be open and all other paths with edge added already would have been completed.
Proof:
When a new path is being opened by adding an edge to it, then the player is ending his turn. Now the player can do what he wants to do in that path and also can take all other paths with edge added already as it won’t effect his ending of the turn. So, it’s optimal for the player opening a new path to complete all other paths which are opened already.
Observation 1:
For each path, player will either take all its squares or take all squares but 2 in non-cyclic or all squares but 4 in cyclic paths.
Proof:
The player ends his turn by not completing a square. So, if the player wants to open a new path, by observation 0 it is always optimal for him to close the current path and if he doesn’t want to open a new path, then it is always optimal for him to leave the minimum possible number of squares and take all others and force his opponent to open a new path. This minimum number of squares left is 2 for non-cyclic and 4 for cyclic paths.
Observation 2:
For all non-cyclic paths of length \geq 4 and cyclic paths of length \geq8, if it is opened by one player by adding an edge to it, then for the other player it is optimal to take all it’s squares but two and end his turn.
Proof:
Player uses the strategy in observation 2 for the paths and take all but 2 squares in a path of length \geq4 and all but 4 squares in cyclic paths \geq8 which forces his opponent to take the 2 squares which he left in non-cyclic and 4 squares left in cyclic paths and open a new path which now the opponent can apply the strategy again in. This ensures that Player using this always has a score lead and you can proof there isn’t a better strategy that ensures this for non-cyclic paths \geq4 and cyclic paths \geq8.
Observation 3:
For paths of lengths 1 and 2, it is basically an “opening switch”, which means that if initially P1 was opening new paths then after a path of length 1 or 2 is completed, P2 is forced to open a new path.
Proof:
For paths of length 1, proof is trivial. For paths of length 2, the player opening it will always place the edge in the middle which forces the player after to take both the squares and do opening switch. If the player opening it places edge in corner of path in hopes of other player not taking it, then the other player will take it and do “opening switch”. So in paths of length 2, there will always be an opening switch
Observation 4:
For paths of length 3 and cyclic paths of lengths 4 and 6, the players with the turn will keep taking the paths and do “opening switch” till a certain point and after that, strategy given in Observation 2 will start taking place.
Proof:
For paths of given lengths, by applying strategy given in observation 2, the player is basically forcing a score difference of -1 in length 3, -2 in cyclic length 6 and -4 in cyclic length 4 in hopes that paths of length given in observation 2 will offset the negative score and give him the win. If in case it doesn’t happen, then player with turn is forced to take all squares in path and do “opening switch” even if it loses him the game as it would have lost him the game even if he didn’t do it.
Final Solution
First use dfs to find the paths and if they are cyclic or not and store that. Now sort the list with it containing first paths of length 1 followed by paths of length 2 followed by cyclic paths of length 4 followed by cyclic paths of length 6 followed by paths of length 3 or more in ascending order. Now assign dp[0] as equal to length of path with greatest length and remove that path length from the list.
Now use dp[i]=max(dp[i-1]+a[n-i] - 4 \text{ or }8(\text{cylic and non cyclic})),-dp[i-1]+a[n-i])) till paths of length >2 and if second one is used in max, reverse parity of a variable z(z = (z+1)mod 2).
The first one is for leaving 4/6 squares and taking rest, i.e. observation 2 and second one is for taking all and doing “opening switch”. For when you encounter paths of length \leq2, just do the second one, i.e. dp[i]=-dp[i-1]+a[n-i] and reverse parity of z. Now, in the end if dp[n] is 0, it’s draw, else the dp[n] is positive and if z is 0, player 1 wins else player 2 wins. Player 1 is Alice if number of edges(i.e. e) is even, else it’s Bob.