May 9, 2017 2017 TCO Algorithm Round 1C Editorials

TCO17 Algorithm Round 1C Editorials are now published! A big thanks to Egor (TCO’12 Algorithm Champion) for writing the editorials. You may discuss the problems in the match discussion forum.
Round 1C ended up with some more familiar faces that are semi-retired from SRM scene dominating the leaderboard. This time around solving 3 problems quickly was not enough, you also had to do some challenges as well. Baz93 won this race with 9 successful challenges while FatalEagle and pieguy trailed with 7 apiece.
2017 TCO Algorithm Round 1C – Division I, Level One EllysTickets
This problem was pretty easy – for each station you just need to calculate how much you are expected to pay if you would buy ticket there unless fined. For i-th station this value is (i * fine + (n – i) * ticketPrice[i]) / n. Now we only need to return minimal such value and to remember that we should never return value bigger than fine – that’s exactly the reason for so many successful challenges. For implementation refer to dj3500 solution.
2017 TCO Algorithm Round 1C – Division I, Level Two EllysWordCoins
This task seems like some kind of problem that require Floyd-Warshall algorithm implementation and then some non-trivial parsing of input. But with one simple observation – if we sum up values of letters for each word each trade’s cost would be just difference of this sums – this problem becomes trivial and we can just ignore available trades as we know that there are some way to trade S for G and we really do not care which one we will use – they all have same cost. So we just need to return cost(G) – cost(S). Refer to poikniok solution for details.
2017 TCO Algorithm Round 1C – Division I, Level Three EllysRPS
Here we need to use meet-in-the-middle – we generate all possible strategies for first half of rounds, calculate for each of them difference between number of wins and loses against every strategy employed by other participant and hence for each possible vector of differences against others we can calculate number of ways we can achieve this vector. Now we only need to do the same with latter half of rounds, match vectors that have opposite values in each position and find sum of products of corresponding values. For implementation details you can check Amylase solution.