Editorialist:Harshit Kumar
PREREQUISITES:
- Basic Arithmetic.
- Prefix sum.
PROBLEM LINK: [ZIO 2008 Problem 4]
PROBLEM IN SHORT:
Given a 2-D array of number of trees. find a L-shaped piece in the array containing at least 1st row and 1st column and having at least half the trees in the overall field.
SOLUTION:
- Finding L-shaped piece could be time taking so, we will try to find the rectangle (Manish’s part of field) that is left after removing the L-shaped piece from the field. So, the number of trees in the rectangular part must be equal to or less than half the trees in the overall field.
- To find the rectangle we will modify our array in such a way that every element in ith row and jth column will give us the number of trees that are in the rectangle formed from row i to n and column j to m (largest rectangle having given element as its top left element).
- Steps to Modify the array:
- We want an element of array to give us sum of every element below and right of it.
- So, first in an element we will store the sum of elements below that element. For that in every column we run through index n-1 to 1 and keep on adding present element with previous value in the array.
For example:
- Now, in an element we will store sum of elements right of that element. For that in every row we run through index m-1 to 1 and keep on adding present element with previous value in the array.
For example:
- After modifying the array we will search for largest element whose value is equal or less than half the trees in the overall field except in 1st row or 1st column.
So, for the given array total number of trees would be at position {1,1} that is 80. Then we have to give at least 40 trees to Akhil.
Now, we will search largest element in the array whose value is less than or equal to 40 from row 2 to n and column 2 to m.
Which is 24. So, the answer is 80 - 24 = 56.
Example 1.
So, the total number of trees = 232
We have to give at least 116 (232/2) tree to Akhil.
For that we will search for a value equal or less than 116 in the table except in 1st column and 1st row.
Value = 105 at {3,3} and answer = 232-105 = 127
Example 2:
So, the total number of trees = 392
We have to give at least 196 (392/2)
For that we will search for a value equal or less than 196 in the table except in 1st column and 1st row.
Value = 178 at {3,3} and answer = 392 – 178 = 214
Example 3:
Total number of trees = 222
Half of total = 111
Value = 106 at {3,3}
Answer = 222 – 106 = 116
Note:
- Do the 4th part yourself (answer = 157)
- For programmers - you can find the code here: FmpQm9 - Online C++0x Compiler & Debugging Tool - Ideone.com