Competitive Programming Sum of Pairs
Or like problems that seem like O(n^2) that you solve in O(n)
Lots of ideas are using prefix sums, sliding windows, 2 pointers.
This is the most classical problem, where you are asked to compute the sum of paired distances between points
I was trying to go for this idea
- Though this is actually a little complicated, I feel like there is a simpler solution
Ok so in this case, you should not reason about the sliding window stuff. But rather, think about the number of times the number is being used. If it was euclidean distance instead of manhattan distance, I don’t think this works…
I really liked this problem:
- https://codeforces.com/contest/2042/problem/C
- Basically, think of this problem as like a sliding window
- Okay, where can we split the groups? The idea is like, you don’t really care about group it is, but rather, you store where the splits are, and sort by the most advantageous
- And when you add, it automatically sums correctly
Shayan helped me understand how it works.