In this HackerRank Move the Coins problem solution Bob must determine if the first player has a winning strategy for the new tree or not. It’s possible that after Alice draws the new edge, the graph will no longer be a tree; if that happens, the question is invalid. Each question is independent, so the answer depends on the initial state of the graph (and not on previous questions).
Given the tree and the number of coins in each node, can you help Bob answer all Q questions?
Problem solution in Python.
from collections import deque
n = int(input())
G = [[int(c), 0, []] for c in input().strip().split()]
G[0][2].append(0)
parity = [True for i in range(n)]
order = [[-1,-1] for i in range(n)]
for i in range(n-1):
v1, v2 = (int(v)-1 for v in input().strip().split())
G[v1][2].append(v2)
G[v2][2].append(v1)
total = 0
pre = 0
post = 0
parent = deque([0])
while (len(parent) > 0):
node = parent.pop()
if (order[node][0] == -1):
order[node][0] = pre
pre += 1
parity[node] = not parity[G[node][1]]
if (parity[node]):
total = total ^ G[node][0]
G[node][2].remove(G[node][1])
if (len(G[node][2]) == 0):
parent.append(node)
else:
for c in G[node][2]:
G[c][1] = node
parent.append(c)
else:
order[node][1] = post
post += 1
for c in G[node][2]:
G[node][0] = G[node][0] ^ G[c][0]
if (G[G[node][1]][2][0] == node):
parent.append(G[node][1])
q = int(input())
for i in range(q):
u, v = (int(vertex)-1 for vertex in input().strip().split())
if (order[u][0] < order[v][0] and order[u][1] > order[v][1]):
print("INVALID")
elif (parity[u] == parity[v]):
newtotal = G[u][0]
if (newtotal ^ total == 0):
print("NO")
else:
print("YES")
else:
if (total == 0):
print("NO")
else:
print("YES")
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static Node[] nodes;
static int tick;
static class Node {
List<Integer> adjacents = new ArrayList<>();
int c;
int dep;
int pre;
int post;
int[] nim = new int[2];
public Node(int c) {
this.c = c;
}
}
static void dfs(int u, int d, int p) {
Node node = nodes[u];
node.nim[d] += node.c;
node.dep = d;
node.pre = tick++;
for (int v: node.adjacents) {
if (v != p) {
dfs(v, d ^ 1, u);
for (int i = 0; i < 2; i++) {
node.nim[i] ^= nodes[v].nim[i];
}
}
}
node.post = tick;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
nodes = new Node[n];
for (int i = 0; i < n; i++) {
int c = Integer.parseInt(st.nextToken());
nodes[i] = new Node(c);
}
for (int i = 0; i < n - 1; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken()) - 1;
int v = Integer.parseInt(st.nextToken()) - 1;
nodes[u].adjacents.add(v);
nodes[v].adjacents.add(u);
}
dfs(0, 0, -1);
st = new StringTokenizer(br.readLine());
int q = Integer.parseInt(st.nextToken());
while (q-- > 0) {
st = new StringTokenizer(br.readLine());
Node u = nodes[Integer.parseInt(st.nextToken()) - 1];
Node v = nodes[Integer.parseInt(st.nextToken()) - 1];
if (u.pre <= v.pre && v.pre < u.post) {
bw.write("INVALID");
} else {
int temp = (u.dep ^ v.dep) > 0 ? 0 : u.nim[0] ^ u.nim[1];
bw.write(((nodes[0].nim[1] ^ temp) > 0 ? "YES" : "NO"));
}
bw.newLine();
}
bw.close();
br.close();
}
}
Problem solution in C++.
#include<bits/stdc++.h>
using namespace std;
#define MAXN 50000
int N;
long long coin[MAXN];
long long MOVE[MAXN];
long long odd[MAXN];
long long even[MAXN];
long long level[MAXN];
long long flag[MAXN];
long long parent[MAXN][20];
vector<int> AdjList[MAXN];
bool no_cycle(int p, int q){
if (level[p] < level[q])
swap(p, q);
else
return true;
int log;
for (log = 1; 1 << log <= level[p]; log++);
log--;
for (int i = log; i >= 0; i--)
if (level[p] - (1 << i) >= level[q])
p = parent[p][i];
if ( p == q )
return false;
else
return true;
}
void rec(int v, int l, int f){
flag[v] = true;
parent[v][0] = f;
level[v] = l;
MOVE[v] = 0;
odd[v] = 0;
even[v] = coin[v];
for (size_t i=0; i<AdjList[v].size(); i++)
if ( !flag[AdjList[v][i]] ) {
rec(AdjList[v][i], l + 1, v);
odd[v] ^= even[AdjList[v][i]];
even[v] ^= odd[AdjList[v][i]];
}
}
void init(){
cin >> N;
memset(flag, 0, sizeof(flag));
for (int i=0; i<N; i++)
cin >> coin[i];
for (int i=0; i<N-1; i++) {
int a, b;
cin >> a >> b;
a--; b--;
AdjList[a].push_back(b);
AdjList[b].push_back(a);
}
for (int i=0; i<MAXN; i++)
for (int j=0; j<20; j++)
parent[i][j] = -1;
rec(0, 0, -1);
for (int j = 1; 1 << j < N; j++)
for (int i = 0; i < N; i++)
if (parent[i][j - 1] != -1)
parent[i][j] = parent[parent[i][j - 1]][j - 1];
}
void solve(){
int q;
cin >> q;
while(q--){
int u, v;
cin >> u >> v;
u--;
v--;
if ( no_cycle(u, v) ) {
long long s = odd[0];
if ( level[u] % 2 == 1)
s = s ^ even[u];
else
s = s ^ odd[u];
if ( (level[v] + 1) % 2 == 1 )
s = s ^ even[u];
else
s = s ^ odd[u];
if ( s != 0 )
cout << "YES" << endl;
else
cout << "NO" << endl;
} else
cout << "INVALID" << endl;
}
}
int main(){
init();
solve();
}
Problem solution in C.
#include <stdio.h>
#include <stdlib.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
void insert_edge(int x,int y,int w);
void preprocess();
int lca(int a,int b);
void dfs0(int u);
int a[50000],level[50000],odd[50000]={0},even[50000]={0},DP[16][50000],n;
lnode *table[50000]={0};
int main(){
int q,x,y,t,i;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",a+i);
for(i=0;i<n-1;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
preprocess();
scanf("%d",&q);
while(q--){
scanf("%d%d",&x,&y);
x--;
y--;
if(lca(x,y)==x)
printf("INVALIDn");
else{
t=odd[0];
if(level[x]%2)
t^=even[x];
else
t^=odd[x];
if(level[y]%2)
t^=odd[x];
else
t^=even[x];
if(t)
printf("YESn");
else
printf("NOn");
}
}
return 0;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void preprocess(){
int i,j;
level[0]=0;
DP[0][0]=0;
dfs0(0);
for(i=1;i<16;i++)
for(j=0;j<n;j++)
DP[i][j] = DP[i-1][DP[i-1][j]];
return;
}
int lca(int a,int b){
int i;
if(level[a]>level[b]){
i=a;
a=b;
b=i;
}
int d = level[b]-level[a];
for(i=0;i<16;i++)
if(d&(1<<i))
b=DP[i][b];
if(a==b)return a;
for(i=15;i>=0;i--)
if(DP[i][a]!=DP[i][b])
a=DP[i][a],b=DP[i][b];
return DP[0][a];
}
void dfs0(int u){
lnode *x;
even[u]^=a[u];
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u]){
DP[0][x->x]=u;
level[x->x]=level[u]+1;
dfs0(x->x);
even[u]^=odd[x->x];
odd[u]^=even[x->x];
}
return;
}
