Wednesday, November 13, 2019

A week that blows minds

TopCoder SRM 763 has started the Jul 15 - Jul 21 competitive week (problems, results, top 5 on the left, analysis). ecnerwal has won the round, bringing his TCO point total for this stage to the respectable 4n, and thus qualifying for the onsite finals which takes place this week in Houston. Congratulations!

With the list of Round 4 and onsite qualifiers through the stage system decided, TopCoder Open 2019 Round 3B a day later offered the last chance to advance for many (problems, results, top 5 on the left, parallel round results). Only rickytheta was able to solve the hard problem successfully, even though their solution looks deceptively short. Congratulations on the well-deserved victory!

Codeforces Global Round 4 took place on Saturday (problems, results, top 5 on the left, analysis). ainta was 10 minutes faster than his competitors, but his 7 incorrect attempts on pretests meant that Radewoosh was still very close. ainta ended up in first place anyway, but Radewoosh has proven his point as well by "up-hacking" ainta's solution for G a few hours later. Well done to both!

AtCoder Grand Contest 036 was the last round of the week (problems, results, top 5 on the left, analysis). Um_nik was very fast in solving five out of six problems, but got stuck in the sixth, allowing snuke to overtake him with a couple of minutes remaining. Congratulations on the win!

Problem D received quite some praise: consider a complete directed graph on n vertices (n<=500), with the cost of the arc from i to j (i  j) equal to -1 if i < j, and to 1 if i > j. Let's add n-1 more arcs with weight 0, going from i to i+1 to each i (those arcs will be parallel to the corresponding -1 arcs). For each arc with weight -1 or 1 we are given the cost of removing it from the graph, and arcs with weight 0 are not removable. What is the minimum total cost to remove some arcs in such a way that there are no cycles of negative weight remaining?

Quite unusually for this blog, I don't know the solution at the time of posting this, so I'm looking forward to trying to solve it myself!

Thanks for reading, and check back for the solution discussion!

1 comment: