abhijeetgupto - if you process the full city set for every query, you will be doing far too much data handling. Much better to separate out the up-train and down-train cities and then use those either to search for suitable journey start points or pre-process to a time map; something like:
ups = []
downs = [0]
for city, dirn in enumerate(trains, start=1):
if dirn == 1:
ups.append(city)
elif dirn == 2:
downs.append(city)
However: if you hadn’t gotten TLE, you would have gotten WA. The results from a single test case are supposed to be delivered on a single line of space-separated values.
Fast output is as important as fast input in this case - you need to limit your print statements.
Simple C++ solution. O(n) time complexity.
#include <iostream>
using namespace std;
void solve()
{
int stationSize,destinationSize;
vector<int> stations,destinations;
cin>>stationSize>>destinationSize;
int in;
for(int i=0;i<stationSize;i++){
cin>>in;
stations.push_back(in);
}
for(int i=0;i<destinationSize;i++){
cin>>in;
destinations.push_back(in);
}
vector<int> distanceArray;
distanceArray.assign(stations.size(),INT_MAX);
distanceArray[0]=0;
int counter=0,lastRightTrain=-1,lastLeftTrain=-1;
//left to right pass
for(int i=0;i<stationSize;i++){
if(stations[i]==1){
lastRightTrain=i;
}
if(stations[i]==1 || stations[i]==2){
distanceArray[i]=0;
}
else if(stations[i]==0){
distanceArray[i]=lastRightTrain==-1?distanceArray[i]:(i-lastRightTrain);
}
}
//right to left pass
for(int i=stationSize-1;i>=0;i--){
if(stations[i]==2){
lastLeftTrain=i;
}
if(stations[i]==0){
distanceArray[i]=lastLeftTrain==-1?distanceArray[i]:min(distanceArray[i],lastLeftTrain-i);
}
}
for(int i=0;i<destinationSize;i++){
int a=distanceArray[destinations[i]-1]==INT_MAX?-1:distanceArray[destinations[i]-1];
cout<<a<<" ";
}
cout<<endl;
}
int main()
{
int t;
cin>>t;
while (t--)
{
solve();
}
}Couple of Python solutions for interest:
#include<bits/stdc++.h>
using namespace std;
int main(){
void solution(long long,long long);
int t;
cin>>t;
while(t){
long long n,m;
cin>>n>>m;
solution(n,m);
cout<<endl;
t--;
}
return 0;
}
void solution(long long n,long long m){
long long x,i,y;
vector<long long> a(n,0);
vector<long long> b(m,0);
vector<long long> start(n,0);
vector<long long> ends(n,0);
for(i=0;i<n;i++) cin>>a[i];
for(int j=0;j<m;j++) cin>>b[j];
if(a[0]==2||a[0]==0){
for(int i=0;i<m;i++){
if(b[i]==1) cout<<0<<" ";
else cout<<-1<<" ";
}
}else{
int x=-1;
for(i=0;i<n;i++){
if(a[i]==1){
start[i]=i;
x=i;
}else{
start[i]=x;
}
}
x=-1;
for(i=n-1;i>=0;i--){
if(a[i]==2){
ends[i]=i;
x=i;
}else{
ends[i]=x;
}
}
for(i=0;i<m;i++){
long long index = b[i]-1;
if(b[i]==1||a[index]==1||a[index]==2) cout<<0<<" ";
else {
if(ends[index]==-1) cout<<index-start[index]<<" ";
else cout<<min(ends[index]-index,index-start[index])<<" ";
}
}
}
}
Bro, don’t use nested loops.
Can someone help me find mistake ,I am getting WA
I traversed array left to right for station 1 an then right to left for station 2 to get a minimum distance array named result for each station
time complexity O(n)
#include<iostream>
using namespace std;
int main(void) {
int t;
cin>>t;
while(t--)
{
int cities;
int people;
cin>>cities;
cin>>people;
int a[cities];
int b[people];
int result[cities];
for(int i=0;i<cities;i++)
{
cin>>a[i];
}
for(int i=0;i<people;i++)
{
int destination;
cin>>destination;
b[i]=destination-1;
}
for(int i=0;i<cities;i++)
result[i]=1000000009;
int pos=-1;
for(int i=0;i<cities;i++)
{
if(a[i]==1)
{
pos=i;
}
if(pos!=-1)
{
if(a[i]==2)
result[i]=0;
else
result[i]=min(result[i],i-pos);
}
}
int pos2=-1;
for(int i=cities;i>=0;i--)
{
if(a[i]==2)
{
pos2=i;
}
if(pos2!=-1)
{
if(a[i]==1)
result[i]=0;
else
result[i]=min(result[i],pos2-i);
}
}
for(int i=0;i<people;i++)
{
if(result[b[i]]!=1000000009)
cout<<result[b[i]]<<" ";
else
cout<<-1<<" ";
}
cout<<endl;
}
}
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.
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++?