Ssjg - editorial

general
, , , ,
1

PROBLEM LINK:

Practice
Contest

Setter: Kunal Jain
Tester: Kunal Jain, Taranpreet Singh
Editorialist: Akash Bhalotia

DIFFICULTY:

EASY

PREREQUISITES:

2-D Prefix Sums

PROBLEM:

An N * N grid contains coins in some cells. Divide it into 4 parts using a vertical and a horizontal line such that the number of coins in the part containing the least number of coins is maximum possible.

CONSTRAINTS:

  • 1 \leq T \leq 10
  • 1 \leq N \leq 1000

QUICK EXPLANATION:

Compute 2-D prefix sums for the grid. For every intersection, compute the number of coins present in its 4 subgrids in constant time using the prefix sums. The intersection that has the maximum min value is the best intersection.

EXPLANATION:

  • We need to calculate the number of coins present in the 4 subgrids created by every possible intersection.
  • We can do this by running nested loops for every intersection. This will take O(N^4), which is sufficient to pass the first subtask, but will result in TLE for the second subtask.
  • Thus, we need to improve the complexity from O(N^4) to O(N^2). We need to somehow make the step of computing the number of coins present in a subgrid a constant time process.
  • We can do this by creating a Prefix sums matrix. PrefSum[i][j] will contain the number of coins present in the subgrid from (1,1) to (i,j).
  • The formula for this is :
Click to view

PrefSum[i][j] = PrefSum[i-1][j] + PrefSum[i][j-1] - PrefSum[i-1][j-1] + coins[i][j]
(why?)

  • If you are having trouble understanding 2-D Prefix Sums, first make sure that you have a good understanding of 1-D Prefix Sums. 2-D Prefix Sums is simply an extension of that in 2 Dimensions.
  • Now let us compute the number of coins present in the subgrids of an intersection at (i,j) in O(1) :
Click to view
  1. Top Left Subgrid: PrefSum[i][j]
  2. Top Right Subgrid: PrefSum[i][N] - PrefSum[i][j]
  3. Bottom Left Subgrid: PrefSum[N][j] - PrefSum[i][j]
  4. Bottom Right Subgrid: M - sum of above three
  • Now we just need to output the maximum min value we can achieve among all intersections.

BONUS:

What if we had to find the number of coins present in a subgrid starting at (i,j) and ending at (x,y)?

Click to view

The general formula for this is:

PrefSum[x][y] - PrefSum[x][j] - PrefSum[i][y] + PrefSum[i][j]
(why?)

COMPLEXITY:

  • Time Complexity: O(N^2) per test case.
  • Space Complexity: O(N^2) per test case.

AC SOLUTIONS:

SIMILAR PROBLEMS:

Feel free to share your approach if it differs. If you have any doubts, or if you feel stuck at any point, you can ask them below. We would love to hear your suggestions :slight_smile:

Thanks to @taran_1407 and @vijju123 for their constant guidance and support.