SHROUTE - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Akash Bhalotia and Daanish Mahajan
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

None

PROBLEM

Given an array A of length N representing N cities present in a line where A_i = 0 means no station, A_i = 1 means city i having a train station with train moving to the right, and A_i = 2 means city i having a train station with train moving to the left.

Initially, M travellers are at city 1 and can teleport to any city with a station in 0 minutes. Determine, for each traveller the minimum time required to reach the destination, or determine if it’s not possible for the traveller to reach the destination.

QUICK EXPLANATION

  • Build a list of trains going left and a list of trains right. For traveller at destination p, we need to find the largest positioned train going right at position \leq p and smallest positioned train going left at position \geq p
  • The minimum time taken among these two trains is the required minimum time, if both don’t exist, then it’s not possible to reach city p.
  • Edge case is when the traveller is at city 1, the time taken is 0 irrespective of train stations.

EXPLANATION

Brute force solution

For each traveller, check all train stations, and if a train from that station can reach the traveller’s destination, update the minimum time. This solution works in O(N*M) time and gets time limit exceeded verdict.

Using Binary Search

For the traveller with destination p, We know, that among trains going right, only the train with the largest positioned train to the left of p matter. If we have a list L of trains going right, our required train’s station is the largest value \leq p in list L.

Similarly, for the list of trains R going left, we want to find smallest value \geq p in list R

Since list L and R can be built before queries, we can build and sort them beforehand, and binary search in order to find the answer to our queries.

Alternatively, these queries are available as lower_bound() and upper_bound() methods in C++, and floor/ceiling methods in TreeSet in java.

The time complexity of this solution is O(N*log(N))

Using precomputation before queries

Let’s compute L_u as the minimum time to reach station u via a train moving towards left, and R_u as the minimum time to reach station u via a train moving right.

Initialliy assuming L_u = R_u = \infin for all u.
For stations with a train going right, we can set R_u = 0, and for all stations with a train going left, we can set L_u = 0.

Now, we can see that train at station u moving right shall reach station u+1 in R_u+1 time, we have update R_u = min(R_u, R_{u-1}+1)

Similarly, we have L_u = min(L_u, L_{u+1}-1)

We can compute R_u in increasing order of u and L_u in decreasing order of u in O(N) time.

The minimum time taken to reach city p is min(L_p, R_p). If both L_p and R_p are \infin, then it’s not possible to reach city p.

Edge Case

Since the travellers start at city 1 before teleporting, all the travellers having city 1 as the destination do not need to teleport. The minimum time needed is 0 here.

TIME COMPLEXITY

The time complexity is O(N) or O(N*log(N)) per test case depending upon implementation.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>

# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;

