September 2011 Contest Problem Editorials

Problem Tester for the September 2011 Contest was Shilp Gupta.

-------------------------------------------------------------------------------------------------------

CHEFBRO (written by Vamsi Kavala)

The problem saw a lot of successful submissions with mostly the same approach(but different implementations).

This problem is a simple application of Sprague-Grundy theorem (http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem) .

It is easy to see that if a coin is at (i,j) on a board with dimensions n x m, it is equivalent to the coin being on a board with dimensions (n-i) x (m-j). It means we can replace the board with a new board of dimensions (n-i) x (m-j). So we can look at it as a game where the given boards are getting smaller and smaller with every move until the size of the all the boards becomes 1x1.

We can associate grundy number with a board of dimensions n x m. Let g[n][m] be the grundy number associated with a board of dimension n x m. The board can be “resized” according to any of the VALID moves. So using the property of grundy numbers (http://en.wikipedia.org/wiki/Grundy_number) we can easily see that:

g[n][m] = mex( g[n-1][m], g[n-2][m], g[n-1][m-1], g[n-2][m-2], g[n][m-1], g[n][m-2])

Now, once we have the grundies of every given board, g[n1][m1] XOR g[n2][m2] XOR ......... XOR g[nc][mc] = 0 will tell us that the brother wins. If it is non-zero, our Chef wins!

Calculating the grundy numbers for every test case will give a TLE. If you observe carefully, the grundy numbers associated with every dimension will remain the same (i.e. do not depend on the test case). So we can precompute all the grundy numbers and use these values later.

The time limit for this problem was a little on the relaxed side. The above approach would pass without any trouble. But a lot of users solved it using the following approach which uses lesser space and time.

This approach is based on a simple observation which is not hard to see (working out a few examples manually would help you see it).  The observation being: Grundy number of any board will not exceed 2. More specifically, grundy of a board of dimensions of n x m will be given by:

(n+m-2)%3. We have the grundy of every board in O(1) time and space. We can proceed similar to the previous approach now.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

CNTHEX (written by Imran Sunny)

This problem looks quite mathematical and most of the accepted solutions were mathematical too. But the time limit was quite relaxed to allow DP solutions too. I am going to explain a DP approach which does not involve any kind of math.

Fix the biggest edge, say 'M'. First calculate all the 5-tuples maintaining the "good" condition (hexagon or not hexagon). This is the easy part, you can just use backtrack to calculate that.

Now calculate all the 5-tuples which are not a hexagon and subtract those from the first to get the count of valid hexagons. This is the hard part.

A DP on digits with some precalculations can be used for that. Place the numbers in non-increasing order. So you are counting the number of ways to place 5 non-increasing integers such that the first integer is <=’X’ and their sum is <=’M’. The DP goes from left to right digit by digit of ‘M’.

The states of DP are: ( position, prefixX, prefixM, carry, an encoding of digits ( say S) )

position = position of the current digit of ‘M’ from left ( 0 ~ length of 'M')

prefixX  = whether the first number currently is a prefix of 'X' or less than 'X' ( 0 or 1)

prefixM  = whether the summed number currently is a prefix of 'M' or less than 'M' ( 0 or 1)

carry    =  the carry after placing the digits at this position ( 0 ~ 4)

S  =  a state encoding the relative orders of the partially filled numbers.

For example, say you are at position=3. And the partially formed numbers are:  {123,120,120,085,085}.

Now this can be encoded as : { 9,8,8,7,7}  [ The second and third number currently are equal and also the fourth and fifth and the numbers are placed in non-increasing order]. There are 16 different such encodings for five numbers.

Some precalculations can help in the DP part.

cnt1[ a][b][c1][S][c2][T][ z]= Number of ways to go( ways by placing 5 digits) from state S, carry c1 to state T, carry c2 such that the first digit is = 'a' and the digit after summing is=  'b'.

cnt2[ a][b][c1][S][c2][T][z] = .... first digit <= 'a' and the digit after summing is = 'b'

cnt3[ a][b][c1][S][c2][T] [z]= .... first digit  = 'a' and the digit after summing is <= 'b'

cnt4[ a][b][c1][S][c2][T][z]= .... first digit <= 'a' and the digit after summing is <='b'

For all the above arrays, z = 1 counts where last digit is zero and z=0 counts with any last digit.

All these can be precomputed by backtracking.

You can view solutions here:

Problem Setter Solution

-------------------------------------------------------

HAUNTED (written by David Stolp)

The challenge here is to simulate Chef's potential escape from the maze within the time constraint. For each time index from 0 until Chef faints from hunger, we calculate every position in the maze Chef could safely occupy. To advance from one time index until the next, for every safe square in the current time step, we mark all of its neighbors as safe in the next step, then mark squares that contain ghosts as unsafe, then move the ghosts, and mark their new locations as unsafe as well. Without optimizations, this approach will time out.

The key is to use bitsets to store the safe positions. Suppose we use one bitset per row of the maze. Then to simulate a north or south move, we need only apply a bitwise "or" between two rows. To simulate an east or west move, we shift the bitmask right or left. The walls of the maze can also be stored as a bitset, and a bitwise "and" operation is used to make sure Chef doesn't try to pass through a wall. Thus it only takes O(M+C) to simulate one time step, instead of O(M*N+C).

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------

SHORT (written by Gennady)

You can view the editorial here.

Anton Lunyov provided an alternative explanation to this problem. You can view his version here.

You can view solutions here:

Problem Setter Solution

-------------------------------------------------------

TILT (written by David Stolp)

This problem had the lowest number of successful submissions ever for a challenge problem, which I found quite surprising. I did not mean for the problem to be so difficult.

The author's solution works as follows:

The main solver function takes 2 parameters. The first parameter is the number of moves to look ahead, and the second parameter is a value that will change how the heuristic is calculated. From any state, consider all possible sequences of moves of length equal to the "look ahead" parameter. Rank these sequences based on the change in score, the heuristic, and whether any balls fell into holes. Execute the first move of the best sequence (or if there's a tie, choose randomly).

The heuristic is calculated as follows:

If there are no inverter balls left, add m for every remaining positive ball, and subtract m for every negative ball, where m is a parameter that varies from run to run. Otherwise, add m for every remaining positive ball and negative ball. Then, subtract cieling((remaining balls)/holes).

Since the algorithm may not always yield a solution, it is executed repeatedly with different parameters and random number seeds until a solution is found.

A better solution is to use a Beam Search. See ACRush's winning solution for an implementation.

You can view solutions here:

Problem Setter Solution

-------------------------------------------------------

TRMAG (written by Saransh Bansal)

You can view the editorial here.

You can view solutions here:

Problem Setter Solution

Problem Tester Solution

-------------------------------------------------------