Crossing the Railways
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3500
Tags: data structures, dp

Isona is in a train station. This station has two platforms, and between them there are $$$m$$$ parallel railways that can be viewed as infinite straight lines. Each railway is identified with an integer from $$$1$$$ to $$$m$$$, railway $$$1$$$ being the closest to the first platform and railway $$$m$$$ being the farthest. There is a $$$1$$$ meter distance between consecutive railways, as well as between each platform and its closest railway.

Isona is standing on the inner border of the first platform, when she realizes that she forgot to validate her ticket! There is a validating machine on the second platform, exactly opposite her current position (thus, the distance between Isona and the validating machine is $$$m + 1$$$ meters). There are only $$$s$$$ seconds left to validate the ticket and the bridge designated to cross the railways is too far from the validating machine. Therefore, Isona (who is very brave and a little bit careless) will cross the railways running in a straight line perpendicular to the railways themselves. Isona can only run forward (not backward) and she can stay still. When she runs at maximum speed, she needs $$$v$$$ seconds to traverse $$$1$$$ meter. She can run at any speed less than or equal to her maximum speed.

There is only one problem: $$$n$$$ trains are programmed to transit through the railways. The $$$i$$$-th train will use the railway $$$r_i$$$. It will start crossing the straight line between Isona and the validating machine $$$a_i$$$ seconds from now and it will end $$$b_i$$$ seconds from now. Of course, Isona cannot cross a railway when a train is passing. Formally, for every $$$i = 1, \, 2, \, \dots, \, n$$$, Isona is not allowed to be on railway $$$r_i$$$ at any time $$$t$$$ with $$$a_i < t < b_i$$$ (but she is allowed to cross at times $$$a_i$$$ or $$$b_i$$$).

The following picture summarizes the situation. In the picture there are $$$m = 4$$$ railways and two trains are visible; the train going through railway $$$3$$$ is currently crossing the line between Isona and the validating machine.

Isona is a really good runner, but she gets tired every time she has to change her running speed. What is the minimum number of speed changes she has to perform to get to the validating machine on the other platform within $$$s$$$ seconds from now? Note that at the beginning Isona is not running. She can start to run anytime. The instant she starts to run (i.e. her speed becomes positive) is not counted as a speed change.

Input format:
The first line of the input contains four integers $$$n$$$, $$$m$$$, $$$s$$$, $$$v$$$ ($$$1 \leq n \leq 500$$$, $$$1 \leq m \leq 10$$$, $$$1 \leq s, v \leq 10^9$$$) — the number of trains, the number of railways, the maximum time in seconds Isona can spend crossing the railways, and the number of seconds she needs to traverse $$$1$$$ meter at maximum speed.

Each of the next $$$n$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$, $$$r_i$$$ ($$$1 \leq a_i < b_i \leq 10^9$$$, $$$1 \leq r_i \leq m$$$) — the start and end times of the $$$i$$$-th train crossing the straight line between Isona and the validating machine, and the railway it will be using.

It is guaranteed that, for any two trains $$$i$$$ and $$$j$$$ that go through the same railway (i.e. $$$r_i = r_j$$$), there is at least $$$1$$$ second between them (that is, either $$$a_j \ge b_i + 1$$$ or $$$a_i \ge b_j + 1$$$).

Output format:
Print the minimum number of speed changes Isona has to perform to get to the validating machine in time. If this is impossible, print $$$-1$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Note:
In the first sample, if Isona starts running at time $$$t=0$$$ at maximum speed ($$$1$$$ m/s), she will cross each railway just when a train is about to traverse it, and she will arrive at the other platform at time $$$4 = s - 1$$$ without changing speed.

In the second sample, a possible solution with $$$2$$$ speed changes is the following: for the first $$$2$$$ seconds Isona goes at maximum speed ($$$0.5$$$ m/s), then she slows down to $$$0.25$$$ m/s for $$$4$$$ seconds until she reaches the second railway. At that point, she goes at maximum speed again until she reaches the other platform.

In the third sample, Isona can wait $$$2$$$ seconds before starting running. She then runs for $$$5$$$ seconds at maximum speed ($$$0.5$$$ m/s). After that, she waits for $$$1$$$ second not running (or running at $$$0$$$ m/s), and finally she runs again at maximum speed for the last $$$5$$$ seconds. Overall, she changes speed twice.

Example input:
4 3 5 1
1 2 1
3 4 1
2 3 2
3 4 3

Example output:
0

Example input:
3 3 12 2
2 10 1
1 6 2
8 12 3

Example output:
2

