PROBLEM LINK:
Author: Hasan Jaddouh
Testers: Kamil Debowski
Editorialist: Hasan Jaddouh
Difficulty:
Medium
Prerequisites:
ad-hoc, game theory
Problem Statement:
Two players are playing a game, there is a sequence of N integers, at one turn the player choose two adjacent numbers and remove them and put in their place either their sum or their product, game ends when there’s only one number left, if it was odd then one of players win if it’s even the other win, you will also given which player will play first
Explanation:
since we only care about the parity of last number then we can change all even numbers in array to 0 and all odd numbers to 1, and when we sum two 1s the result will be 0.
for simplicity, we will denote the player who will win if last number was 0 by P0, and P1 for the other player.
First thing to notice that we have 4 possibilities for the status of array before the last move is made and they are (0, 0), (0, 1), (1, 0), (1, 1). we can observe that in all 4 cases we can make the result 0 so if the game started in way that P0 will make the last move then P0 will definitely win, after handling this case now we can assume that P1 will play that last move, that means we can assume P0 will play when array length is odd and P1 will play when array length is even.
now let H be maximum number of non-neighboring ones in the array, for now we will claim that P1 can play his moves such that he doesn’t decrease H, while P0 can play his moves to decrease H by at most 1 (i.e. he can’t decrease it by 2 or more), we will prove that later, but let’s assume this is correct for now.
P0 will win if and only if H became 0 in the end of the game, that means P1 should try not to decrease H while P0 should try to decrease it but since he can decrease it by 1 in each of his turns then this will lead us to conclude that P0 will win if and only if H at the beginning of the game is less or equal than number of turns that P0 will play. so to solve the problem we only need to calculate H which is trivial to calculate in O(N), then compare it with the number of turns that P0 will play.
proof: P1 can always play such that H doesn’t decrease
if H < N/2 where N is current length of the array then there must be at least one pair of adjacent elements that are not included in maximum non-consecutive ones, P1 can simply choose them and H will not decrease.
if H = N/2 then either the first element or the last element will not be part of the maximum non-consecutive ones (Remember N is even because it’s P1’s turn), if it was the first element then P1 should choose first two elements and replace them with 1, otherwise he should choose last two elements and replace them with 1, so in this case H will not decrease.
proof: P0 can play so that to decrease H by at most 1
whatever two numbers P0 did choose at most one of them will be part of maximum set of non-neighboring ones, so if he removed them and replaced them with 0 then the same set (excluding deleted numbers) will work to be of non-neighboring ones of size H-1