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

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

Time Complexity: $\mathcal{O}(N^2)$ ~\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)$ ~path(i)~ to mean the number of paths from planet $i$ ~i~ to planet $D$ ~D~. Now, $path(D) = 1$ ~path(D) = 1~ and we want to find $path(0)$ ~path(0)~. We now note that for a planet $i$ ~i~, if $j$ ~j~ is the furthest planet that can be reached, $path(i) = \sum_{x=i+1}^j path(x)$ ~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)$ ~\mathcal{O}(N)~

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

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

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

First, notice that $path(i) = path(i+1)+path(i+2)+\dots+path(i+R_i)$ and $path(D) = 1$ ~path(D) = 1~. That means if the array $[path(i+1), path(i+2), \dots, path(D)]$ is known, then $path(i)$ ~path(i)~ is a prefix sum of this array. It is pointless to have $R_i = 0$ ~R_i = 0~ because $path(i) = 0$ ~path(i) = 0~ fills up valuable space in the array. Given a completed array $[path(0), path(1), \dots, path(D)]$ ~[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})$ ~\mathcal{O}(\text{total fuel})~ algorithm. To solve $X=2$ ~X=2~, construct this array so that the first element is $W$ ~W~.

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

In total, $D < 64\,000$ ~D < 64\,000~.

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

d is too lazy to finish the editorial for subtask 6, and has forgotten what the solution was.

Bonus Challenge: Try to solve $X=2$ ~X=2~ with $D=32$ ~D=32~.

Comments

8

anishmahto commented on April 25, 2017, 8:36 p.m. ← edit 2 →

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: $\mathcal{O}(\log W)$ ~\mathcal{O}(\log W)~

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

$2^n, \dots, 8, 4, 2, 1, 1$ ~2^n, \dots, 8, 4, 2, 1, 1~

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

To accommodate for odd numbers, we need to have a sufficient amount of planets at the end of the sequence with simply $1$ ~1~ distinct path - because $1$ ~1~ plus an even number equals an odd number. Take $W=27$ ~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$ ~1~. Second, each planet $i$ ~i~ has paths $floor(paths[i - 1]/2)$ ~floor(paths[i - 1]/2)~ except for the first (which should have $W$ ~W~ distinct paths). Third, everytime $paths[i - 1]$ ~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$ ~1~. Fourth, if a planet should have an odd number of paths and is not equal to $1$ ~1~, its fuel equals the fuel of the planet ahead of it plus $2$ ~2~. Otherwise it should have the fuel of the planet ahead of it, plus $1$ ~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$ ~W~, and keep dividing it by $2$ ~2~. If the current value of $W$ ~W~ happens to be odd, then we subtract $1$ ~1~ first and add a planet with $1$ ~1~ distinct path at the end of our list. We also must remember that this is planet $i$ ~i~, and that it should have either $fuel[i + 1] + 1$ ~fuel[i + 1] + 1~ or $fuel[i + 1] + 2$ ~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$ ~W=0~ and that planet $end - 1$ ~end - 1~ as well as planet $end$ ~end~ always has $1$ ~1~ distinct path. Oh, if you didn't know, assuming planet $i + 1$ ~i + 1~ has $1$ ~1~ distinct path, then planet $i$ ~i~ can also have $1$ ~1~ distinct path by giving it $1$ ~1~ fuel.