Editorial:
First of all, let us transform the given problem to a geometry problem. We consider the plane where the $$$x$$$ coordinate represents the distance of Isona from the first validating machine (remember that Isona is always in the straight segment between the two validating machines), and the $$$y$$$ coordinate represents time.
Thus, the point $$$(a, b)$$$ of the plane corresponds to being $$$a$$$ meters away from the first validating machine after $$$b$$$ seconds. If we represent trains in this plane they are vertical segments from $$$(r_i,a_i)$$$ to $$$(r_i,b_i)$$$.
Let us look at how is represented the fact that Isona is $$$m_j$$$ meters away from the validating machine and starts moving at constant speed $$$v_j$$$ at time $$$t_j$$$, and does so for $$$s_j$$$ seconds. We get a straight segment with endpoints $$$(m_j,t_j)$$$ and $$$(m_j+v_j \cdot s_j,\, t_j + s_j)$$$.
So, the movement of Isona at constant speed for a period of time is represented by a straight segment.
The constraint on the speed of isona corresponds to a constraint on the slope of the segment. Let us suppose that a segment passes through the points $$$(m_1,t_1)$$$ and $$$(m_2,t_2)$$$ with $$$t_1 < t_2$$$. Since Isona cannot run backward, it must hold $$$m_1 \le m_2$$$. Isona's constant speed is $$$v_I = \frac{m_2-m_1}{t_2-t_1}$$$. From the statement we know that $$$\frac{1}{v} \geq v_I \geq 0$$$, so we can write $$$\frac{t_2-t_1}{m_2-m_1} \geq v$$$. That means that the slope of the segment must be greater or equal then $$$v$$$.
From now on we will consider a segment to be valid if it does not cross any train segment (take into account that train segments are open, so the endpoints are not considered part of the segment) and has a valid slope (that is $$$m_1 = m_2$$$ or $$$\frac{t_2-t_1}{m_2-m_1} \geq v$$$).
The problem is equivalent to finding the minimum number of segments that constitute a path from $$$x=0$$$ to $$$x=m+1$$$ that does not intersect any train segment. This statement is similar to a BFS where the nodes are the valid segments and the edges the intersection points. The source node is the segment $$$(0,0)-(0,s)$$$ and the target node is $$$(m+1,0)-(m+1,s)$$$. The issue is that we have infinitely many valid segments. The following lemma allows us to consider only finitely many segments.
Lemma. A special segment is a valid segment such that at least one of the following holds:
• It contains $$$(0, 0)$$$ and has slope equal to $$$v$$$.
• It contains the upper endpoint of a train (i.e., $$$(r_i, b_i)$$$) and has slope equal to $$$v$$$.
• It contains two points $$$(r_i, a_i)$$$ and $$$(r_j, b_j)$$$ with $$$r_i < r_j$$$.
From the previous lemma we see that we only need to consider $$$O(n^2)$$$ segments, and we can construct the full set of segments from the lemma in time $$$O(m \cdot n^2 \cdot \log(n))$$$, as for each valid segment we only need to check if it crosses any train segment, which can be done using binary search in each rail in total time $$$O(m \cdot \log(n))$$$.
But there may be $$$O(n^4)$$$ intersection points, so running a BFS on this graph is too slow. So let us see when Isona shall change speed in an optimal solution. She may change speed at a given railway or between two railways. It is never convienient to change speed between the first validating machine and the first railway or between the last railway and the second validating machine.
Lemma. Any solution using only special segments changes speed at most once between any two railways.
Proof. Any solution changing speed twice between two rails is using a segment which is strictly contained between two railways, hence it cannot be a special segment because, by definition, any special segment has at least one point with coordinate $$$x$$$ that is integer.
With this new observation, we can now proceed to describe an efficient algorithm. For each $$$i=1,\dots,m$$$, and for each segment $$$j$$$, we keep a value $$$d^{(i)}_j$$$ that denotes the minimum number of changes of speed that are necessary to reach this segment, starting from $$$x=0$$$, considering only the region $$$0\le x\le i$$$. If we know $$$d^{(m)}_j$$$ then we know the answer to the problem.
Given $$$d_j^{(i)}$$$ for all segments $$$j$$$, we will efficiently compute $$$d_j^{(i+1)}$$$ for all segments $$$j$$$.
Let us see how to deal with the intersections (the changes of speed) between two railways (or on one railway).
Let us consider all the special segments that intersect both railway $$$i$$$ and railway $$$i+1$$$; these segments will be indexed by an integer $$$j$$$ (from here on, we consider only these segments, as the other ones are not important for the changes that happen between railway $$$i$$$ and railway $$$i+1$$$). Let us identify the $$$j$$$-th segment with a pair of integers $$$(a_j,b_j)$$$ where $$$a_j$$$ and $$$b_j$$$ are the positions that the segment $$$s_j$$$ has if we order the segments by the $$$y$$$ coordinate of the crossing point with $$$x = i$$$ and $$$x = i+1$$$ respectively. From now on we will only use the pair $$$(a_j,b_j)$$$ to work with the segments.
Notice that having the pairs $$$(a_j, b_j)$$$ is sufficient to tell if two segments intersect (taking care of intersections on the railways is a technical detail we skip in this explanation). If we have two segments $$$j, k$$$ with $$$a_j > a_k$$$ and $$$b_j < b_k$$$ it means that they cross. Also if $$$a_j < a_k$$$ and $$$b_j > b_k$$$, then they cross.
For all segments $$$j$$$, it is trivial that $$$d^{(i+1)}_j \le d^{(i)}_j$$$. Moreover, if segment $$$j$$$ and segment $$$k$$$ cross, then necessarly $$$d_j^{(i+1)} < d^{(i)}_k +1$$$. These two observations allow us to compute $$$d_{j}^{(i+1)}$$$, but how can we do it efficiently?
We shall use a Fenwick tree (or a segment tree) to efficiently compute the minimum over an interval.
First, for each $$$j$$$, we consider the crossings such that $$$a_j > a_k$$$ and $$$b_j < b_k$$$. We process them in increasing order of $$$a_j$$$. When processing the $$$j$$$-th segment, we update $$$d^{(i+1)}_j$$$ with the minimum over the interval $$$[b_j + 1, \infty]$$$ (if such value is smaller than the current value of $$$d'_j$$$). Then, we update the Fenwick with the value $$$d^{(i)}_j+1$$$ at position $$$b_j$$$.
The other type of crossings, those such that $$$a_j < a_k$$$ and $$$b_j > b_k$$$, can be processes analogously by considering the segments in increasing order of $$$b_j$$$.
This allow us to process all the crossings between two railways in $$$O(n^2 \cdot \log(n))$$$. So, at the end, the total time complexity is $$$O(m \cdot n^2 \cdot \log(n))$$$.