The following will be a very dramatic rendition of my silver contest. Read the end if you don't care.

As Spiderman Far from Home just hit the theaters in the Americas, I sat in my chair and took the USACO silver contest. My heater was not working properly, but it's Texas, it's like only 50 degrees. (Fahrenheit)

First problem, finding an optimal placement of cows on a number line? Oof... gonna skip that.

Problem two, interesting, a graph problem of which I have to create edges on a graph with a minimum cost. I can definitely do that. Ideas came flooding in my head. I have to connect node 1 and node N, but how do I do that optimally?

Ahh! node 1 and node N are in their own set. Then the question is just finding the right union between those sets with the lowest cost. I could just DSU it. Find the set with the smallest size and binary search the larger set to find the optimal placing. Problem 2, solved (2hr 50 min remaining). Time is ticking.

Problem 3, hmmmmm..................................................... Scrolls down Yeah it was made my ben qi so it must be hard. Given a bunch of intervals of a and b, find the number of possibilities of each number from 0..2M (K) which fulfill the condition

a1+a2<=k<=b1+b2 using two intervals

with (a1, b1) and (a2, b2) being pairs of intervals

First, I started rearranging the variables, yeah was didn't work. Waittttt a minute, M is only 5000, meaning I can do an algorithm that is O(M^2) time! Ok ok ok ok, what can I do?

Let's simplify the problem, what if B was infinity? Than every k greater than or equal to a1+a2 would work. Wait, this sounds like prefix sums. Well, I know that A will always be less than B, so I can make big prefix sum representing the amount of possibilities that fulfill the condition for each K. I'll count all the times an interval starts with a certain A, then do the same for B. In my prefix sum, I'll have two for loops.

vector p(2*M+5); for i...M for j....M p[i+j]+=acnt[i]*acnt[j]; p[i+j+1]-=bcnt[i]*bcnt[j];

Where i and j represent different starting points for a There are acnt[i] * acnt[j] different possibilities for pairs of intervals that satisfy a1+a2<=k.

Where i and j represent different ending points for b And bcnt[i]*bcnt[j] represent the different possibilities that are greater than k, thus I have to subtract them.

Problem 2 Down (50 min left)

Oh damn, I only have 50 min on the hardest problem. Despite it being freezing temperates in Texas, I pushed forward and stared the problem in the face.

Ok, Farmer John and Farmer Nhoj have cows on a number line, and you have to place Farmer John's cows so you can have the most grassy fields. Given points on a number line with their tastiness scores, find the placements of N cows that allow for the max tastiness score.

Let's simplify the problem.