Editorial for TLE '16 Contest 8 P4 - Delivery Service

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

For the first subtask, we can use recursion to brute force the number of possible paths.

Time Complexity:

For the second subtask, we can use basic dynamic programming. For each planet, let be the number of paths to that planet, . For the planet from to , and some other planet , if planet can be directly reached from planet .

Time Complexity:

For the third subtask, we optimize the DP algorithm above by using a suffix sum array (similar to a prefix sum array). Now, redefine to mean the number of paths from planet to planet . Now, and we want to find . We now note that for a planet , if is the furthest planet that can be reached, . This is equal to , and the suffix sum array stores both of these values. Note that we should now process planets in reverse order.

Time Complexity:

In the case of , define to mean the number of paths from planet to planet . Make sure to code and separately because these are corner cases (in subtasks 5 and 6, it is sufficient to solve for ).

For the fourth subtask, notice that is relatively small. It is enough to have planets where every non-starting planet has exactly path to the end, or . Next, let Fax initially have units of fuel. Now Fax can first choose any of the planets and for each of these choices, there is way to go to the end.

Complexity of :

First, notice that and . That means if the array is known, then is a prefix sum of this array. It is pointless to have because fills up valuable space in the array. Given a completed array , it is easy to find the amount of fuel from each location (including the starting location) using a naive algorithm. To solve , construct this array so that the first element is .

For the fifth subtask, notice that the allowed is quite large. If , refer to subtask 4. Otherwise, construct the array so that it contains elements which are all 's. Then add the element to the array since is a possible prefix sum. While the sum of the elements in the array is less than , keep adding another . Once the sum of the elements in the array is at least , can be constructed. All of the 's are necessary to get , along with some of the 's. After this array is complete (the first element is ), the planet's fuels can be calculated in some other step.

In total, .

Complexity of : , and is chosen because

d is too lazy to finish the editorial for subtask 6. If you want an editorial, please bug him via the DMOJ slack.

Bonus Challenge: Try to solve with .

• commented on April 25, 2017, 4:36 p.m. edited

Edit: Full Points [Unofficial] Editorial The following solution works for subtasks 4, 5, AND 6. It also uses a completely different idea than what I had before. You can read the older version for your own amusement.

Time Complexity:

Understand that we can always double the number of distinct paths starting at path , at a new planet (we traverse the planets backward, like in the official solution). So, if is a power of , we can easily set up planets in the following sequence:

(This works as the fuel at planet is enough to reach all planets ahead of itself.) Notice that we can build this solution by starting with , and dividing by continuously until we reach , if . But, we cannot do so if is not a power of . This is because if we kept dividing by , we would eventually reach an odd number before we reach .

To accommodate for odd numbers, we need to have a sufficient amount of planets at the end of the sequence with simply distinct path - because plus an even number equals an odd number. Take for example.

Planet: 0 1 2 3 4 5 6 7 Paths: 27, 13, 6, 3, 2, 1, 1, 1
Fuel: 7, 5, 3, 2, 2, 1, 1, 0 (planet 7 is the end, thus has 0 fuel)

There are several things to notice from this example. First, the end planet and the second last planet will always have a distinct number of paths equal to . Second, each planet has paths except for the first (which should have distinct paths). Third, everytime , is an odd number, we create another planet at the end of the list (before ending destination) with a distinct path of . Fourth, if a planet should have an odd number of paths and is not equal to , its fuel equals the fuel of the planet ahead of it plus . Otherwise it should have the fuel of the planet ahead of it, plus .

It is left to the reader to determine why the statements/patterns above are true, cause I am too lazy to explain. Once all this is understood, the code is fairly simple. All we do is start with , and keep dividing it by . If the current value of happens to be odd, then we subtract first and add a planet with distinct path at the end of our list. We also must remember that this is planet , and that it should have either or if it's even or odd, respectively. One way to store this is with a vector of pairs.

Finally, be aware of the edge case of and that planet as well as planet always has distinct path. Oh, if you didn't know, assuming planet has distinct path, then planet can also have distinct path by giving it fuel.