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: \mathcal{O}(2^P)

For the second subtask, we can use basic dynamic programming. For each planet, let path(i) be the number of paths to that planet, path(0) = 1. For the i^{th} planet from 0 to D-1, and some other planet j (j > i), path(j) := path(j) + path(i) if planet j can be directly reached from planet i.

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

For the third subtask, we optimize the DP algorithm above by using a suffix sum array (similar to a prefix sum array). Now, redefine path(i) to mean the number of paths from planet i to planet D. Now, path(D) = 1 and we want to find path(0). We now note that for a planet i, if j is the furthest planet that can be reached, path(i) = \sum_{x = i+1}^{j}path(x). This is equal to \sum_{x = i+1}^{D}path(x) - \sum_{x=j+1}^{D}path(x), and the suffix sum array stores both of these values. Note that we should now process planets in reverse order.

Time Complexity: \mathcal{O}(N)


In the case of X=2, define path(i) to mean the number of paths from planet i to planet D. Make sure to code W=0 and W=1 separately because these are corner cases (in subtasks 5 and 6, it is sufficient to solve for W+10^9+7).

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

Complexity of D: \mathcal{O}(W)

First, notice that path(i)=path(i+1)+path(i+2)+\dots+path(i+R_i) and path(D)=1. That means if the array [path(i+1),path(i+2),\dots,path(D)] is known, then path(i) is a prefix sum of this array. It is pointless to have R_i=0 because path(i)=0 fills up valuable space in the array. Given a completed array [path(0),path(1),\dots,path(D)], it is easy to find the amount of fuel from each location (including the starting location) using a naive \mathcal{O}(\text{total fuel}) algorithm. To solve X=2, construct this array so that the first element is W.

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

In total, D < 64\,000.

Complexity of D: \mathcal{O}(\sqrt{W}), and 30\,000 is chosen because \sqrt{10^9+7} \approx 30\,000

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 X=2 with D=32.


Comments


  • 6
    anishmahto  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: O(logW)

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

    2^n, ... 8, 4, 2, 1, 1

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

    To accommodate for odd numbers, we need to have a sufficient amount of planets at the end of the sequence with simply 1 distinct path - because 1 plus an even number equals an odd number. Take W=27 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 1. Second, each planet i has paths floor(paths[i - 1]/2) except for the first (which should have W distinct paths). Third, everytime paths[i - 1], is an odd number, we create another planet at the end of the list (before ending destination) with a distinct path of 1. Fourth, if a planet should have an odd number of paths and is not equal to 1, its fuel equals the fuel of the planet ahead of it plus 2. Otherwise it should have the fuel of the planet ahead of it, plus 1.

    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 W, and keep dividing it by 2. If the current value of W happens to be odd, then we subtract 1 first and add a planet with 1 distinct path at the end of our list. We also must remember that this is planet i, and that it should have either fuel[i + 1] + 1 or fuel[i + 1] + 2 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 W=0 and that planet end - 1 as well as planet end always has 1 distinct path. Oh, if you didn't know, assuming planet i + 1 has 1 distinct path, then planet i can also have 1 distinct path by giving it 1 fuel.