TWOLANE - Editorial

vijju123 · July 27, 2019, 4:32pm

PROBLEM LINK:

Div1
Div2
Practice

Setter- Hasan Jaddouh
Tester- Roman Bilyi
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Greedy, (Some)Implementation

PROBLEM:

There are 2 lanes. At some parts of the lanes, there are some obstacles. Given the X-coordinate and lane of each obstacle, tell the maximum distance Chef can travel. Print K if he is able to reach his destination.

QUICK-EXPLANATION:

Key to AC- Realize that if there is an obstacle in the lane you’re at, its good to switch lane as soon as possible if other lane is clear of obstacles till that X-Coordinate.

Start from the lane with obstacle at a greater distance X_i. Also keep a track of the next obstacle in the other lane. Once the next obstacle in the other lane lies at an X coordinate of X_{i+1}>X_i, switch the lane. Rinse and repeat until you can no longer move further or if you cleared all obstacles.

EXPLANATION:

We will first discuss the greedy strategy, and then discuss the intuitional proof.

The greedy strategy-

The quick explanation pretty much sums it all. I will just expand that part here a little bit.

Start at the lane where the obstacle lies at a greater X-coordinate, X_i - this is an obvious choice.

Now, we keep a track of positions of all obstacles. There are 2 cases possible-

The obstacle is not in your lane - Simple, just record its position as “Position of Latest Obstacle Passed in Other Lane” and move on.
The obstacle is in your lane - If this is the case, then it is optimal to switch lanes as early as possible, due to the constraint of moving D length before switching lanes. (The proof will be discussed below, but it should be easy to see why this might be correct.) The best position to switch lane is “Position of Latest Obstacle Passed in Other Lane +1” (i.e. immediately after crossing that obstacle). If D distance isn’t covered till then, then switch as soon as you cover the required distance. If you can’t switch before hitting the next obstacle, then its the end of the journey .

The implementation for this is surprisingly crisp and simple. You can try doing it yourself first, and then refer to setter’s implementation to appreciate the differences between them-

Setter's implementation

int last_switch =-1<<30;
	int lane = 3 - L[0];
	int ans = k,ans_i=-1;
	for(int i=0;i<n;i++){
		if(L[i] != lane)continue;
		int bst = max(last_switch + d, X[i-1] +1 );
		if(bst >= X[i] ){
			ans =  X[i];
			ans_i = i;
			break;
		}
		lane = 3 - L[i];
		last_switch = bst;
	}
	cout<<ans<<endl;

Now, if you think on why this works - then we do not need to look far. By switching lanes as soon as possible (when the next obstacle is in your lane, and the next lane is clear till then), you are reducing the amount of distance to travel before the switch. You anyway have to make the switch - there is no choice here. You also cannot make the switch before crossing the latest obstacle on the other lane (such that the next obstacle is on the other lane). This is a hint that it is not a dynamic programming problem. Its trivial to see that switching any later will only increase the distance to travel before switching again, and hence is non-optimal.

SOLUTION

Setter

#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
			
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			assert(cnt>0);
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
 
int T;
int n;
int X[100100];
int L[100100];
int k,d;
int sm_n=0;
int main(){
	//freopen("01.txt","r",stdin);
	//freopen("01o.txt","w",stdout);
	T=readIntLn(1,1000);
	while(T--){
		n=readIntSp(1,100000);
		k=readIntSp(2,1000000000);
		d=readIntLn(1,1000000000);
		sm_n += n;
		assert(sm_n<=1000000);
		for(int i=0;i<n;i++){
			if(i==n-1){
				X[i]=readIntLn(1,k-1);
			} else {
				X[i]=readIntSp(1,k-1);
			}
			if( i > 0){
				assert(X[i] >X[i-1]);
			}
		}
		for(int i=0;i<n;i++){
			if(i==n-1){
				L[i]=readIntLn(1,2);
			} else {
				L[i]=readIntSp(1,2);
			}
		}
 
		int last_switch =-1<<30;
		int lane = 3 - L[0];
		int ans = k,ans_i=-1;
		for(int i=0;i<n;i++){
			if(L[i] != lane)continue;
			int bst = max(last_switch + d, X[i-1] +1 );
			if(bst >= X[i] ){
				ans =  X[i];
				ans_i = i;
				break;
			}
			lane = 3 - L[i];
			last_switch = bst;
		}
		cout<<ans<<endl;
	}
	assert(getchar()==-1);
}

Tester

 #include "bits/stdc++.h"

using namespace std;
 
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))
 
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
 
typedef long long Int;
typedef vector<int> VI;
typedef pair<int, int> PII;
 
const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000;
const Int LINF = INF * (Int) INF;
const int MAX = 100007; 
 
const int MOD = 998244353;
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
           
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            assert(cnt>0);
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void assertEof(){
    assert(getchar()==-1);
}
 
int main(int argc, char* argv[])
{
	// freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);
    
    int t = readIntLn(1, 1000);
    int sn = 0;
    FOR(tt,0,t)
    {
        int n = readIntSp(1, 100000);
        int k = readIntSp(1, INF);
        int d = readIntLn(1, INF);
 
        VI X(n), L(n);
        FOR(i,0,n)
        {
            X[i] = readInt(1, k - 1, (i + 1 < n ? ' ' : '\n'));
            if (i)
                assert(X[i] > X[i - 1]);
        }
        FOR(i,0,n)
        {
            L[i] = readInt(1, 2, (i + 1 < n ? ' ' : '\n'));
            -- L[i];
        }
 
        int S[2];
        S[0] = S[1] = -INF;
        int cur = 0;
        if (L[0] == 0)
            cur = 1;
        else
            cur = 0;
        int res = k;
        int last_change = -INF;
        FOR(i,0,n)
        {
            if (L[i] == cur)
            {
                int r = X[i] - 1;
                int l = max(S[cur ^ 1] + 1, last_change + d);
                if (l > r)
                {
                    res = X[i];
                    break;
                }
                last_change = l;
                cur ^= 1;
            }
            S[L[i]] = X[i];
        }
        cout << res << endl;
    }
    assert(sn <= 1000000);
    assertEof();
 
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
    
}

Time Complexity=O(N)
Space Complexity=O(N)

CHEF VIJJU’S CORNER

Tester's Notes

Switch lane as soon as you cross the last obstacle of the other lane, obviously after D distance from the previous switch.

Proof: The only possible situation when you couldn’t switch lanes is when the distance from previous switch is less than D, so in case you need to switch it’s better to do asap.

2.New to coding? Beginner? Did this kind of went over your head? Start with solving a simpler version of this problem - Solve it assuming that there is no constraint for distance D.

3.What would you do, if, the problem is modified as-

"Your car moves at a speed S. There are Q queries which you need to additionally do, of the form-

1 X  L t - insert an obstacle in Lane L, at time t, and at position X 
2 X L t - Remove an obstacle from Lane L, at time t and at position X. Its guaranteed that there will be an obstacle at the position.

4.Implementation neatness! Implementation neatness! Implementation neatness!! I cannot stress this enough. Look at setter’s code and appreciate how he made it clean - this will help you greatly! Small things like, how he used 3-L[i] to decide which lane to go, instead of using if-else conditions &etc. Don’t ignore a setter’s solution which is neatly implemented!!

5.If you are not able to solve this problem within the contest- then try to do a timed practice. There is absolutely no denying the fact that if this problem was to be given in long challenge, it’d have a looot of AC submissions! You don’t lack the talent, you lack the time! And the only thing we can do to avoid it is to be quicker.