A week with a new max-flow problem

Codeforces Round 305 started this week's competitions on Tuesday (problems, results, top 5 on the left). Nobody got all problems right despite the promise of an easy contest, and dreamoon got the first place being the only one to solve the two hardest problems correctly - congratulations!

Google Code Jam 2015 Round 2 took place on Saturday at the time which minimizes the number of people who have to compete in the middle of the night - 14:00 UTC (problems, results, top 5 on the left). Gennady has earned another very convincing victory - amazing performance!

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?

Russian Code Cup 2015 Qualification Round 3 was the last chance to advance to the next stage for Russian-reading contestants (problems in Russian, results, top 5 on the left). The two top spots with just one minute of penalty time difference were occupied by GlebsHP, the double ICPC gold medalist, and KAN who needs to live up to quite big expectations at the next year's ICPC. Congratulations to Gleb and Nikolay!

TopCoder Open 2015 Round 2A has wrapped up the week (problems, results, top 5 on the left). This time it was KAN's teammate's turn to convincingly claim the top spot - way to go Vlad!

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?

Thanks for reading, and check back next week!