×

SSJG - EDITORIAL

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

EASY

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 :
View Content
• 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) :
View Content
• 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)?

View Content

COMPLEXITY:

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

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

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

This question is marked "community wiki".

68112
accept rate: 14%

 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:

×3,767
×177
×31
×28
×16
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}