USACO Silver: Triangle

I’m kind of confused with the solution explanation for the Triangle problem in USACO 2020 February Contest, Silver. I know that it has to deal with psum’s, but I don’t know how to optimize my code from O(N^2) to O(nlog(n)) to solve all of the test cases. Any help or explanation would be great. Thanks!

1 Like

In the solution from the USACO website, they use if (j) cur = cur+(2*j-sz)*(todo[i][j].f-todo[i][j-1].f); (sz is the number of points in some row, j iterates through the row, i is the index of the row in the matrix, cur, is the sum of adjacent line segments from vertex v)to count the number of adjacent lines from vertex v. However, I don’t understand what the “2 * j - sz” part exactly means.

Have you tried running it on an example case?

Yeah but I don’t really understand the explanation from the editorial. It says,
"

‘’

Can you explain the logic behind “Si+1 = si + (2i - n)(xi+1 - xi)”

The editorial doesn’t explain why the formula for s_{i+1} is correct. It’s left as an exercise to the reader (and it’s not too hard to so using an example test case).