LazyPay Java Question Runtime Error & TLE

This is a past hiring challenge https://www.hackerearth.com/challenges/hiring/lazypay-java-developer-hiring-challenge-2019/

Question :
Tree Play

Given a tree with N vertices and N - 1 edges. Every vertex has stone piles kept on them given on them given by array Stones. Bob and Alex plays game of Q rounds. In each round piles in path from vertex u to v are considered. Both of them play in alternate turns. In each turns, a player can choose only one pile and remove any number of stones (at least one) from that pile.The player who cannot move is considered to lose the game. Bob always start first, Print winner after every round if both of them play optimally.

Input
First line : N,Q, no. of vertices and no. of round respectively
Second line : N integers defining array stones.
Next N-1 lines : u and v, meaning there is an edge between vertex u and u.
Next Q lines : u and v for i^{th} round.

Output
For each round print winner as Alex or Bob in new line.

Constraints

1 \leq N, Q \leq 2 \times 10^5
1 \leq u, v \leq N
1 \leq Stones_i \leq 10^5

Sample Input
8 \> 4
2 \> 3 \> 4 \> 4 \> 2 \> 3 \> 2 \> 1
1 \> 2
1 \> 3
2 \> 4
2 \> 5
5 \> 6
6 \> 7
4 \> 8
3 \> 6
4 \> 4
1 \> 6
4 \> 7

Sample Output

Bob
Bob
Alex
Bob

Explanation

For round two there is only one pile containing 4 stones. Bob will pick up all the stones and winds the game as Alex can’t pick up further.

Time limit : 1 sec.

I found out clearly this is nim game https://www.geeksforgeeks.org/combinatorial-game-theory-set-2-game-nim/

My approach :

So I have to just xor the values of each nodes in the path and check whether it is zero or not. If it is 0 then Alex win otherwise Bob.

I am getting Runtime error in many case and TLE in others. I don’t understand what is wrong in my code.

My Solution :

    static class Pair {
        boolean isPath;  //  whether the path exits or not
        int xor;  // xor value
        Pair(boolean isPath, int xor) {  // Constructor
            this.isPath = isPath;
            this.xor = xor;
        }
    }
    static class Graph {
        int V;
        LinkedList<Integer>[] adj;
        int[] val;
        Graph(int V) {
            this.V = V;
            adj = new LinkedList[V + 1];
            for (int i = 0; i <= V; ++i) {
                adj[i] = new LinkedList<>();
            }
            val = new int[V + 1];
        }

        void addEdge(int u, int v) {  // undirected graph edges u to v and backedge v to u
            adj[u].add(v);
            adj[v].add(u);
        }

        Pair DepthFirstSearch(int s, int d, boolean[] visited) {
            visited[s] = true;

            if(s == d) {
                return new Pair(true, val[s]);  // is we reach destination then return Pair(path exits , value of the path)
            }


            for (int i = 0; i < adj[s].size(); ++i) {  // calling on adjacency list
                if(!visited[adj[s].get(i)]) {
                    Pair temp = DepthFirstSearch(adj[s].get(i), d, visited);
                    if(temp.isPath) {
                        return new Pair(true , temp.xor ^ val[s]);  // xor the current node value with every child node value in path
                    }
                }
            }

            return new Pair(false, 0); // path does not exits 

        }
        boolean DFS(int s, int d) {  // dfs from source to destination
            boolean[] traversed = new boolean[V + 1];  // visited array
            Pair p = DepthFirstSearch(s, d, traversed);  // calling dfs
            return p.xor == 0;  // if xor value is 0 or not
        }
    }

/*
8 4
2 3 4 4 2 3 2 1
1 2
1 3
2 4
2 5
5 6
6 7
4 8
3 6
4 4
1 6
4 7

*/
static class Code {

    private void solve(InputReader in, OutputWriter out) {
        int n = in.readInt();  // number of vertices in tree
        int query = in.readInt();  // number of query
        Graph graph = new Graph(n);  // initialize tree with n nodes
        for(int i = 1; i <= n; ++i) {
            graph.val[i] = in.readInt();  // initialize value of each node
        }
        for(int i = 0; i < n - 1; ++i) {
            graph.addEdge(in.readInt(), in.readInt());  // add edges
        }

        for(int i = 0; i < query; ++i) {
            if(graph.DFS(in.readInt(), in.readInt())) {  
                out.printLine("Alex");
            }
            else {
                out.printLine("Bob");
            }
        }
    }
}

you have to use LCA(lowest common ancestor) in log(n)

first, precompute the xor-sum form root to that node using DFS then in queries compute LCA of the two nodes.

nim = xorsum[u] ^ xorsum[v] ^ stones[lca(u,v)]

now use nim game concept.

1 Like