September 18, 2017 2017 TCO Algorithm Wild Card Round

TCO17 Algorithm Wild Card Round Editorials are now published. Once again thanks to Egor for the editorial and overview of  the wild card round.
Overview
Last 2 tickets to TCO onsite in Buffalo were up for grabs in Wildcard round for those people who qualified from regional rounds all around the world. kuniavski and xudyh took those two spots, congratulations!
 
2017 TCO Algorithm Regional Wildcard – Division I, Level One  – ArmorUp
In this problem you have an opponent with given current hit points and maximal hit points. Opponent’s armor is half of his lost hit points percentage. What is the minimal strength of hit that will kill this enemy in k swings?
There are 2 ways to solve this problem – you can either come up with formula (which is 2 * maxHP * (1 – (maxHP / (maxHP + currentHP)) ^ (1 / k))) or you can use binary search on answer and calculate if you would kill opponent with given strength. k could be up to a billion, so you can’t just simulate hits, you have to use formula in this case as well.
For former approach you can see Petr’s implementation, for latter – ACRush’s
2017 TCO Algorithm Regional Wildcard – Division I, Level Two  – SixDegreesOfSeparation
Given connected graph with n vertices add at most n / 3 edges so that any 2 vertices are connected by path with length no more than 6.
Let’s take any spanning tree in a graph (for example DFS tree from vertex 0) and categorize all vertices based on remainder by modulo 3 of distance from vertex 0 in this tree. Now we take category with least number of vertices in it and connect all those vertices to vertex 0 (if there is no edge from given vertex to 0 in original graph). Smallest category contains no more than n / 3 vertices, so we will fit into limit on the number of edges. It is easy to see that any 2 vertices are now connected by path no longer then 6.
For implementation details you can read Eryx’s solution.
2017 TCO Algorithm Regional Wildcard – Division I, Level Three  – DayAndNight
Here we are given n attractions, for each attraction we know price of visiting it at day and at night, we have several conditions in the form that we should visit attraction a before attraction b and also there is a cost each time you visit attraction at day after visiting previous one at night and vice versa. What is the minimal cost of visiting all attraction in order respecting all conditions?
Suppose we know how many day to night and night to day changes we would do in our solution and we also know if we start at day or at night. Now we can say we would have k periods (some are day periods, some are night periods, no 2 consecutive periods are of the same type) and we would build a graph of size n * k + 2. For each period and each attraction we would have an edge of capacity equal to either day cost or night cost of this attraction that goes either to the next period of same attraction or, if this is last period, to special vertex t. Also for each pair (a, b) of attractions where a should be visited before b we would have edge of infinite capacity between vertices corresponding to a and some period and b and the same period. Additionally we would have edges of infinite capacity between special vertex s and all vertices corresponding to the first period. Now minimal cut between s and t corresponds to some way of dividing attraction between periods (as we had to cut one edge on each path of vertices corresponding to the same attraction) and if we assign vertex a of some condition to later period than vertex b of the same condition there would still be path from s to t. So we need to find minimal cut in this graph, which equals to maximal flow. Now we need to add costs of switching between periods and we have optimal answer for given number of periods starting at given state. There would never be more periods than there are attractions, so we would have to run our max flow algorithm at most 2n times
kuniavski’s solution illustrates this approach.