PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
PROBLEM:
2-player game played on k piles of integers where in each turn a player chooses one pile and a number in that pile; all numbers greater than or equal to the chosen number are deleted from the chosen pile. Before the game starts, player 1 will decide to choose either EVEN or ODD numbers throughout the game and the other choice goes to player 2. Both players take turns alternately and the player who can not make move loses. Find if it is possible for player 1 to always win the game by choosing EVEN or ODD.
QUICK EXPLANATION:
The problem is reducible to blue-red hackenbush where each pile is equivalent to a hackenbush stalk. Even and Odd numbers can be mapped to blue and red line segments in the original version of the game. The overall game value can be calculated as a sum of all the game values corresponding to each stalk.
Very good explanation of hackenbush game and calculating the game values can be found here
EXPLANATION:
Let’s assume if game is in favour of EVEN we’ll give it positive value and otherwise negative.
This means:
if(GameValue > 0 ) printf("EVEN\n");
else if(GameValue < 0 ) printf("ODD\n");
else printf("DON'T PLAY\n");
Let observe some simple cases:
Case 1: Only one pile containing {2} -> Since game is clearly in favor of EVEN, we can assign it value V
Case 2: Only one pile containing {3} -> we can assign it value -V
Case 3: Only one pile containing {2, 3} -> Chef can win this game by choosing EVEN so game is in favor of even(hence +ve value) but should we give this case value less than V? Let’s try to answer this question by comparing case 1 and case 3.
If chef has both piles {2}, {2, 3} and some more piles such that overall game is in favor of EVEN then pile {2, 3} is less desirable than pile {2}; because when chef is playing on some other more critical pile, second player has a “free” move to play on pile {2,3}. Lets give this pile a value of V/2
Now if we can ensure that the values we assign to the piles are such that their relative order is always consistent with their ability to turn the game in favor of EVEN or ODD, then we can calculate the overall game value as a sum of all values assigned to individual piles. [This means if 2 piles p1 and p2 both have smallest number EVEN but p1 has more possible moves for ODD than p2, then value assigned to p1 < p2 but it is +ve]
Now the only thing left in this problem is to determine how to calculate the value for any given pile. We can use this scheme to calculate value of each pile:
- Until the parity changes for the first time, each number is worth +V or -V (depending on whether it is Even or Odd, respectively).
- Once parity change occurs, each subsequent number (regardless of being Even or Odd), is worth half of the previous value, with a +/- corresponding to the parity
Lets take this pile for example {4, 8, 9, 11, 16}. Its value can be calculated as: +V +V -V/2 -V/4 +V/8 = 11V/8
See section 11.1 here to read more about this value calculation.
Algorithm to calculate GameValue:
GameValue = 0;
For each pile:
Read the pile and sort
v = Calculate the value as explained above
GameValue += v
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here
Testers’ solution can be found here and here