July 25, 2017 2017 TCO Algorithm Round 2C Editorials

TCO17Algorithm Round 2C Editorials are now published. Once again thanks to Egor for the editorial and overview of TCO17 Algorithm Round 2C.
With completion of round 2C we now know all 120 participants of round 3. kraskevich was the only one to solve all 3 problems, trailed by Deretin and tomekkulczynski. rng_58 claimed victory in parallel round. Congratulations to all those who qualified.
 
2017 TCO Algorithm Round 2C – Division I, Level One  – CanidsSeesaw
Here we have wolves and foxes who are playing on a seesaw. They are getting on it one wolf and one fox at a time and foxes score a point whenever their side is heavier. We know the order in which wolves are seated, can we produce an order of foxes so that they score exactly k points?
It is easy to see that of foxes wanted to score most points they should sit in decreasing order of weights, and if they wanted least number of points – in increasing order. Hence if k falls outside this values there are no order requested in the problem. Also if 2 consecutive foxes in order are swapped score will change by no more than 1. Hence we start with increasing order and exchange foxes until we either get score of k or would reach decreasing order (in which case there are no solution). Refer to ACRush’s solution for details.
 
2017 TCO Algorithm Round 2C – Division I, Level Two   – AngelDemonGame
Given a graph with N vertices angel and demon nominate some pairs of vertices simultaneously (at most A by angel, at most D by demon), then edges between angel’s pairs of vertices added to graph and then edges between demon’s pairs removed. If there is path from 0 to N – 1 in resulting graph angel wins, otherwise demon wins.
First if D >= N – 1 then he wins – he would just nominate all edges from 0. Otherwise he can’t guarantee win as he can’t remove an edge from each path of length at most 2 from 0 to N – 1 and as A >= 2 angel can add any such path.
Angel would win for sure if he can add at most A edges so that flow from 0 to N – 1 in resulting graph is at least D + 1. There are 2 ways to check this condition. First we can find minimal cost of flow of size D + 1 in full graph where edge costs 0 if it present in original graph and 1 otherwise. For example of this approach you can go to PaulJefferys’s solution.
Also one can notice that if current flow between 0 and N – 1 is F and there are O outgoing edges from 0 and I incoming edges to N – 1 (we would disregard edge from 0 to N – 1 here) then we can increase flow by 1 with first O + I – F added edges and then we would need to add 2 edges per one flow increment. Petr’s solution illustrate this approach.
 
2017 TCO Algorithm Round 2C – Division I, Level Three  – TreasureOfWinedag
In this problem we are given string str and number K and we need to subdivide str into K strings with minimal total cost, where cost of substring is number of distinct letters in it.
Suppose length of str was small enough. Then we can just do a dynamic solution with state d(i = prefix of str processed so far, j = number of parts it subdivided into). It is easy to see that d(i, j) – j >= 0 and d(i, j) – j < 26 (as we can always take j – 1 parts of size 1 and 1 part of size i – j + 1, and no part can cost more than 26). Hence we would use f(i, k) instead which is minimal j such that d(i, j) – j <= k. Here we have 26 * length(str) states and each state is processed in 26 operations. For implementation details see ainu7’s solution.