The Way Through The Forest

Today, the results for the December 2018 contest came out. I got 409 points in the Gold Division, much better than any of my previous Gold scores but still worse than I expected. As 2018 passes into 2019, I took time to contemplate the difficulties and achievements of the past two years. 2016 - 2017 My first USACO contest in December 2016 went quite smoothly; all of the questions were moderately challenging, but I ended getting all but one correct. That one problem stumped me for quite a while; in the end, I got only half credit for the question. Overall, I got 800 points out of the total 1000 points. However, I was still quite happy knowing I would definitely cross the promotion threshold, which I did. New Year's came and went, and soon, it was time for my second USACO contest. I was now in the Silver division, a tad harder than the Bronze division but not too much harder; after trying my best, I got 223 points out of the total 1000 points. When the 4-hour timer ran out, I s...

Floyd-Warshall's for k in 1-N do:     for i in 1-N do:         for j in 1-N do:             d[i][j] := min(d[i][j], d[i][k]+d[k][j]) Why it Works Floyd-Warshall's is an algorithm for computing all-pairs shortest paths, taking a DP approach: selct any "middle node" K and two nodes I and J in which you'd like to calculate the shortest path for, and then define the shortest path between I and J as whichever is smaller, the current shortest path betwen I and J OR the current shortest path between I and K plus the current shortest path between K and J. At first this may seem obvious. Let's delve into why it works. If we iterate K from the beginning (1 to N), at any given point in time whilst K is strictly less than a definite number X, we can say that the current shortest path between any two nodes I and J (regardless of whether I=X or J=X) that the current shortest path will NOT include X. The start and end nodes may inc...