Unfortunately I was unable to pass into the Silver Division this competition but there was marked improvement from my previous attempts. Needless to say, I am at least proud of much much better as a programmer this year than I was the last time I competed.
In during the competition, I completed first and third with full marks quite easily, but was completely stuck on the second problem. I am going to quickly go over my thoughts durring each problem and my problem solving process. You can find the problem statements for this contest on the USACO website once they but I won’t go over what the problems were since I don’t exactly remember them, so apologize about that.
For the first problem, it was quite obvious with some critical thinking that the most optimal way for Elsie to play was simply constructed from the corresponding suffix and prefixes of the given array such that there is k values accounted for total, and that this is the highest sum given these contrainst. We can check this quick easily by consructing a prefix sum array in O(N) and then trying all solutions in O(K). Then to find Bessie’s answer, take the complement of Elsie’s answer.
There will be no complications like Elsie eating cakes that have been combined by Bessie, since allowing that to happen would be suboptimal for Bessie, making it impossible.
For the third problem, I first noticed that for any given board state, a square is deemed alive if it is directly neighboring another alive square. This makes it a simple floodfill problem. Second, it was very difficult to construct the graph as Farmer John added his converyor belts, as each time Farmer John added a converyor belt, assuming that you already had an existing board state, you would need to check if it is still, alive. Then if it wasn’t, you would need to check all neighboring pieces squares, and overall just be a very messy solution that I didn’t like.
However, I noticed that this process was simplified if you were removing squares instead. Instead of needing to check and update a ton of neighboring squares, you can know with certainty that all alive squares are unchanged, so you can simply floodfill through the square that was added and flip all converyors that run into it to free.
I actually really like this solution since just like many cool programming solutions, you need to look at the problem from a different direction to find a good and simple solution, one of the parts I always find fascinating about Computer Science.
Now for the dreaded second problem, I will be very frank about this. I had no clue how to solve this. because it involved countring trees within intervals, I can guess that it likely uses prefix sums, some form of line sweep and maybe pointers. This is because prefix sums and pointers are always common techniques used in problems dealing with subarrays, and linesweep is a very common and flexible technique for interval problems.
However, I could not understand how I would implement these things to solve it. Since I had a lot of time, I was able to code up a few solutions to at least get half the test cases to no avail.
My final solution was a greedy solution was to go through the plot of land using a line sweep algorithm and remove trees while the each interval ended by checking how many trees I can remove while still satisfying all currently existing intervals. As you can probably notice, this solution was in polynomial time so it was also too slow.
I look forward to seeing the results, and seeing what the real solution was. Either it was something insanely brilliant, or I missed an obvious observation, we will see. Regardless, I will keep practicing and definitely pass next month!
Lingyuan's blog 