SHROUTE - Editorial

editorial
, , ,
49

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;
    }
50

@cubefreak777
i am getting correct output

image
image1366×768 84.5 KB

51

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
52

Dry run your code, and run it on some other complier, maybe on CC compiler.

53

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.

54

What is wrong with my program?.. I’m unable to figure out :cry:
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);
	}
}
55

@cubefreak777 @taran_1407
please help!!!

56

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
57

Thank you so much @cubefreak777

1 Like
58

This was the first time I participated in Codechef Discussions.
My experience has been so amazing this far.
I was stuck at this problem for quite a long time; not knowing it was such a silly mistake.
I appreciate that you took out time for me and tested my program!
Thank you so much :slight_smile:

4 Likes
59 
void solve()
{
    ll i,n,m;
    cin>>n>>m;
    
    //Resetting variables
    memset(lev,-1,sizeof(lev));

I don’t see any explicit restriction on T, so maybe it can be as large as 10^6, in which case you’re setting 100005 values to -1, 10^6 times.

That’s just a guess, though.

4 Likes
61

O(N) Simple Solution :slightly_smiling_face:

62

I submitted a similar solution using a distance vector, an O(n) solution but it didn’t yet passed the test. I have posted my solution below…

63

Consider the test input:

1
4 1
0 0 1 2
2
3 Likes
64

-1

That’s the result of running the test-case below. My solution performs well for this one. Didn’t it?..
1
4 1
0 0 1 2
2

65

Not really, since the correct answer is 2 :slight_smile:

1 Like
66

Ohhh… Yeah!!! You’re right. What a big mistake!!! Thanks for your support…

2 Likes
67

i was getting an error because i missed an edge case in which i forgot to print 0 whenever i am asked for a query on position 0.
probably this could be the reason for your code not passing.
CodeChef: Practical coding for everyone here is my code.

1 Like
68

My O(n) solution using stacks. Converted 1 to -1 and found the next greater element for all 0s and then found the previous smaller element for all 0s and then took the minimum of the two.
https://www.codechef.com/viewsolution/47755461

69

@cubefreak777
got it thank you :slightly_smiling_face: