HDELIVERY: Getting tle

general
1

Hi,

I am currently attempting the problem “Home delivery” from the March long contest. As soon as I saw it, I knew that all I needed was to use a Union-Find data structure. My code is very simple and straight forward, yet I am getting TLE. ( I have implemented both path-compression as well as union-by-rank in my union-find data structure )

I would be very grateful if anyone could suggest improvements to my code. Thank you :slight_smile:

CODE :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
    Implements DisjointSet data structure using both Union by Rank as well
    as Path Compression
*/

class DisjointSet
{
private int[] parent;
private int[] rank;
private int size;


public DisjointSet( int n )
{
    size = n;
    parent = new int[ n ];
    Arrays.fill( parent, -1 );
    rank = new int[ n ];
    Arrays.fill( rank, -1 );
}

public void makeSet( int x )
{
    parent[ x ] = x;
    rank[ x ] = 0;
}

public int findRoot( int x )
{
    if( parent[x] != x )
        parent[ x ] = findRoot( parent[x]);

    return parent[x];
}

public void Union( int x, int y )
{
   int root1 = findRoot( x ) ;
   int root2 = findRoot( y );

   if( root1 != root2)
        Link( root1, root2 );
}

private void Link( int x, int y )
{
   if( rank[ x ] < rank[ y ])  // Make y x's parent
   {
       parent[ x ] = y;
   }

   else if( rank[ x ] > rank[ y ])
   {
       parent[ y ] = x;
   }

   else
   {
       parent[ x ] = y;
       rank[ y ]++;
    }
}


}

public class Main
{
    static int n, m;

public static void main( String[] args ) throws IOException
{
    BufferedReader br = new BufferedReader( new InputStreamReader( System.in ));

    int T = Integer.parseInt( br.readLine() );
    StringTokenizer tok;
    String s;

    while( T-- > 0 )
    {
        s = br.readLine();
        tok = new StringTokenizer( s );

        n = Integer.parseInt( tok.nextToken() );
        m = Integer.parseInt( tok.nextToken() );
        
        DisjointSet d = new DisjointSet( n );
        for( int i=0; i<n; i++ )
            d.makeSet( i );

        for( int i=0; i<m; i++ )
        {
            s = br.readLine();
            tok = new StringTokenizer( s );
            int a = Integer.parseInt( tok.nextToken() );
            int b = Integer.parseInt( tok.nextToken() );

            if( a==b )
                continue;

            d.Union(a, b);
        }

        int q = Integer.parseInt( br.readLine() );

        for( int i=0; i<q; i++ )
        {
            s = br.readLine();
            tok = new StringTokenizer( s );
            int a = Integer.parseInt( tok.nextToken() );
            int b = Integer.parseInt( tok.nextToken() );

            if( d.findRoot(a) == d.findRoot(b))
                System.out.println("YO");

            else
                System.out.println("NO");


        }
    }
}
}
1 Like
2

In this problem the queries are too large. Each time you are computing for the parent value thereby increasing the complexity. You could use pre-computation method to firstly generate all sorts of combination then answer the queries in O(1) time. I used Floyd-Warshall algorithm to get AC.

3 Likes
3

I think you should have a look at my soution . I have solved it using Disjoint sets only and it was quite fast (0.81).

2 Likes
4

Thank you so much for your answer :slight_smile:

5

In your code does each query gets answered in O(1) time? To re-phrase does the running time of this line of code d.findRoot(a) == d.findRoot(b) depend on ‘n’ in the worst case or is it a constant always.

The easiest solution for me in this particular problem was to use BFS/DFS as described in the editorial.

6

Thank you :slight_smile: I went through your code, it’s more or less the same as mine I guess, but I will see if I can use tips from your code to optimize my own further :slight_smile:

Thing is, I actually converted the entire solution to just doing a BFS once, and answering all the queries in constant time. I am still getting a TLE. Is it that StringTokenizer is making my code slow ? If so, could you please suggest some alternatives ?

7

Yes, I think you get TLE beacause taking input as a string and then parsing makes your code slow. I’ll recommend you to look at EgorK’s solution(CodeChef: Practical coding for everyone). It will be good if you use c++ for online judges. I personally feel c++ has almost everything you will need during a contest. If you want to remain stuck to Java then atleast pick up those FastIO methods from EgorK’s code.