TopCoder problem "CakeParty" used in SRM 338 (Division I Level Three)

Problem Statement


Julianne invited her two friends Michael and Jane to a cake party. When Michael and Jane arrived, they saw that their host had prepared several tables. On each table there was a plate with one of the cakes. Each cake was cut into several pieces.

Not knowing where to start, Michael and Jane decided to play the following game: Players take alternating turns. In each turn the player selects one cake, and takes and eats several pieces of the cake. The player must take and eat at least one piece. The player who eats the last piece of the last cake wins.

However, the host would be really offended if she had the impression that the guests didn't like some of her cakes. Therefore Michael and Jane agreed on one additional rule: Each time a player selects a cake, he or she may only select one of those cakes that have the most pieces remaining.

Michael starts the game and plays optimally. In other words, if there is a strategy that will ensure his win (no matter how Jane plays), he will follow one such strategy. If he finds himself in a position where no strategy can guarantee him winning the game he just makes a valid move. In addition, whenever Michael has more than one move to choose from, he picks the lexicographically smallest one (explained below).

You are given a int[] pieces. The i-th element of pieces is the initial number of pieces of the i-th cake. Return Michael's first move as a String formatted as follows: "CAKE C PIECES P", where C is the zero-based index of the cake he should select and P is the number of pieces he should eat. The numbers C and P must not contain unnecessary leading zeroes. In case there are multiple valid answers return the one where the resulting String is lexicographically smallest.



Method signature:String makeMove(int[] pieces)
(be sure your method is public)


-Ignore the appetite and eating speed of both players. In other words, assume that each of them is able to eat all the cakes in a short amount of time.
-When selecting the correct output, standard string comparison rules apply:

The string A is lexicograpically smaller than the string B if and only if (A is a proper prefix of B) or (there is an integer X such that first X-1 characters of A and B are equal, and the X-th character of A has a smaller ASCII value than the X-th character of B).
-Valid characters ordered by their ASCII values (smallest to largest): space, digits '0'-'9' in this order, letters 'A'-'Z' in this order.


-pieces will contain between 1 and 50 elements, inclusive.
-Each element of pieces will be between 1 and 2,000,000,000, inclusive.


Returns: "CAKE 0 PIECES 47"
With one cake the game is simple: just take everything.
Returns: "CAKE 0 PIECES 1"
Two equally big cakes. This is clearly a losing position for the player to move. Thus we return the lexicographically smallest possible move.
Returns: "CAKE 1 PIECES 2"
The winning move is to create the position from the previous example.
Returns: "CAKE 0 PIECES 1"
This is an almost deterministic game. The players can not influence the result at all.
Returns: "CAKE 2 PIECES 110"
This is a winning position, as we can eat the entire last cake and thus create the position from Example 1. However, this is not the only winning move, and there is a lexicographically smaller winning move than the one we described.
Returns: "CAKE 0 PIECES 1"
Note that we can not eat the last cake now, as it is not one of the largest ones.
Returns: "CAKE 10 PIECES 1"

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy , ged

Problem categories:

Greedy, Math