SHROUTE - Editorial

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

Simple

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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../in.txt", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int sumN = 0;
int sumM = 0;
forn(tc, T)
{
vector<int> A(N);
set<int> s1;
set<int> s2;
forn(i, N)
{
if(i + 1 != N)
else
if (A[i] == 1)
s1.insert(i);
if (A[i] == 2)
s2.insert(i);
}
forn(i, M)
{
int Bi = 0;
if (i + 1 != M)
else
--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;
void run() throws Exception{
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());}

StringTokenizer st;
}

}

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

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


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

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

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() {
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

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

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(' '))

# 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";
}
}