This is a past hiring challenge 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 Combinatorial Game Theory | Set 2 (Game of Nim) - GeeksforGeeks
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");
}
}
}
}