A strategic week

The last week started with the middle-of-the-night SRM 682 on Tuesday (problems, results, top 5 on the left). Continuing the recent trend, the hardest problem did not crack, and the winner was decided during the challenge phase, where subscriber has squeezed the victory - congratulations!

The week ended with two contests on Sunday: first, the Open Cup Grand Prix of Bashkortostan catered to the team contest lovers (results, top 5 on the left). Past Glory team was unstoppable once again, making just one incorrect attempt over 12 solved problems!

Problem F's statement is so short that I'll quote it verbatim: "For each vertice of given undirected weighted graph calculate the length of shortest simple cycle, which contains this vertice". The graph had 300 vertices. Is this a textbook problem?

And finally, Codeforces hosted the Final Round of 8VC Venture Cup 2016 for those who prefer to compete on their own (problems, results, top 5 on the left). The round had a $2500 prize for the first place, which tourist has won convincingly thanks to some super fast problem solving - great job!

My story in this round is all about strategy and tactics. Having solved problem A, I've read the statement for problem B first, which looked quite tedious, so I've decided to check other problems. Having read problem C, I've realized that it's a well-known problem which I don't remember the solution to, so solving it at this point would put me at a disadvantage. Finally, problem D also looked tedious but at least brought 2x more points than problem B.

I've glanced at the scoreboard at this point, and it turned out that tourist has already submitted B. It was pretty obvious at this point that following his strategy would not give me a win, since he was quite a bit ahead in time, so in order to win I needed a different strategy, so I've decided to implement D, then E, and then attempted F. My hope when starting F with almost 1 hour to go was to solve it, and then come back to either B or C, while tourist would not be able to finish F in time because he'd spend a lot of time on A-E.

My prediction about tourist's result turned out to be correct, but I couldn't execute on my strategy - problem F did not crack in 1 hour :( After the contest, I required 20-30 more minutes to get my solution to work.

Here's the tricky problem: you are given a tree with n nodes, one of the nodes being empty and other nodes containing all numbers between 1 and n-1 exactly once. One is allowed to add at most one arbitrary edge to the tree, and then move the numbers along the resulting graph, where at each move we can move a number to an adjacent empty node, and the goal is to reach the given ending state from the given starting state in the least number of moves. Implementation details aside, can you find the algorithmic solution in 1 hour?

I hope I won't need to rely on unusual strategies in today's Hacker Cup final round, which starts in less than 2 hours :) There should be at least a scoreboard, and maybe more live coverage at the competition page.

Tweet