rb235's blog

By rb235, history, 3 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
3 years ago, # |
Rev. 6   Vote: I like it +1 Vote: I do not like it

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)$$$.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My program passes the example.

    Code:

    #include <bits/stdc++.h>
    
    using namespace std;
    const int N = 1e5 + 5;
    int p[N], lg2[N], st[2][N][20], dp[N];
    
    int main() {
    #ifndef ONLINE_JUDGE
    	freopen("in.txt", "r", stdin);
    #endif
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);
    	cout.tie(nullptr);
    	for (int i = 1; i < N; ++i) lg2[i] = (int) log2(i);
    	int n, x1, x2;
    	cin >> n >> x1 >> x2;
    	for (int i = 1; i <= n; ++i) {
    		cin >> p[i];
    		st[0][i][0] = st[1][i][0] = p[i];
    	}
    	for (int i = 1; i <= 18; ++i) {
    		for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
    			st[0][j][i] = min(st[0][j][i - 1], st[0][j + (1 << (i - 1))][i - 1]);
    			st[1][j][i] = max(st[1][j][i - 1], st[1][j + (1 << (i - 1))][i - 1]);
    		}
    	}
    	for (int i = 1; i <= n; ++i) {
    		dp[i] = max(abs(x1 - x2),
    					min(max(abs(min(st[0][1][lg2[i]], st[0][i - (1 << lg2[i]) + 1][lg2[i]]) - x1),
    							abs(max(st[1][1][lg2[i]], st[1][i - (1 << lg2[i]) + 1][lg2[i]]) - x1)),
    						max(abs(min(st[0][1][lg2[i]], st[0][i - (1 << lg2[i]) + 1][lg2[i]]) - x2),
    							abs(max(st[1][1][lg2[i]], st[1][i - (1 << lg2[i]) + 1][lg2[i]]) - x2))));
    		int l = 1, r = i - 1;
    		while (l <= r) {
    			int m = (l + r) >> 1;
    			int a = dp[m];
    			int b = max(abs(min(st[0][m + 1][lg2[i - m]], st[0][i - (1 << lg2[i - m]) + 1][lg2[i - m]]) - p[m]),
    						abs(max(st[1][m + 1][lg2[i - m]], st[1][i - (1 << lg2[i - m]) + 1][lg2[i - m]]) - p[m]));
    			dp[i] = min(dp[i], max(a, b));
    			if (a == b) break;
    			if (a > b) r = m - 1;
    			else l = m + 1;
    		}
    	}
    	cout << dp[n] << '\n';
    	return 0;
    }
    

    UPD: Mistake is corrected.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks <3333333! but it's not working properly. Here's the link to the original problem d4^yn4`y. You can have a look.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Oh, it's my bad. The binary search has something wrong.

        Previous code:

        if (a > b) l = m + 1;
        else r = m - 1;
        

        It should be:

        if (a > b) r = m - 1;
        else l = m + 1;
        

        Sorry.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          result

          But it still wrong

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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:

  • $$$dp[1]=(4)$$$(there is no $$$3$$$ because $$$|7-3|=4>3$$$),
  • $$$dp[2]=(4,7)$$$(either transfer from $$$dp[1]$$$ and continue moving the car at $$$7$$$, or stop the car at $$$7$$$ and move the other one),
  • $$$dp[3]=(4,5)$$$(we can let one car stop at $$$4$$$ but can't let it stop at $$$7$$$),
  • $$$dp[4]=(4,5)$$$(we can't stop a car at $$$2$$$).

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:

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int p[N];

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, x1, x2;
	cin >> n >> x1 >> x2;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	int l = abs(x1 - x2), r = 1e9 + 7, ans = -1;
	while (l <= r) {
		int m = (l + r) >> 1;
		set<int> dp;
		if (abs(x1 - p[1]) <= m) dp.insert(x1);
		if (abs(x2 - p[1]) <= m) dp.insert(x2);
		bool ok = !dp.empty();
		for (int i = 2; i <= n; ++i) {
			while (!dp.empty() && abs(*dp.begin() - p[i]) > m) dp.erase(dp.begin());
			while (!dp.empty() && abs(*--dp.end() - p[i]) > m) dp.erase(--dp.end());
			if (abs(p[i - 1] - p[i]) <= m) dp.insert(p[i - 1]);
			if (dp.empty()) {
				ok = false;
				break;
			}
		}
		if (ok) ans = m, r = m - 1;
		else l = m + 1;
	}
	cout << ans << '\n';
	return 0;
}
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You so cool. I got understand. Thank you so much! <3