USACO Silver: Triangle

[brsca]

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!

[Benq]

@thecodingwizard

If you don’t understand the problem solution conceptually:

These are great questions to ask in the Forum! Make sure to let us know what part of the solution doesn’t make sense to you instead of simply saying “I need help on this problem.” If you really don’t understand any part of the solution, that’s fine – you should specify this in your question.

\quad

[brsca]

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.

[Benq]

Have you tried running it on an example case?

[brsca]

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)”

[Benq]

@brsca

Yeah but I don’t really understand the explanation from the editorial.

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).

This might be helpful.