We has a N (N <= 10^5) position and 2 car on shaft number (from 0 to 10^9). Initially 2 cars in 2 positions different on the shaft number. Mission is each position in N position has been visited by only 1 in 2 car and visited by ordered 1, 2, 3, .. N. We have a lot of way. But we need find one way has max distance of car 1 and car 2 all time is minimum. Print minimum distance.
Input:
First line has N, pos of car 1, pos of car 2
Second line has N position
Example:
Inp
Out
Note
Thanks! <3
Here's my thought.
Consider DP. We define $$$dp[i]$$$ as the minimal maximum distance of the two cars if one car is at position $$$i$$$ and the other is at some position before $$$i$$$.
Our goal is to calculate $$$dp[n]$$$ and this is the answer. We calculate $$$dp[1]$$$ to $$$dp[n]$$$ one by one.
Let the $$$i$$$-th position is $$$p[i]$$$. Now we have the transfer $$$dp[i] = \min_{j=1}^{i-1}\max(dp[j], \max_{k=j+1}^{i}(|p[j]-p[k]|))$$$, and don't forget to transfer from the initial positions just like this.
We can easily gat $$$\max_{k=j+1}^{i}(|p[j]-p[k]|) = \max(|\max_{k=j+1}^{i}(p[k])-p[j]|, |\min_{k=j+1}^{i}(p[k])-p[j]|)$$$ with some data structure in $$$O(1)$$$.
Using brute force on $$$j$$$ will obviously get TL so we should use faster algorithm. Consider binary search. You can find that when $$$j$$$ is increasing, $$$dp[j]$$$ is non-decreasing and $$$\max_{k=j+1}^{i}(|p[j]-p[k]|)$$$ is non-increasing. So binary search will work.
The total time complexity is $$$O(n\log_2n)$$$.
I realize that there's something wrong if I use $$$dp[0]$$$ and $$$dp[-1]$$$. Since the initial positions has no order, it will get wrong answer during transfer. We can transfer from the initial positions out of the binary search.
UPD: the mistakes have been corrected.
My program passes the example.
Code:
UPD: Mistake is corrected.
Thanks <3333333! but it's not working properly. Here's the link to the original problem d4^yn4`y. You can have a look.
Oh, it's my bad. The binary search has something wrong.
Previous code:
It should be:
Sorry.
But it still wrong
The previous solution is wrong. Solution below is the correct one, and my code got AC.
We should maintain a set of positions during DP.
First, we should do binary search on the answer. So we should ensure that for a given distance $$$m$$$, whether it is possible to find one way to move that the distance of the two cars never exceeds $$$m$$$.
Let $$$dp[i]$$$ be the set of available positions of one car when the other car is at the $$$i$$$-th position. For example, if the positions are $$$[7,5,2,6]$$$ and $$$m=3$$$, the initial positions are $$$x_1=3,x_2=4$$$, we will have:
If $$$dp[i]$$$ is never empty during the whole process, then $$$m$$$ is a possible answer. This way, the time complexity is $$$O(\log_2n(n^2+n\log_2n))$$$. Note that we transfer every element from $$$dp[i-1]$$$ to get $$$dp[i]$$$ and to copy the set is very slow.
In order to avoid copy the whole set, we should edit on the set directly. We should delete all of the elements that is too far from $$$p_i$$$, and check if the distance between $$$p_{i-1}$$$ and $$$p_i$$$ is no greater than $$$m$$$. It will be easier to understand after reading the code.
The total time complexity is $$$O(n\log_2^2n)$$$.
Code:
You so cool. I got understand. Thank you so much! <3