ANNOUNCEMENT

-
I moved all the posts from Codrspace, another blogging platform. Here is the link to my Codrspace blog (now no longer updated.) So don't think I wrote all these posts in a single day. Thank you.

😌

Comments

Post a Comment

Popular posts from this blog

USACO 2018 January Contest, Gold Problem 1. MooTube

-
USACO January 2018 - MooTube Problem Statement In his spare time, Farmer John has created a new video-sharing service, which he names MooTube. On MooTube, Farmer John's cows can record, share, and discover many amusing videos. His cows already have posted  N  videos ( 1 ≤ N ≤ 100 , 000 ), conveniently numbered  1 … N . However, FJ can't quite figure out how to help his cows find new videos they might like. FJ wants to create a list of "suggested videos" for every MooTube video. This way, cows will be recommended the videos most relevant to the ones they already watch. FJ devises a metric of "relevance," which determines, as the name suggests, how relevant two videos are to each other. He picks  N − 1  pairs of videos and manually computes their pairwise relevance. Then, FJ visualizes his videos as a network, where each video is a node and the  N − 1  pairs of videos he manually considered are connected. Conveniently, FJ has picked his  N...
Read more

A goodbye letter to 2018

-
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...
Read more

USACO Training "Camelot"

-
USACO Training: "Camelot" (This was a hard problem) Problem Analysis If the problem did not specify that the king needed to be picked up, this would be a simple all-pairs shortest pathes problem: find the point (r,c) such that sum(distance((r,c),(i-th knight row, i-th knight column))) is minimized. However, we need to take into account that the king needs to be picked up and ridden to (r,c) too! Our first discovery: The king can only take at most two steps. Why? We notice that for any sequence of three (non-undoing) steps the king makes, the knight can do it in three (or sometimes even two) steps, so it would be inconstructive for a king to move three steps when a knight carrying it can. We try this method: Choose an arbitrary point (i,j). Add up all the distances between each knight and (i,j) - if no shortest path exsists, (i,j) is invalid. For each position a king can be in with at most two moves (ki, kj) find i such that the value: max(abs(ki-kr), abs(kj-k...
Read more