A week with randomized travel

Quite unusually, this week had two Codeforces rounds. The first one, Codeforces Round 309, took place on Wednesday (problems, results, top 5 on the left). Congratulations to ecnerwal for his second Codeforces victory! The scoreboard is a bit unusual, too, as all successful submissions for the top 5 happened within the first hour, highlighting the huge gap in difficulty between problem E and the rest. I haven't solved it myself yet, but the problem statement looks interesting: you're given a graph with 50 vertices and 100 edges, where each edge has a cost and a travel time associated with it, and the travel time is actually a random value: you're given the probabilities that it's equal to 1, 2, .., t (t <= 20000). You need to get from vertex A to vertex B, and if you spend more than t time doing that, you pay an additional constant penalty. How do you minimize the expected payment for getting from A to B?

Codeforces Round 310 happened on Saturday (problems, results, top 5 on the left). The problems were more tractable this time, and the order of solving them played the key role - congratulations to Borys on getting that right and claiming the first place!

Challenge24 finals in Budapest covered both Saturday and Sunday (results, top 5 on the left). There is little information available right now, but the final scoreboard is, and team HoChockiGon is the winner, overtaking the last year's champions PrecisionScrewdrivers in Sunday's morning hours - nice push!

Last week I mentioned the nice problem H2 from the IPSC: you're given an undirected graph, and need to color its vertices into red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices.

The key idea is: it turns out that the problem is equivalent to finding a subset of vertices with total degree as close to half of the total degree of all vertices as possible! Having made this observation, the rest is very straightforward dynamic programming.

Thanks for reading, and check back next week!

Tweet