PROBLEM LINKDIFFICULTYEASY PREREQUISITESDynamic Programming PROBLEMYou are described a game between Alice and Bob.
You have to calculate the maximum number of candies the winner would have at the end.
QUICK EXPLANATIONThe 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,
EXPLANATIONLet 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,r11,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,c11] ) 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
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,M1,0,N1]. SETTERS SOLUTIONCan be found here. TESTERS SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Nov '12, 18:33

similar problem: http://www.spoj.pl/problems/TWENDS/ answered 12 Nov '12, 21:53

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
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 TShirt from Codechef
(13 Nov '12, 15:40)

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
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/howisthedefaultjavaheapsizedetermined The question was about stack size  http://www.onkarjoshi.com/blog/209/usingxsstoadjustjavadefaultthreadstacksizetosavememoryandpreventstackoverflowerror/ 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)

I followed the same algorithm, every time it was bob's turn i did the following 
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
it seems, that for this input
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)
Sorry I wrote it swapped, my code returns 554 and that's more than 528. If I try simple min max strategy: steps
so B can take at least 541 candies (and it's not optimal still)
(15 Nov '12, 14:53)

@gamabunta: Hi, Can you please provide me with one testcase 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
1
@betlista: Hi, I think 18 is the correct answer for this testcase. 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)
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)
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:
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)
Probably there is problem in algorithm somewhere, try this one:
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)
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

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
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)

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 . answered 18 Nov '12, 15:30
1
Yes, there is such possibility, I added few of them here f.e.:
your code returns 497, correct answer is 503. also
your code returns 540, correct answer is 554.
(18 Nov '12, 15:48)

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
