CANDYGAM - Editorial

PROBLEM LINK

Practice
Contest

DIFFICULTY

EASY

PREREQUISITES

Dynamic Programming

PROBLEM

You are described a game between Alice and Bob.

  • There is an M by N board of candies.
  • In Alice’s turn, she picks either one of the first row, last row, first column or last column depending on which one has the least value.
  • In Bob’s turn, he picks either one of the first row, last row, first column or last column depending on which maximizes the number of candies he has at the end.

You have to calculate the maximum number of candies the winner would have at the end.

  • An additional piece of information is that if this strategy allows for both Alice and Bob to have the same number of candies, then both are winners and can take all the candies home.
  • But Alice’s strategy is well defined for any state.
  • And Bob’s strategy is not trying to optimize the “total candies” a winner can take. Only his own.

QUICK EXPLANATION

The constraints allow for a straight forward dynamic programming formulation of the problem.

Let bob[r0,r1,c0,c1] represent the maximum number of candies that Bob can get in the submatrix from row r0 to r1 (inclusive) and column c0 to c1 (inclusive).

We can assume that before every turn that Bob takes, there is a move by Alice. Since Alice’s moves are predictable, we can simulate one move by Alice right before any move by Bob.

This means,

  • We can find what move Alice will make and remove the first row, last row, first column or last column accordingly.
  • Then, we recurse over the four possible moves that Bob can make and choose the maximum result (plus the move that we chose to make for Bob.

EXPLANATION

Let us look at how bob[r0,r1,c0,c1] may be implemented.

bob[r0,r1,c0,c1] =
    switch( alice_move[r0,r1,c0,c1] )
        case first_row:
            r0++
        case last_row:
            r1--
        case first_column:
            c0++
        case last_column
            c1--
    return max (
        sum of row r0 from c0 to c1 + bob[r0+1,r1,c0,c1],
        sum of row r1 from c0 to c1 + bob[r0,r1-1,c0,c1],
        sum of col c0 from r0 to r1 + bob[r0,r1,c0+1,c1],
        sum of col c1 from r0 to r1 + bob[r0,r1,c0,c1-1]
    )

It is obvious that bob[] is memoized for speed.

We also want to make sure that all the sums inside bob[], including Alice’s move are calculated in O(1) time.

To achieve this, we can use the following precomputed arrays

  • row-sum[r,c0,c1] = the sum of elements in row r from column c0 to c1
  • col-sum[c,r0,r1] = the sum of elements in column c from row r0 to r1

These can be pre computed in O(M*N*N) and O(N*M*M) time respectively.

Now, they can be used inside bob[] while predicting Alice’s move, and to try all moves for Bob. The answer would of course be bob[0,M-1,0,N-1].

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

similar problem:
http://www.spoj.pl/problems/TWENDS/

1 Like

I did the same thing


[1] but everytime got Wrong Answer .And I could not figure out the mistake in the last 4 days on the same question ..Please some one help me by finding the bug.


  [1]: http://www.codechef.com/viewsolution/1541870

I changed a single character and your code gets AC.

Note the change using any diff tool :slight_smile:

Submission here.

1 Like

JAVA code gave me RTE, while the same algorithm in C gave me AC.
What exactly is the stack size on Cube for JAVA?

Omg…What would you say that…Thank You anyways for looking into a clumsy code…I wish I had seen this , then I would have received another T-Shirt from Codechef

I followed the same algorithm, every time it was bob’s turn i did the following -

  1. Since Bob could remove First Row/Column or Last Row/Column, i computed 4 matrices (m1,m2,m3,m4) that could result from these 4 choices.
  2. For each of these matrices i found number of candies, Alice would remove in the next turn.
  3. Thus, the alternative which made Alice remove the least number of candies, was chosen by Bob.

This continued until the matrix was empty. This is the


[1] i submitted.
Could you **PLEASE** have a look and tell me what am i missing in my code ?

Thanks.


  [1]: http://www.codechef.com/viewsolution/1514495

@gamabunta: Hi, Can you please provide me with one test-case where my code fails.I did exactly what the editorial says but got the WA everytime.I just want to validate my code.Here is my code… http://www.codechef.com/viewsolution/1522752

Please give it a look. :slight_smile:

Your code returns for

1
4 3
4 1 4
1 6 1
1 2 1
3 2 3

18, my code returns 17.

@betlista: Hi, I think 18 is the correct answer for this test-case.

Alice : Takes last row. (3+2+3=8)

Bob : Takes first row. (4+1+4=9)

Alice : Takes first column.(1+1=2)

Bob : Takes first column.(6+2=8)

Alice : Takes first row. (1=1)

Bob : Takes first row. (1=1)

In the end bob wins with total=9+8+1=18 candies.

Please correct me if I am wrong.I am not able to figure out why 18 is wrong .I checked with other submissions ,and It looks like 17 is correct.

1 Like

You are correct I incorrectly updated test case for my solution…

So,is my code correct ?

I don’t think so. In yours implementation the Bob’s strategy is greedy - he takes possible max in current step. I do not know the counter example.

In problem statement there is:

It’s quite evident that their strategy is not optimal. It might happen that Bob loses a game

I din’t find test in which Bob looses (except 1 x 1, where Alice takes all candies in first step) too.

1 Like

Yeah ,I get it now.I misinterpreted the question.Thanks for your time. :slight_smile:

Probably there is problem in algorithm somewhere, try this one:

1
4 4
83 43 69 43
35 45 39 33
 9 76 39 55
22 88 58 60

your code returns 261 and that’s lower than one half of the whole matrix (797), so it cannot be a winner.

Also the greedy returns 497, but my solution returns 503.

Yup,You are correct. My solution is incorrect.

In Java… the VM by default allows a maximum allocation of 64MB.

@codersrikant that was true for old JVM, actually it’s something like 1/4 of RAM - http://stackoverflow.com/questions/4667483/how-is-the-default-java-heap-size-determined

The question was about stack size - http://www.onkarjoshi.com/blog/209/using-xss-to-adjust-java-default-thread-stack-size-to-save-memory-and-prevent-stackoverflowerror/

And in this thread EgorK asked to increase stack size (without response).

1 Like

Thank you betlista for the info.

@betlista I am sorry but I do not know about the stack size issue in JAVA. I would certainly like to help bringing it to attention.

The JAVA stack size is left to the default in both Pyramid and Cube.

Why was this not an issue on pyramid? Or it was and we didn’t notice it for 3 years?

//