Hello,
I'm confused how to come up with a solution for 738B - Прожекторы. A naive approach should take nearly O(N^4), but the correct approach is only O(N^2).
How to formulate the correct algorith?
Please help me fill the gaps in this approach:
1 — Read all inputs, and in the same time fill values for "UP" & "LEFT". O(N^2) 2 — After reading, run a nested loop over the grid, and sum values for "Down" & "RIGHT". O(N^2)
What is the formula to sum the values?
I can only imagine counting the empty cells with '0' in each row and column, and then when one encounters an occupied cell with "1" is to subtract somehow depending on the position of this one.
I just can't put it all together into a working solution.
Thanks in advance~
Hi! I've just solved this problem and I used 4 prefix sum arrays to precalculate the number of actors from the left, right, top and bottom of each cell. Then you will have overall complexity O(N^2). If you don't know what prefix sum is, you may ask me or try to search for it, it's pretty easy dynamic programming technique. P.S. I can provide the code if you need.
You can use only 2. sum[i] is the sum of all values until i.
For example: if you want to get right[i] from left[i] just get left[all numbers]-left[i-1].
This would be important to save some memory if needed.
Nice idea! However, 4 arrays were easier to think up and implement for me. :)
Thank you for the hint about All Prefix Sum now I can reason about the problem in a structured approach. I also love the memory optimization technique.
All Prefix Sum: 1. https://codility.com/media/train/3-PrefixSums.pdf 2. https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf 3. http://www.drdobbs.com/parallel/the-mystery-and-magic-of-prefix-scan/240001744?pgno=2 4. http://wcipeg.com/wiki/Prefix_sum_array_and_difference_array
There's another approach:
You'll do this for all columns/rows. Run through the row and count how many straight 0's there are before a 1. Sum these 0's in the answer and reset the counter. Do this for both directions. There are O(2*n) columns/rows and O(n) cells in each column/row so this is O(2*2*n^2)=O(n^2)
ie: 0000010000 you run through the row and "remember" all the spots that you haven't found a person yet. Sum that value to the answer and reset it to 0 when you find a person.
I did the same but I only went in one direction per row/column (insignificant in this problem though) by adding the number of zeroes everytime I hit a one, and adding it again if I had met a one before (ie counting from the other side). When I exit the loop I then add it once more if I have met a 1 before (ie considering the first batch from the other side).
I solved in this manner, iterate through all actors (1's in the array). Maintain two vectors of length n and m, where rowvisited[i] = -1 if the row does not have an actors, and otherwise it holds the column of the last actor on the row, similiar idea for columvisited[i]. If the actor is in a row that has not been visited, then add (m-1) to the answer (since there are m positions that the spotlight could be in on that row, but it cannot be on the actor himself), otherwise if the row has been visited, then the spots between this actor and the previous actor on that row can each have two potential positions, so add (currentcolumn — rowvisited[i] + 1) to the answer. Also subtract 1 because this actor also blocks one position for the previous actor.
Same idea for columns.
Code : 22351281
Here is my technique:
First calculate the position of left most 1 and right most 1, i.e. boundary position of left l[i] and right r[i] for each row i. If there is no 1 in any row i, then l[i] and r[i] remains 0.
Then, similarly calculate the position of top most 1 and bottom most 1, i.e. boundary position of up u[j] and down d[j] for each column j. If there is no 1 in any column j, then l[j] and r[j] remains 0.
Finally calculate the ans. Let cnt = 0 Now check for each cell (i, j):
1) if(l[i]!=0 && j>l[i]) cnt++;
2) if(r[i]!=0 && j<r[i]) cnt++;
3) if(d[j]!=0 && i<d[j]) cnt++;
4) if(u[j]!=0 && i>u[j]) cnt++;
print the value of cnt.
And here is my solution: 22396010