Editorial for Yet Another Contest 2 P6 - Travel Budget - Olympiads Online Judge

Editorial for Yet Another Contest 2 P6 - Travel Budget

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

Subtask 1

Clearly, it is optimal to always go east. We can use dynamic programming to solve this problem.

Define $dp[i]$ $d p [i]$ as the minimum cost to reach the $N$ $N$ -th town from the $i$ $i$ -th town, assuming that we will start by using the $i$ $i$ -th car.

Then, we can loop over all possible towns $j$ $j$ in which we will switch from the $i$ $i$ -th car to the $j$ $j$ -th car. Then, we will update $dp[i]$ $d p [i]$ as $\min(dp[i], dp[j]+(p_j-p_i) \times c_i + d_i)$ $min (d p [i], d p [j] + (p_{j} - p_{i}) \times c_{i} + d_{i})$ . Make sure to only consider feasible values of $j$ $j$ , where $p_j-p_i \le s_i$ $p_{j} - p_{i} \leq s_{i}$ .

The base case is $dp[N] = 0$ $d p [N] = 0$ , and the answer to the problem is $dp[1]$ $d p [1]$ .

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

Subtask 2

Let's try to optimise our dp transition from before. Since $s_i = 10^9$ $s_{i} = 10^{9}$ for all $1 \le i \le N$ $1 \leq i \leq N$ , we do not need to consider which towns are reachable using the $i$ $i$ -th car.

Recall that $dp[i] = \min_{j > i} (dp[j]+(p_j-p_i) \times c_i + d_i)$ $d p [i] = min_{j > i} (d p [j] + (p_{j} - p_{i}) \times c_{i} + d_{i})$ .

We can rewrite this as $dp[i] = d_i - p_i \times c_i + \min_{j > i} (dp[j]+p_j \times c_i)$ $d p [i] = d_{i} - p_{i} \times c_{i} + min_{j > i} (d p [j] + p_{j} \times c_{i})$ .

If we compute our dp bottom-up, then we can optimise our transition using the convex hull trick. This is because we are essentially keeping a set of lines in the form $y = mx + b$ $y = m x + b$ , and to calculate $dp[i]$ $d p [i]$ , we find the line in our set which minimises the value of $m \times c_i + b$ $m \times c_{i} + b$ . Once we compute $dp[i]$ $d p [i]$ , we add the line $y = p_i \times x + dp[i]$ $y = p_{i} \times x + d p [i]$ into our set.

Note that we are not guaranteed that the gradients of the lines we insert are in non-increasing order. Thus, we require the dynamic implementation of the convex hull trick.

Alternatively, we can optimise our dp using the same method using a Li Chao Tree.

Time complexity: $\mathcal{O}(N \log N)$ $O (N \log N)$

Subtask 3

Observe that the restriction on the maximum distance that a car can travel means that when calculating $dp[i]$ $d p [i]$ , we can only consider a contiguous range of possible lines. This range can be easily found using a binary search.

To determine the minimum of any given range of lines, we can create a segment tree, where each node stores its own convex hull trick data structure or Li Chao Tree.

Time complexity: $\mathcal{O}(N \log^2 N)$ $O (N \log^{2} N)$

Comments

There are no comments at the moment.