2017: Grid-Game
Medium

table of contents

Another straightforward question!

The question itself can be simplified down quite a bit; I understood the problem as given a 2 x n grid, find the min of the max sum of points present in any corner from any valid position that exists after the first robot moves. It is quite hard to put into words, so I’ll draw a diagram.

Using Example 1:

+-+-+-+
|2|5|4|
+-+-+-+
|1|5|1|
+-+-+-+

Now, since the first robot wants to move from (0, 0) to (1, 2), we know it can take 3 paths:

+-+-+-+    +-+-+-+    +-+-+-+
|0|5|4|    |0|0|4|    |0|0|0|
+-+-+-+ or +-+-+-+ or +-+-+-+
|0|0|0|    |1|0|0|    |1|5|0|
+-+-+-+    +-+-+-+    +-+-+-+

Notice that in all these paths, the second robot is incentivised to move either through the bottom left or top right corner as that is where all the remaining valuable cells are left.

Therefore, in every state, you can focus on finding the max sum of points present in either the bottom left or top right corner. However, since the first robot is playing optimally and trying to minimise the points the second robot is receiving, it means we need to find the min of the max sum of points.


          (9)          (4)          (0)
   +-+-+-+      +-+-+-+      +-+-+-+
   |0|5|4|      |0|0|4|      |0|0|0|
   +-+-+-+  or  +-+-+-+  or  +-+-+-+
   |0|0|0|      |1|0|0|      |1|5|0|
   +-+-+-+      +-+-+-+      +-+-+-+
(0)          (1)          (6)

Hence, from the diagram above, we can see that the answer is 4.

code

class Solution {
public:
    long long gridGame(vector<vector<int>>& grid) {
        // bl = bottom left sum, tr = top right sum
        long long bl = 0, tr = 0;
        for (int i = 1; i < grid[0].size(); ++i) {
            tr += grid[0][i];
        }
        long long ans = tr;
        for (int i = 0; i < grid[0].size()-1; ++i) {
            bl += grid[1][i];
            tr -= grid[0][i+1];

            /* can afford to break early, 
               since if `ans = max(bl, tr)` is true,
               it means that `ans > bl`,
               and since we are always adding to `bl`, 
               `ans < bl` will never occur again */
            if (ans > max(bl, tr)) {
                ans = max(bl, tr);
            } else break;
        }
        return ans;
    }
};

complexity