const int maxtn = 1e6, maxtm = 1e6, maxn = 1e5, maxm = 1e5;
const string newln = "\n", space = " ";
int main()
{   
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    int tn = 0, tm = 0;
    while(t--){
        int n, m; cin >> n >> m;
        tn += n; tm += m;
        int dp[n + 2][2];
        int a[n + 2];
        for(int i = 1; i <= n; i++){
            cin >> a[i];
        }
        dp[0][0] = dp[n + 1][1] = n + 10;
        for(int i = 1; i <= n; i++){
            if(a[i] == 1){
                dp[i][0] = 0;
            }else{
                dp[i][0] = dp[i - 1][0] + 1;
            }
            if(a[n - i + 1] == 2){
                dp[n - i + 1][1] = 0;
            }else{
                dp[n - i + 1][1] = dp[n - i + 2][1] + 1;
            }
        }
        for(int i = 1; i <= m; i++){
            int x; cin >> x;
            int ans = min(dp[x][0], dp[x][1]);
            if(ans > n)ans = -1;
            if(x == 1)ans = 0;
            cout << ans << (i == m ? newln : space);
        }
    }
    assert(tn <= maxtn);
    assert(tm <= maxtm);
} 
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
    #include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

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 main(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../in.txt", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 1'000'000);
    int sumN = 0;
    int sumM = 0;
    forn(tc, T)
    {
	    int N = readIntSp(1, 100'000);
	    int M = readIntLn(1, 100'000);
	    vector<int> A(N);
	    set<int> s1;
	    set<int> s2;
	    forn(i, N)
	    {
		    if(i + 1 != N)
			    A[i] = readIntSp(0, 2);
		    else
			    A[i] = readIntLn(0, 2);
		    if (A[i] == 1)
			    s1.insert(i);
		    if (A[i] == 2)
			    s2.insert(i);
	    }
	    forn(i, M)
	    {
		    int Bi = 0;
		    if (i + 1 != M)
			    Bi = readIntSp(1, N);
		    else
			    Bi = readIntLn(1, N);
		    --Bi;
		    int res = -1;
		    if (!s1.empty())
		    {
			    auto b1 = s1.upper_bound(Bi);
			    if (b1 != s1.begin() && (b1 == s1.end() || *b1 != Bi))
			    {
				    --b1;
			    }
			    if (*b1 <= Bi)
				    res = Bi - *b1;
		    }
		    if (!s2.empty())
		    {
			    auto b2 = s2.lower_bound(Bi);
			    if (b2 != s2.end())
			    {
				    if (res == -1)
					    res = *b2 - Bi;
				    else if (res > *b2 - Bi)
					    res = *b2 - Bi;
			    }
		    }
		    if (Bi == 0)
			    res = 0;
		    printf("%d ", res);
	    }
	    printf("\n");
    }
    assert(sumN <= 1'000'000);
    assert(sumM <= 1'000'000);
    assert(getchar() == -1);
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class SHROUTE{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), Q = ni(), INF = (int)1e9;
        int[] left = new int[N], right = new int[N];
        Arrays.fill(left, INF);
        Arrays.fill(right, INF);
        for(int i = 0; i< N; i++){
            int x = ni();
            if(x == 1)right[i] = 0;
            if(x == 2)left[i] = 0;
        }
        for(int i = 1; i< N; i++)right[i] = Math.min(right[i], right[i-1]+1);
        for(int i = N-2; i>= 0; i--)left[i] = Math.min(left[i], left[i+1]+1);
        for(int q = 0; q< Q; q++){
            int p = ni()-1;
            int time = Math.min(left[p], right[p]);
            if(time == INF)time = -1;
            if(p == 0)time = 0;
            p(time);
            if(q+1 < Q)p(" ");
            else pn("");
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new SHROUTE().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

4 Likes

anyone did this question with binary search ,share your code to understand where i was wrong

3 Likes

https://www.codechef.com/viewsolution/47460379

:slight_smile: not the best. took lot lot lot lot of tries.

1 Like

nice one bro . checked many solutions . all are same except variable changes . finally a different one .

3 Likes

I did somewhat same what editorilist solution suggest, but instead of putting distance i putted the closest index where train gets started and solve q according to that. but my solution did not pass, plz tell me where my code goes wrong.
https://www.codechef.com/viewsolution/47807115

I tried coding up the solution using “upper_bound” and “lower_bound” as well but it seems it doesn’t work for me. If the editorialist can clear this out as to why it doesn’t work for me it will be great.

#include <map>
#include <set>
#include <cstdio>
#include <vector>
#include <iostream>
#include <cstdlib>
#include <algorithm>

using namespace std;

void printVector(vector<int> vec) {
	cout << "printing vector : " << endl;
	for (int i = 0; i < vec.size(); ++i) {
		cout << vec[i] << " ";
	}

	cout << endl;
}

void solve() {
	int N, M; 
	scanf("%d", &N);
	scanf("%d", &M);

	vector<int> Ai(N + 1, 0);
	vector<int> Bi(M + 1, 0);
	vector<int> Ci(M+1, 0);
	vector<int> rightTrains;
	vector<int> leftTrains;

	for (int i = 1; i <= N; ++i) {
		scanf("%d", &Ai[i]);

		if (Ai[i] == 1) {
			rightTrains.push_back(i);
		}

		if (Ai[i] == 2) {
			leftTrains.push_back(i);
		}
	}

	for (int i = 1; i <= M; ++i) {
		scanf("%d", &Bi[i]);
	}

	// sort the vectors for the trains going to the right and the left
	sort(rightTrains.begin(), rightTrains.end());
	sort(leftTrains.begin(), leftTrains.end());

	//printVector(rightTrains);
	// printVector(leftTrains);

	for (int i = 1; i <= M; ++i) {
		// if the destination of the traveller is the first station itself
		// then they are already there and hence time taken is 0
		if (Bi[i] == 1) {
			Ci[i] = 0;
			continue;
		}

		// in the case when every station has 0 trains and the destination
		//  is not 1
		if (rightTrains.size() == 0 && leftTrains.size() == 0) {
			Ci[i] = -1;
			continue;
		}

		int lb, ub;
		lb = ub = -1;

		if (rightTrains.size() != 0) {
			auto lowerBound = lower_bound(rightTrains.begin(), rightTrains.end(), Bi[i]);
			cout << "lowerBound index : " << lowerBound - rightTrains.begin() << endl;
			lb = rightTrains[lowerBound - rightTrains.begin()];
		}

		if (leftTrains.size() != 0) {
			auto upperBound = upper_bound(leftTrains.begin(), leftTrains.end(), Bi[i]);
			cout << "upperBound index : " << upperBound - leftTrains.begin() << endl;
			ub = leftTrains[upperBound - leftTrains.begin()];
		}

		cout << "lb : " << lb << " ub : " << ub << endl;

		if (lb != -1 && ub == -1) {
			Ci[i] = abs(lb - Bi[i]);
			continue;
		}

		if (lb == -1 && ub != -1) {
			Ci[i] = abs(ub - Bi[i]);
			continue;
		}

		Ci[i] = min(abs(lb - Bi[i]), abs(ub - Bi[i]));
	}

	for (int i = 1; i <= M-1; ++i) {
		printf("%d ", Ci[i]);
	}
	
	printf("%d\n", Ci[M]);
}

int main() {
	int T;
	scanf("%d", &T);

	while (T--) {
		solve();
	}
}

Can you guys make a review on my solution. I merged both left and right train directions in a common vector like in a Dijsktra algorithm but it didn’t work for me. I’m not sure if it was an I/O issue because I ran many sample tests and it always gave me the correct answer. Thanks for your help. Here is my solution in C++:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int T;
    scanf("%d\n", &T);
    for (int i = 0; i < T; i++)
    {
        int N, M;
        scanf("%d %d\n", &N, &M);

        vector<int> dist(N, INT_MAX);

        dist[0] = 0;

        // Building the distance vector
        for (int i = 0; i < N; i++)
        {
            int direction;
            scanf("%d", &direction);
            if ((direction == 1)) {
                dist[i] = 0;
                int j = 1;
                while ((i + j < N) && (dist[i + j] > j)) dist[i + j] = j, j++;
            }
            else if (direction == 2) {
                dist[i] = 0;
                int j = 1;
                while ((i - j >= 0) && (dist[i - j] > j)) dist[i - j] = j, j++;
            }
        }

        for (int i = 0; i < M; i++)
        {
            int destiny;
            scanf("%d", &destiny);
            printf("%d ", (dist[destiny - 1] != INT_MAX)? dist[destiny - 1] : -1);
        }

        printf("\n");
    }

    return 0;
}

I did it with mower bound and it passed all cases

#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–){
int n,m;
cin>>n>>m;
multimap<int, int> mp1;
multimap<int, int> mp2;
for(int i=1; i<=n; ++i){
int x;
cin>>x;
if(x==1){
mp1.insert({i,1});
}
else if(x==2){
mp2.insert({i,2});
}
}
int size1 = mp1.size();
int size2 = mp2.size();

    for(int i=1; i<=m; ++i){
        int x;
        cin>>x;
        if(x==1){
            cout<<0<<" ";
        }
        else{
            auto it1 = mp1.lower_bound(x);
	        auto it2 = mp2.lower_bound(x);
	        int behind = -1;
	        int next = -1;
	        if((it1->first==x && it1->second!=0) || (it2->first==x && it2->second!=0)){
	            behind=0;
	            next=0;
	        }else{
	            if(it1->second!=0){
	                auto f=mp1.begin();
	                if(f->first == it1->first)
	                    behind=-1;
	                else{
	                    it1--;
	                    behind = x-(it1->first);
	                }
	            }
	            else{
	                if(size1>0){
	                    --it1;
	                    if(it1->second!=0)
	                        behind = x - (it1->first);
	                    else
	                        behind=-1;
	                }
	                else{
	                    behind = -1;
	                }
	            }
	            if(it2->second!=0){
	                next=(it2->first)-x;
	            }
	            else{
	                next = -1;
	            }
	        }
	        
	        if(behind==-1&&next==-1){
	            cout<<-1<<" ";
	        }
	        else if(behind == -1&& next!=-1){
	            cout<<next<<" ";
	        }
	        else if(behind!=-1&& next==-1){
	            cout<<behind<<" ";
	        }
	        else{
	            cout<<min(behind, next)<<" ";
	        }
        }
    }
    cout<<endl;
}
return 0;

}

4 Likes

Care to format your code and put it in a spoiler before posting or rather share a link if you really want to help.

Yeah i’ll take care of that in future

4 Likes

Somewhat readable c++ solution

I don’t see any c++ submission by you for this problem

Can’t understand why my solution is giving TLE? I have implemented it in O(n).
Please take a look.

https://www.codechef.com/viewsolution/47838720

vectors were slow for this problem, i used c typed arrays to get away.

But in the Tester’s solution and in the video editorials they used vectors.

1 Like

although I haven’t spent much time on your code but I can see two while loops inside your for loops and I think there might be the TLE.

3 Likes

You are partially correct. Please look at it once more. I am still getting TLE.

Can someone please tell me what’s wrong with this solution , i was getting tle.

import sys
t = int(input())
for i in range(t):

# taking input
n, m = map(int, sys.stdin.readline().split(' '))
direction = list(map(int, sys.stdin.readline().split(' ')))
travellers = list(map(int, sys.stdin.readline().split(' ')))

# logic
for destination in travellers:
    if direction[destination - 1] != 0 or destination == 1:
        print(0)
    else:
        s1 = n
        s2 = n
        if 1 in direction[:destination - 1]:
            l = direction[:destination - 1]
            l.reverse()
            temp = l.index(1) - len(l) + 1
            s1 = (destination - 1) - temp
        if 2 in direction[destination:]:
            l = direction[destination:]
            temp = l.index(2) + destination
            s2 = temp - (destination - 1)

        if s1 == n and s2 == n :
            print(-1)
        else:
            print(min(s1,s2))

Hi can anyone help me find what is wrong with my solution?
It’s almost similar to Editorials solution, but I got Wrong Answer

#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include <bits/stdc++.h>

using namespace std;
long long int best[100002];
long long int A[100002];
long long int B[100002];
int main()
{
    // ios_base::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
    long long int T;
    cin>>T;
    while (T--)
    {
        long long int N,M,a,b;
        cin>>N>>M;
        long long int left = -1,right=N;
        for(long long int i=0;i<N;i++)
        {
            best[i] = -1;
        }
        for(long long int i=0;i<N;i++)
        {
            cin>>A[i];
        }
        for(long long int i=0;i<M;i++)
        {
            cin>>B[i];
        }
        for(long long int i=0;i<N;i++)
        {
            if(A[i] == 1)
                left = i;
            if(left != -1)
                best[i] = i-left;
        }
        for(long long int i=N-1;i>=0;i--)
        {
            if(A[i] == 2)
                right = i;
            
            if(right != N)
                if((best[i] == -1) || (best[i] > (right-i)))
                    best[i] = right - i;
        }
        for(long long int i=0;i<M;i++)
        {
            cout<<best[B[i]-1]<<" ";
        }
        cout<<"\n";
    }
}

Solution using Dijkstra’s Algorithm