Has anyone solved this Question using Java . Please share your solution
void solve() {
ll n,m,one=-1,two=-1;
cin>>n>>m;
vl a(n+1),b(m+1),v1(n+1,-1),v2(n+1,-1);
vector check(n+1,false);
FOR(i,1,n+1)
{
cin>>a[i];
if(a[i]==1)
{
one=i;
}
v1[i]=one;
if(a[i])check[i]=true;
}
for(ll i=n;i>=1;i–)
{
if(a[i]==2){
two=i;
}
v2[i]=two;
}
FOR(i,1,m+1)
{
cin>>b[i];
if(a[b[i]]){
cout<<0<<" “;
} else{
ll x=v2[b[i]]-b[i],y=b[i]-v1[b[i]];
if(v1[b[i]]==-1 && v2[b[i]]==-1)
{
cout<<-1<<” ";
} else if(v1[b[i]]!=-1 && v2[b[i]]!=-1) {
/*cout<<x<<" "<<y<<" ";*/
cout<<min(x,y)<<" ";
} else if(v1[b[i]]!=-1 && v2[b[i]]==-1)
{
// cout<<x<<" "<<y<<" ";
cout<<y<<" ";
/*cout<<v2[b[i]]<<" ";*/
}
else if(v1[b[i]]==-1 && v2[b[i]]!=-1)
{
/* cout<<x<<" "<<y<<" ";*/
cout<<x<<" ";
}
}
}
}
I have done in o(n) time complexity still i am getting TLE.Can anyone help me in figuring out this?
For checking every value of B list i used nested list. Any other way to do it?
Did anyone did it in python? If anyone did pls share…
@cubefreak777 @taran_1407
can you please tell me what is wrong in my code, my test cases are passing but i am getting WA.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void binary_search(ll dest, vector<ll> train_1, vector<ll> train_2)
{
ll train_1_point = -1;
ll train_2_point = -1;
ll mid = 0;
if (train_1.size() > 0)
{
if (dest > train_1[0])
{
mid = (1 + train_1.size()) / 2;
if (dest > train_1[mid - 1])
{
while (dest > train_1[mid - 1])
{
train_1_point = train_1[mid - 1];
if (mid - 1 < train_1.size() - 1)
mid++;
else
break;
}
}
else
{
mid = 0;
while (dest > train_1[mid])
{
train_1_point = train_1[mid];
if (mid - 1 < train_1.size() - 1)
mid++;
else
break;
}
}
}
else
train_1_point = -1;
}
if (train_2.size() > 0)
{
if (dest < train_2[train_2.size() - 1])
{
mid = (1 + train_2.size()) / 2;
if (dest < train_2[mid - 1])
{
while (dest < train_2[mid - 1])
{
train_2_point = train_2[mid - 1];
if (mid - 1 > 0)
mid--;
else
break;
}
}
else
{
mid = train_2.size() - 1;
while (dest < train_2[mid])
{
train_2_point = train_2[mid];
if (mid - 1 > 0)
mid--;
else
break;
}
}
else
train_2_point = -1;
}
ll ans = 0;
if (train_1_point == -1 && train_2_point == -1)
ans = -1;
else if (train_1_point > -1 && train_2_point > -1)
ans = min((train_2_point - dest), (dest - train_1_point));
else if (train_1_point == -1)
ans = train_2_point - dest;
else if (train_2_point == -1)
ans = dest - train_1_point;
cout << ans << " ";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
while (t--)
{
ll n, m;
cin >> n >> m;
ll a[n];
vector<ll> train_1;
vector<ll> train_2;
for (ll i = 0; i < n; i++)
{
cin >> a[i];
if (a[i] == 1)
train_1.push_back(i + 1);
else if (a[i] == 2)
train_2.push_back(i + 1);
}
ll b[m];
for (ll i = 0; i < m; i++)
{
cin >> b[i];
}
for (ll i = 0; i < m; i++)
{
if (b[i] == 1)
{
cout << 0 << " ";
}
else if (a[b[i] - 1] == 1 || a[b[i] - 1] == 2)
{
cout << 0 << " ";
}
else
binary_search(b[i], train_1, train_2);
}
cout << endl;
}
return 0;
}
Thank you
Your code isn’t compiling, would you rather share the code link?
let say if the test case is like this.
6 1
1 2 0 1 2 0
3
now,
I used two multimaps to keep track of stations.
1st map for train numbered 1 and second map for train numbered 2.
so for above test case maps would look like this.
map 1 :
index | train number
1 | 1 (train with number 1 at index 1)
4 | 1 (train with number 1 at index 4)
map 2:
index | train Number
2 | 2
5 | 2
I have ignored the station 0/
now for every query I just need to find the lower_bound of the query
as here q = 3
so I have to find the lower_bound of 3 in map one and the same for map 2
now I have to display the min( (q - lower_bound(3).map1 ) , ( lower_bound(3).map2 - q ) )
although you could do it with multiset too.
4 Likes
Your code fails for the following test-case,
TEST_CASE
1
10 10
1 0 1 1 0 1 0 1 1 1
1 6 4 6 8 10 9 4 10 5
CORRECT_OUTPUT
0 0 0 0 0 0 0 0 0 1
YOUR_OUTPUT
0 0 0 0 0 0 0 0 0 4
Thank you. Now I found out my mistake…
Any solution without using the stl in c++?
Hello, Coders,
I tried to find answer with Binary Search from desired station, But getting TLE.
Can you review on my code ?
Thank You
https://www.codechef.com/viewsolution/47815176
/*
TLE
written by Aashray Bavisa
on 14 June 2021
*/
#include <iostream>
#include <cstdlib>
#define MARS \
ios_base::sync_with_stdio(false); \
cin.tie(NULL); \
cout.tie(NULL);
#define endl '\n'
using namespace std;
#define S ' '
#define pfor(iter, init, lim, diff) for (int iter = init; iter < lim; iter += diff)
void solve()
{
int stations, travellers;
cin >> stations >> travellers;
int train[stations];
pfor(i, 0, stations, 1)
{
cin >> train[i];
}
pfor(i, 0, travellers, 1)
{
int t;
cin >> t;
// decreased by one just to count from 0
t--;
// if desired station has train at time = 0
if (train[t])
cout << 0;
else
{
int c = 1;
bool f = 1;
while (t - c >= 0 || t + c < stations)
{
// if left side stations have train going in right side i.e. == 1
// or right side stations have traing going in left side i.e. = 2
// whenever we got first occurance of that, we got our minimum station
if ((t - c >= 0 && train[t - c] == 1) || (t + c < stations && train[t + c] == 2))
{
cout << c;
f = 0;
break;
}
c++;
}
// if couldn't find any station satisfying our condition
if (f)
cout << -1;
}
cout << S;
}
cout << endl;
}
int main()
{
MARS;
int TC = 1;
cin >> TC;
for (int u = 1; u <= TC; u++)
solve();
return 0;
}
Easy and clear solution:
simply precompute what is the closest index in left side where arr[i]==1 and
what is the closest index in right side where arr[i]==2.
My code link: CodeChef: Practical coding for everyone
2 Likes
You can get away with vectors but you have to use it very effectively. you cant use any of the vector functions. you have to use them just as an array. I used them to store the min time to reach of each an every station. by just taking last valid station (for both left and right) - index of the station.
What is wrong with my program?.. I’m unable to figure out 
Please help!!!
import java.util.*;
import java.io.*;
class shroute {
static class FastReader
{
BufferedReader br;
StringTokenizer st;
public FastReader()
{
br = new BufferedReader(new
InputStreamReader(System.in));
}
String next()
{
while (st == null || !st.hasMoreElements())
{
try
{
st = new StringTokenizer(br.readLine());
}
catch (IOException e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt()
{
return Integer.parseInt(next());
}
long nextLong()
{
return Long.parseLong(next());
}
double nextDouble()
{
return Double.parseDouble(next());
}
String nextLine()
{
String str = "";
try
{
str = br.readLine();
}
catch (IOException e)
{
e.printStackTrace();
}
return str;
}
}
public static void main(String[] args) {
FastReader fr=new FastReader();
int t=fr.nextInt();
StringBuilder sb=new StringBuilder();
while(t-->0)
{
int n=fr.nextInt();
int a[]=new int [n];
int m=fr.nextInt();
int b[]=new int[m] ;
int l[]=new int[n];
int left=-Integer.MAX_VALUE,right=Integer.MAX_VALUE;
int r[]=new int[n];
for(int i=0;i<n;i++)
a[i]=fr.nextInt();
for(int i=0;i<n;i++)
{
if(a[i]==1) {
right=i;
break;
}
}
for(int i=n-1;i>-1;i--)
{
if(a[i]==2) {
left=i;
break;
}
}
for(int i=0;i<m;i++)
b[i]=fr.nextInt();
int j=1;
Arrays.fill(l, Integer.MAX_VALUE);
Arrays.fill(r, Integer.MAX_VALUE);
for(int i=right;i<n;i++)
{
if(a[i]==1) {
r[i]=0;
j=1;
}
else
{
r[i]=j;
j++;
}
}
j=1;
for(int i=left;i>=0;i--)
{
if(a[i]==2) {
l[i]=0;
j=1;
}
else
{
l[i]=j;
j++;
}
}
for(int i=0;i<m;i++)
{
j=Math.min(l[b[i]-1], r[b[i]-1]);
if(j==Integer.MAX_VALUE)
sb.append("-1 ");
else
sb.append(j+" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}Your code fails for the following test-case,
TEST_CASE
1
3 5
0 2 1
3 1 3 2 1
CORRECT_OUTPUT
0 0 0 0 0
YOUR_OUTPUT
0 1 0 0 1