Editorial for TLE '16 Contest 8 P4 - Delivery Service - Olympiads Online Judge

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

For the second subtask, we can use basic dynamic programming. For each planet, let $path(i)$ $p a t h (i)$ be the number of paths to that planet, $path(0) = 1$ $p a t h (0) = 1$ . For the $i^{th}$ $i^{t h}$ 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)$ $p a t h (j) := p a t h (j) + p a t h (i)$ if planet $j$ $j$ can be directly reached from planet $i$ $i$ .

Time Complexity: $\mathcal{O}(N^2)$ $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)$ $p a t h (i)$ to mean the number of paths from planet $i$ $i$ to planet $D$ $D$ . Now, $path(D) = 1$ $p a t h (D) = 1$ and we want to find $path(0)$ $p a t h (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)$ $p a t h (i) = \sum_{x = i + 1}^{j} p a t h (x)$ . This is equal to $\sum_{x=i+1}^D path(x) - \sum_{x=j+1}^D path(x)$ $\sum_{x = i + 1}^{D} p a t h (x) - \sum_{x = j + 1}^{D} p a t h (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)$ $O (N)$

In the case of $X=2$ $X = 2$ , define $path(i)$ $p a t h (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$ $p a t h (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)$ $O (W)$

First, notice that $path(i) = path(i+1)+path(i+2)+\dots+path(i+R_i)$ $p a t h (i) = p a t h (i + 1) + p a t h (i + 2) + \dots + p a t h (i + R_{i})$ and $path(D) = 1$ $p a t h (D) = 1$ . That means if the array $[path(i+1), path(i+2), \dots, path(D)]$ $[p a t h (i + 1), p a t h (i + 2), \dots, p a t h (D)]$ is known, then $path(i)$ $p a t h (i)$ is a prefix sum of this array. It is pointless to have $R_i = 0$ $R_{i} = 0$ because $path(i) = 0$ $p a t h (i) = 0$ fills up valuable space in the array. Given a completed array $[path(0), path(1), \dots, path(D)]$ $[p a t h (0), p a t h (1), \dots, p a t h (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})$ $O (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 \leq 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})$ $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)$ $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)$ $f l o o r (p a t h s [i - 1] / 2)$ except for the first (which should have $W$ $W$ distinct paths). Third, everytime $paths[i - 1]$ $p a t h s [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$ $f u e l [i + 1] + 1$ or $fuel[i + 1] + 2$ $f u e l [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$ $e n d - 1$ as well as planet $end$ $e n d$ 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.