The following will be a very dramatic rendition of my silver contest. Read the end if you don't care.↵
↵
As SpidermanFar fromNo Way 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<long long> 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 John's cows are closest to the grassy fields. If John's cows are closest to a certain field, he gets a tastiness score. Given points on a number line with fields and their tastiness scores, find the placements of N cows that allow for the max tastiness score. ↵
↵
Let's simplify the problem.↵
↵
↵
↵
We want to maximize the number of points with the least amount of Johns cows.↵
Well, there are 3 different types of sections that we can maximize points in. Everything left of Nhoj's first cow and everything right of Nhoj's last cow can be taken with just 1 of John's cows.↵
↵
Now here's where it gets complicated, what do we do with those middle sections? ↵
After a bit of thinking, I realized that the best possibilities are the following. ↵
↵
Directly in the middle of the section, (just in case if the best fields are in the middle)↵
Close to the leftmost field in the section (just a bit closer than Nhoj's leftmost cow)↵
Close to the rightmost field in the section (just a bit closer than Nhoj's rightmost cow)↵
↵
Through a lot of trial and error, I figured it out.↵
↵
I in-contest promoted on a silver contest and then preceded to tank gold. But it's fine, I'm going to grind CF, Atcoder, and USACO. Times are sometimes tough, but today the winter winds were somewhat warm to me.↵
↵
I hope this was somewhat inspirational because a lot of people are stuck in silver, but I hope that everyone and promote and have high ratings in the future.↵
↵
↵
Plat is next baby!
↵
As Spiderman
↵
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<long long> 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 John's cows are closest to the grassy fields. If John's cows are closest to a certain field, he gets a tastiness score. Given points on a number line with fields and their tastiness scores, find the placements of N cows that allow for the max tastiness score. ↵
↵
Let's simplify the problem.↵
↵
↵
↵
We want to maximize the number of points with the least amount of Johns cows.↵
Well, there are 3 different types of sections that we can maximize points in. Everything left of Nhoj's first cow and everything right of Nhoj's last cow can be taken with just 1 of John's cows.↵
↵
Now here's where it gets complicated, what do we do with those middle sections? ↵
After a bit of thinking, I realized that the best possibilities are the following. ↵
↵
Directly in the middle of the section, (just in case if the best fields are in the middle)↵
Close to the leftmost field in the section (just a bit closer than Nhoj's leftmost cow)↵
Close to the rightmost field in the section (just a bit closer than Nhoj's rightmost cow)↵
↵
Through a lot of trial and error, I figured it out.↵
↵
I in-contest promoted on a silver contest and then preceded to tank gold. But it's fine, I'm going to grind CF, Atcoder, and USACO. Times are sometimes tough, but today the winter winds were somewhat warm to me.↵
↵
I hope this was somewhat inspirational because a lot of people are stuck in silver, but I hope that everyone and promote and have high ratings in the future.↵
↵
↵
Plat is next baby!
