The three harder problems gave everybody a chance to shine in the area one likes the most: a tricky greedy requiring careful implementation, a nice max-flow graph puzzle, and a logical case study together with Burnside's lemma or combinatorial dynamic programming. Solving any of these three problems together with the easy problem A was enough to advance to the next round.
The max-flow (spoiler alert :)) puzzle was, in my opinion, the most beautiful. You were given at most 200 sentences containing at most 3000 words in total, and told that the first sentence is in English, the second is in French, and the rest is unknown. You needed to pick a language for each sentence in such a way that the number of words that appear in both languages is minimized. Can you see how to do it? The problem statement is so simple that makes me wonder if somebody has already come up with something similar - have you encountered something like this before?
8 out of the 42 competitors who advanced to the next round were competing onsite in St Petersburg ITMO, including three out of the top five. It was exciting to meet with everybody again - thanks a lot to TopCoder and ITMO for organizing the event!
The medium problem required making several simplifying steps in sequence, and thus is a good example to train on. You are given a tree where each edge has an integer length, and some nodes of the tree contain foxes. What is the smallest number D such that it's possible for each fox to travel at most D, ending up in a vertex, in such a way that the vertices occupied by foxes form a connected subset?
The first step is straightforward: when you are asked "what is the smallest number D such that", it's often wise to learn to answer "is the given number D enough" question and apply binary search to solve the original problem. But what would you do next?
0 komentar:
Post a Comment