I tried to solve this problem but couldn’t and it’s editorial has just crossed my head.
please explain me this editorial.
I understood before this part but didn’t get any thing after that part.
“The key to this is to notice that ri can be computed by a simple adjustment from ri−1! In other words, we can just calculate the difference ri−ri-1, and if we have already computed ri-1, then we can calculate ri by adding this difference. In more detail, let’s try to compute ri−ri-1:”
The Basic thing in the question is "tractor passes the whole grid when a rectangle with contiguous N*H empty grid cells is existing. So we have to find such rectangle but with minimum cost of removing the soil from non empty spaces. Let us keep complexity aside for a moment then the best way to solve this problem is that for every ‘a’ and ‘b’ in the input take a matrix with soil as 0 and empty as 1 and upgrade each cell as per the given input and after that pick all rectangles contiguously in chunks of H i.e. height of tractor and find the minimum value of soil removed for every chunk you pick. Now the basic goal is to optimize it. To easily solve this either use segment tree or even without any tree you can solve this.
Let us have two arrays start and end where start[i] denotes total white boxes starting at the ith height and end[i] denotes total white blocks ending at height ‘i’.Now we need one more array named ‘row’ where row[i] denotes how many empty blocks are existing at ith height To calculate this row[i] efficiently in O(N) what you simply need is previous results.
Row[1] = start[1] //all blocks starting at the 1st row is the total gaps in that row
Row[2] = start[2] - end[1] + Row[1]
and so on till …
Row[n] = start[n] - end[n-1] + Row[n-1]
and this gives us the relation Row[i] = start[i] - end[i-1] + Row[i-1]
Now the main thing is how i arised to this conclusion. To calculate empty spaces in a particular row you must know how many empty blocks are starting at that particular row which is start[i] also some blocks may have started at previous rows and may not have ended till now and also some blocks may be ending at this ith row. So basically it means total blocks which have not started in this row but are from some previous rows + total blocks starting in this row.
Now you have your data that For every row you know how many empty spaces are in this row. Now calculate sums cumulatively in groups/chunks of H and the group which has maximum spaces subtract that from N*H and that is your answer. Do comment for HELP
thank you for this smart answer, it helped 