×

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.

This question is marked "community wiki".

2.4k128183169
accept rate: 14%

 1 similar problem: http://www.spoj.pl/problems/TWENDS/ answered 12 Nov '12, 21:53 4★faiyaz26 15●1●2●6 accept rate: 0%
 0 I did the same thingcode 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. answered 12 Nov '12, 22:42 81●1●7 accept rate: 0% 1 I changed a single character and your code gets AC. Note the change using any diff tool :) Submission here. (12 Nov '12, 23:06) 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 (13 Nov '12, 15:40)
 0 JAVA code gave me RTE, while the same algorithm in C gave me AC. What exactly is the stack size on Cube for JAVA? answered 13 Nov '12, 00:01 2★svm11 429●3●7●9 accept rate: 12% In Java.. the VM by default allows a maximum allocation of 64MB. (13 Nov '12, 23:13) 1 @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). (13 Nov '12, 23:21) Thank you betlista for the info. (14 Nov '12, 13:21) @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? (14 Nov '12, 18:25)
 0 I followed the same algorithm, every time it was bob's turn i did the following - 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. For each of these matrices i found number of candies, Alice would remove in the next turn. 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 code i submitted. Could you PLEASE have a look and tell me what am i missing in my code ? Thanks. answered 13 Nov '12, 17:48 2★ankit459 1 accept rate: 0% it seems, that for this input 1 4 4 34 70 66 56 94 89 22 67 22 9 26 79 30 78 73 63  your code returns 554, my returns 528. (14 Nov '12, 22:36) hey i tested my code again. This is my code : http://www.codechef.com/viewsolution/1514495 But i'm getting 528, i guess same as you. Thanks anyways :) (15 Nov '12, 14:01) ankit4592★ Sorry I wrote it swapped, my code returns 554 and that's more than 528. If I try simple min max strategy: steps A takes first column +180 (A=180) B takes last column +265 (B=265) A takes first row +136 (A=362) B takes first column +177 (B=442) A takes first row +22 (A=384) B takes all remaining candies +121 (B=541)  so B can take at least 541 candies (and it's not optimal still) (15 Nov '12, 14:53)
 0 @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. :) answered 13 Nov '12, 19:07 2★g4ur4v 76●5 accept rate: 0% Your code returns for 1 4 3 4 1 4 1 6 1 1 2 1 3 2 3  18, my code returns 17. (13 Nov '12, 20:26) 1 @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. (13 Nov '12, 21:13) g4ur4v2★ You are correct I incorrectly updated test case for my solution... (13 Nov '12, 21:49) So,is my code correct ? (13 Nov '12, 21:58) g4ur4v2★ 1 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. (13 Nov '12, 22:02) Yeah ,I get it now.I misinterpreted the question.Thanks for your time. :) (13 Nov '12, 22:20) g4ur4v2★ 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. (13 Nov '12, 22:34) Yup,You are correct. My solution is incorrect. (13 Nov '12, 22:40) g4ur4v2★ 1 tried each and every test case (even given in the comments above) still getting wrong answer.. Here is my code http://www.codechef.com/viewsolution/1556684 Can anyone tell whats wrong? (15 Nov '12, 20:32) showing 5 of 9 show all
 0 tried each and every test case (even given in the comments above) still getting wrong answer.. Here is my CODE Can anyone tell whats wrong? answered 15 Nov '12, 20:33 30●3 accept rate: 0% 2 Woe is a template that has an INF and a BIG_INF, where you forget to think for a moment which one should you use :P (I hope the poetic expression gave away what was wrong in your code. It gets AC here after this small change) (15 Nov '12, 22:56) @gamabunta- dude only one thing to say, you are just excellent.Excellent coding analysing ability.Itne chote se error ne dimag kharab kar rakha tha subah se. :) (16 Nov '12, 02:01)
 0 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 answered 18 Nov '12, 15:30 162●1●3●7 accept rate: 0% 1 Yes, there is such possibility, I added few of them here f.e.: 1 4 4 83 43 69 43 35 45 39 33 9 76 39 55 22 88 58 60  your code returns 497, correct answer is 503. also 1 4 4 34 70 66 56 94 89 22 67 22 9 26 79 30 78 73 63  your code returns 540, correct answer is 554. (18 Nov '12, 15:48)
 0 can anyone plz help me with my code.I m getting correct answer for every testcase given above but codechef is showing wrong answer. answered 20 Nov '12, 19:16 1●1●2 accept rate: 0% try this simple case: 1 1 1 1  (20 Nov '12, 19:23)
 0 thanks a lot betlista...I got my mistake...I modified my code so that it now prints winner's candies not bob's candies but still I m getting a wrong answer. answered 21 Nov '12, 19:45 1●1●2 accept rate: 0%
 0 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 answered 08 Jan '13, 12:43 1★sumanjit 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,005
×3,393
×1,875
×16

question asked: 12 Nov '12, 18:33

question was seen: 10,448 times

last updated: 01 Sep '15, 10:44