USACO February 2008
USACO February Contest 2008, just held. As usual there were 3 problems for each division.
Actually February problem-set is not so hard.
Bronze Division:
-diningb -> straightforward DP problem, which you should precompute the cost to change to card 1 for all length and cost to change to card 2 as well, once you’ve done that you can combine it and get the result, O(N).
-racing -> just a typical simulation problem, all you can do is run trough all the track, O(N).
-cowmult -> using an easy observation of mathematics, we can solve it very easy, O(1).
Silver Division:
-lines -> mathematis + sorting = full score, the only thing that made my code fail to get full score is because my array wasn’t big enough, I forgot that the number of gradiens will probably reach N^2, once I change the array [1..210] to [1..40010] I will get full score, hiks, one more time I hate bug! O(N^2).
-meteor -> a tricky flood fill problem, all you have to do just do a flood fill and simulate the meteors chronologically (you have to sort them first), don’t forget to code your solution clearly, my code didn’t get full score coz I did some bug (arrrghhh, I hate bug!), O(max(T,X,Y)^2).
-egroup -> similar to diningb in bronze division, but this one is a little bit more difficult since we also have card 3, the keyword is only “precompute” and then you can combine it and get the result, another no-hard DP, I got full score for this, O(N).
Gold Division:
-cgame -> when I saw this problem I think about knapsack algorithm, but it’s impossible to have a normal knapsack within that constraint, all we have to do is hack the normal knapsack algorithm (as RK said in the analysis), the fact that we have to hack the normal way make this problem considered as a output-only problem, I only got 5-first-testcases.
-hotel -> problem with advance data structure, I realize what to do to solve it but until now I can’t code binary indexed tree or something like that, that means I have to practice it more, I only got the small testcases since I only submitted my kind of brute force code, the expected solution is run for O(MlogN).
-grading -> a typical DP-push problem, but before that you have to convince yourself with a lemma that no need to change a height into particular height that doesn’t exist in the height set, in other words you only have N possible height to try that makes this can be done in O(N^2), I got full score.
February 13, 2008