USACO March Report

I finally got the Silver division… What makes it special is because i got this “Silver Pass” with “Early Grade”… but this month’s contest is a bit easier than the past contests…

My Solution for the bronze division :
- rollers : i do this in O(N^2). I checked every roller, who has the order of 2 (in contact with EXACTLY TWO other rollers). If they do, then they are in the middle; otherwise if they don’t. then it’s the edge, whether the starting or the finishing edge. Just check, if the edge coordinate is (0,0) then it is NOT the answer…
- lake : i do this in O(m). Just need to check every step made. I use the procedure with the complexity O(9) to check the maximum number of every 3 X 3 area. Then use this algorithm : ar[i][ii]=max(ar[i][ii], ar[xmax][ymax]-maxstep);
-stats : this one is a bonus question i guess… because the knowledge of quicksort is enough… just need to write the mean and median… real quick.

then i work on the silver problems… SCREWED! haha
my analysis : (remember, this is JUST AN ANALYSIS. NOT THE SOLUTION)
- baler : i used O(n^2) solution, i checked which wheel is in touch with which wheel… then i use the backtrack algorithm to parse through the line. I dunno where my error is, but i think it’s because of my data type…
- ctravel : i am really pointless here… i got some clue but after the submission was closed… the only thing that makes this “shortest path” hard is because we can go in the same place twice. Using the parity fundamentals, BFS is enough for this problem… damn…
-river : just a simple DP problem… i just need to check if steps[x]<steps[i]+steps[n-i], with i as the iterator… i did a very stupid bug here… giving constants to variables… just because i ran out of time..

i wish i could be more careful… well, anyway a bit proud for the fullscore i got in the bronze division… next time, GOLD!!!! :p

~ by SkyBlaze on March 23, 2008.