PROBLEM LINK
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.
