CANDYGAM - Editorial

dynamic-programming
easy
editorial
nov12

#1

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.


#2

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


#3

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

#4

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


#5

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

#6

@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:


#7

tried each and every test case (even given in the comments above) still getting wrong answer… Here is my


[1] Can anyone tell whats wrong?


  [1]: http://ideone.com/4CReZE

#8

Is there a possibility that bob leaves greater candies of some row now but get more candies in the end than he might have got if he had taken greater candies in the preceding steps ??

If this is true, then we would have to go through all the combinations of bob as presented in the solution. I went through only cases having largest number of candies among current 4 choices .

my code


#9

can anyone plz help me with my


[1].I m getting correct answer for every testcase given above but codechef is showing wrong answer.  


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

#10

thanks a lot betlista…I got my mistake…I modified my


[1] so that it now prints winner's candies not bob's candies but still I m getting a wrong answer.

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

#11

Heyy I’ve solvd this problem and somehow I’m not able to get why it’s giving me a wrong answer here…would you kindly check the code???
http://www.codechef.com/viewsolution/1693143


#12

I changed a single character and your code gets AC.

Note the change using any diff tool :slight_smile:

Submission here.


#13

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


#14

Your code returns for

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

18, my code returns 17.


#15

@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.


#16

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


#17

So,is my code correct ?


#18

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.


#19

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


#20

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.