Editorial for TLE '16 Contest 6 (Mock CCC) S3 - Hyper Fax

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: d

In this editorial, the -x direction refers to the left, and the +x direction refers to the right. It is assumed that the programmer has already sorted the neighbours from left to right, which takes \mathcal{O}(N \log N) time.

For the first subtask, it is optimal for Fax to travel only to the right (which is right, according to William), while eating all of the pies along the way. Remember that the remaining distance is not replaced when eating a pie; rather, sugar is added onto the remaining distance. Fax will stop being hyper when the remaining distance reaches 0.

Time complexity: \mathcal{O}(N \log N)

The second subtask is troll.

For the third subtask, it is possible to generate all (N-1)! possible ways (permutations) that Fax can visit the neighbours. Afterwards, calculate the total distance that Fax can run when following this permutation, which takes \mathcal{O}(N) time. The answer is the maximum total distance among these permutations.

Time complexity: \mathcal{O}(N!)

For the fourth subtask, it is a bad strategy to skip over a neighbour and not eat the pie. So, when given the optimal route, Fax will go to the closest neighbour at the left/right side (only 2 choices!), and eat their pie. Then, only the combination of left/right will matter. Calculate the distance that Fax will travel if he follows a specific combination of left/right.

Time complexity: \mathcal{O}(N \times 2^N)

For the fifth subtask, the idea for the fourth subtask can be used. Instead of checking every single possible combination, dynamic programming can be used. A state can be represented by 3 things: the left end of Fax's eating spree, the right end of Fax's eating spree, Fax is at the left/right end (2 choices!) of the defined range. Each of these \mathcal{O}(N^2) states will contain the maximum remaining distance that Fax can travel.

After performing some dynamic programming to fill out the table, it is helpful to know the maximum distance that Fax can travel. If Fax ate all of the pies in the range [u,v], the total distance is the sum of sugars from the u^{th} pie to the v^{th} pie. Each of these can be solved in \mathcal{O}(1) with a prefix sum array.

Time complexity: \mathcal{O}(N^2)


There are no comments at the moment.