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; }