The editorial and problem setter's code is not clear to me. Can someone explain the code. I don't understand how he reduced O( n^2 ) to just O( n ) . Please explain this to me .
Thanks!
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
The editorial and problem setter's code is not clear to me. Can someone explain the code. I don't understand how he reduced O( n^2 ) to just O( n ) . Please explain this to me .
Thanks!
Name |
---|
I can try to explain my solution.
Move is define as moving to a neighbouring cell with adjacent border. Now, let's state a couple of facts (I believe they are easily believable/provable):
Due to these facts, we can now deduce that we are only interested in calculating values of the bottom row and picking maximum of it. For every cell in the bottom row, we are only interested in minimum of all paths described above. As such, for a cell (i, 1):
First term is O(1) for a cell, while second and third can be precomputed in advance from left and right sides by noting that for neighbouring cell in the direction of increasing amount of terms, all previously existent terms are increased by one and we just add a single new one.
In brief: Use prefix and postfix summs
Ok, I think I got it.
worst stores t[j]-j in the worst case from left to right. So, if t[i]-i is greater than worst, we simply assign res[i] = t[j]-j+i , else res[i] = t[i] .This way, we can ensure that the lowest value is assigned that falls on left of t[i] . (j<=i)
This works because, if t[j]+i-j > t[j+1]+i-j-1 then t[j] >= t[j+1], which is true in this case.
Phew! Such twisted logic. I'm respecting people who solved such problems even more now :)
edit: Another way(and much more intuitive and understandable) is: we are trying to find min ( t[i-j] + j ), for each j, for a fixed i. This minimum value is res[i].
Let p=i-j. So, j=i-p Now, the statement becomes min(t[p]-p) + i for each p, for a fixed i .