Editorial for TLE '17 Contest 1 P2 - Willson and Food


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: ZQFMGB12

We first want to associate each of the F food types to its energy value. We can use a map or we can simply use an array of strings and energy values, preserving their order.

Next, we sort the N food items since Willson must visit them in increasing order of distance. We keep track of Willson's total energy as we iterate through the food items. Note that when arriving at food item j, Willson must have had at least enough energy to walk d_j meters, so we can simply check if Willson's current energy is at least d_j, since he requires 1 unit of energy per meter. We can get the energy value of food item j by using the map or by iterating through the string array to find the correct index of the food item's type.

However, we must be careful if there is more than one item with the same distance. In particular, there could be a food item that drains a lot of energy followed by a food item that gives a lot of energy. If Willson eats the former first, his energy could become 0 or negative. However, it is still possible for him to eat the second food item, restoring his energy to a positive value. In this case, Willson should not stop eating after he eats the first food item. A solution that did not make this consideration would have received 30\% of the points.

Time Complexity: \mathcal{O}(N \log F) or \mathcal{O}(NF) if a data structure such as a map is not used.


Comments

There are no comments at the moment.