1
\$\begingroup\$

So, here is a practice question, on Hackerearth. It states that :

Oliver and Bob are best friends. They have spent their entire childhood in the beautiful city of Byteland. The people of Byteland live happily along with the King. The city has a unique architecture with total N houses. The King's Mansion is a very big and beautiful bungalow having address = 1. Rest of the houses in Byteland have some unique address, (say A), are connected by roads and there is always a unique path between any two houses in the city. Note that the King's Mansion is also included in these houses.

Oliver and Bob have decided to play Hide and Seek taking the entire city as their arena. In the given scenario of the game, it's Oliver's turn to hide and Bob is supposed to find him. Oliver can hide in any of the houses in the city including the King's Mansion. As Bob is a very lazy person, for finding Oliver, he either goes towards the King's Mansion (he stops when he reaches there), or he moves away from the Mansion in any possible path till the last house on that path.

Oliver runs and hides in some house (say X) and Bob is starting the game from his house (say Y). If Bob reaches house X, then he surely finds Oliver.

Given Q queries, you need to tell Bob if it is possible for him to find Oliver or not.

The queries can be of the following two types:
0 X Y : Bob moves towards the King's Mansion.
1 X Y : Bob moves away from the King's Mansion

INPUT : The first line of the input contains a single integer N, total number of houses in the city. Next N-1 lines contain two space separated integers A and B denoting a road between the houses at address A and B. Next line contains a single integer Q denoting the number of queries. Following Q lines contain three space separated integers representing each query as explained above.

OUTPUT : Print "YES" or "NO" for each query depending on the answer to that query.

CONSTRAINTS :
1 ≤ N ≤ 10^5
1 ≤ A,B ≤ N
1 ≤ Q ≤ 5*10^5
1 ≤ X,Y ≤ N

NOTE : Large Input size. Use printf scanf or other fast I/O methods.

And, here is my submission :

import java.util.* ;
import java.io.BufferedReader ;
import java.io.InputStreamReader ;

class nodeA
{
    int value ;
    int size ;//keeps track of the number of nodes after nodeA
    nodeA next = null ;
    nodeA(int v)
    {
        value = v ;
    }
}
class nodeB
{
    int value ;
    boolean visited = false ;
    HashSet<Integer> H = new HashSet<Integer>() ;
    nodeB(int v)
    {
        value = v ;
    }
}
class OliverAndTheGame2
{
    int counter = 0;
    Map<Integer,nodeA> toList = new HashMap<Integer,nodeA>() ;//adjacency List
    // Map<Integer,nodeB> toNode = new HashMap<Integer,nodeB>() ;
    nodeB[] toNode ;
    OliverAndTheGame2(int n)
    {
        toNode = new nodeB[n+1] ;
    }

    void addToLinkedList(int a,nodeA N,nodeA x)
    {
        x.next = N ;
        toList.put(new Integer(a),x) ;//x replaces N as the first node

    }
    void addToList(int a,int x)// 
    {
        if(toNode[a]==null)
        {
            //System.out.println(a+" was added") ;
            toNode[a] = new nodeB(a) ;
        }
        if(toNode[x]==null)
        {
            // System.out.println(x+" was added");
            toNode[x] = new nodeB(x) ;
        }
        if(toList.containsKey(a))
        {
            nodeA X = new nodeA(x) ;
            nodeA N = toList.get(a) ;
            X.size = N.size+1 ;
            addToLinkedList(a,N,X) ;
        }
        else
        {
            nodeA N = new nodeA(x) ;
            N.size = 1 ;
            toList.put(new Integer(a),N) ;
        }
    }
    void modifiedDFS(int a)
    {
        counter++ ;
        if(toList.containsKey(a))
        {
            // System.out.println("Ohh Yeah "+a) ;
            nodeA Na = toList.get(a) ;
            nodeB Nb = toNode[a] ;

            for(nodeA tempA = Na;tempA!= null;tempA = tempA.next)
            {
                nodeB tempB = toNode[tempA.value] ;
                tempB.H.addAll(Nb.H) ;
                tempB.H.add(tempA.value) ;

                // System.out.println("tempB.H contains "+tempA.value+":"+tempB.H.contains(tempA.value)) ;
                modifiedDFS(tempA.value) ;
            }
        }
    }
    boolean onWay(int awayFK,int hide,int start)
    {
        // System.out.println("-->"+awayFK+" "+hide+" "+start) ;
        if(awayFK==0)//towards the king
        {
            nodeB N = toNode[start] ;
            if(N.H.contains(hide))
                return true ; 
            else 
                return false ;

        }
        else//away from the king1
        {
            nodeB N = toNode[hide] ;
            if(N.H.contains(start))
                return true ;
            else
                return false ;

        }
    }
    public static void main(String args[]) throws Exception 
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine() ;
        int N = Integer.parseInt(line) ;

