2017 TCO Algorithm Round 1C Editorials

May 9, 2017 Harshit Mehta

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.

The post 2017 TCO Algorithm Round 1C Editorials appeared first on Topcoder.

Previous Article
Project Managers, Designers, Jack of all Trades – Topcoder Copilots: Part 2
Project Managers, Designers, Jack of all Trades – Topcoder Copilots: Part 2

We were so excited to interview some of our amazing Design Copilots for Design Month that we couldn’t fit a...

Next Article
ITMO University Hosts TCO17 Russia Regionals
ITMO University Hosts TCO17 Russia Regionals

This post was cowritten by gorbunov and hmehta. The St. Petersburg regional event took place on Sunday, May...