        OliverAndTheGame2 O = new OliverAndTheGame2(N) ;
        for(int i=0;i<N-1;i++)
        {
            line = br.readLine() ;
            O.addToList(Integer.parseInt(line.split(" ")[0]),Integer.parseInt(line.split(" ")[1])) ;//adding to adjacency list O(1)
        }
        O.toNode[1].H.add(1) ;
        O.modifiedDFS(1) ;
        int Q = Integer.parseInt(br.readLine()) ;
        boolean[] results = new boolean[Q] ;
        for(int i=0;i<Q;i++)
        {
            line = br.readLine() ;
            results[i] = O.onWay(Integer.parseInt(line.split(" ")[0]),Integer.parseInt(line.split(" ")[1]),Integer.parseInt(line.split(" ")[2])) ;
        }
        for(int i=0;i<Q;i++)
        {
            System.out.println(results[i]?"YES":"NO") ;
        }
        // System.out.println("Counter :"+O.counter) ;


    }

}

But, this solution gives TLE(time limit exceeded) for 6 test cases. Based on the fact that 4 test cases are absolutely correct, I assume that my solution is correct, but isn't efficient.

Explanation:

  • nodeA: The Graph will be saved in an adjacency list. This list will contain nodes of time "nodeA"
  • nodeB: Each vertex of the graph will have one node of type "nodeB", which has it's own HashSet, which is basically the path to it, from the root node(the king's mansion)
  • Map toList: A hashmap, to find the adjacency list of a given vertex, the value of the vertex being the key of the Hashmap.
  • toNode nodeB array: To access the nodes' hashsets in O(1) time. Note that this is created due to the fact that the value of the vertices can't go above the number of vertices.
  • addToLinkedList(): "a" is the value of the vertex, and x is adjacent to it. N is the first vertex in the adjacency list of a. So, x replaces N, and N comes next to x.
  • addToList(): Creates a "nodeB" for the vertex if not created (for both a and x), and checks whether there is any list of "a" or not. If no, then it creates one, and puts the element into it's list. If yes, then the element is simply put into the list(along with the creation of a "nodeA" type object for x).
  • modifiedDFS(): Simple DFS, but is doesn't check whether the current node has been visited or not since the given graph is a tree (acyclic, and contains N-1 edges for N nodes, and connected too).
  • onWay(): If we are going towards the root, then start's hashset should contain hide, otherwise, if we're going away from the root, then hide's hashset should contain start.

Now in the main function, modifiedDFS() will take O(N) time, and the loop which runs on all the queries O(Q) time. So, a total complexity will be O(N+Q). And if 10^6 queries run in 1s (which I assume if the runtime of queries in many Online Judges, correct me if I'm wrong). So this should take 2 seconds approximately.

Is there any way to optimize the program further?
Any help apprecited.

\$\endgroup\$
  • \$\begingroup\$ try only reading input and giving output to check if it does tle because of input/output or because of algorithm \$\endgroup\$ – juvian Nov 8 '17 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.