We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Game Theory
- Deforestation
- Discussions
Deforestation
Deforestation
+ 1 comment cbuff's link and dingma129's post is really helpful, thnx^^ but if u need code:
int gr[501]; int dfs(int u, int p, vector<vector<int>>& G){ for(auto ch : G[u]){ if(ch != p) gr[u] ^= dfs(ch,u,G); } return u == 1 ? gr[u] : ++gr[u]; } string deforestation(int n, vector<vector<int>> tree) { memset(gr, 0, sizeof(gr)); vector<vector<int>> G(n+1); for(auto p : tree){ G[p[0]].push_back(p[1]); G[p[1]].push_back(p[0]); } return dfs(1,-1,G) ? "Alice" : "Bob"; }
+ 0 comments just a useful quick note about computing the nimber for such a game:
When played with a forest of “trees” (Colon Principle): When branches come together at a vertex, one may replace the branches by a non-branching stalk of length equal to their nim sum.
reference: http://web.mit.edu/sp.268/www/nim.pdf page 19
+ 3 comments Can anyone explain why Alice will select 3->4? Why can't he choose 1->2 or 1->3??
+ 0 comments import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
static int[] a,b;//0-index static int[] c;//1-index static int[] d;//1-index static int n; public static void main(String[] args) throws IOException{ new Solution().run(); } public static void dfscol(int root){ d[root]=1; for(int i=0;i<n-1;i++){ if(a[i]==root && d[b[i]]==0){ dfscol(b[i]); c[root]++; } if(b[i]==root && d[a[i]]==0){ b[i]=a[i]; a[i]=root; dfscol(b[i]); c[root]++; } } return; } public static int dfs(int root){ if(root > 0 && root <=n){ if(c[root]==0) {//leaf return 0; } else {//c[root]>0 int count =0; for(int i=0;i<n-1;i++){ if(a[i]==root){ count^=(int)(1+dfs(b[i])); } } return count; } } return 0; } public void run() throws IOException{ Scanner in = new Scanner(System.in); BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out)); int t = in.nextInt(); int i,u,v, counter; a = new int[501]; b = new int[501]; c = new int[501]; d = new int[501]; for(int tt =0;tt<t;tt++){ Arrays.fill(c,0); Arrays.fill(d,0); n = in.nextInt();//n<=500 counter = 0; for(i=0;i<n-1;i++){ u = in.nextInt();//n<=500 v = in.nextInt();//n<=500 a[i]=u; b[i]=v; } d[1]=1; dfscol(1); //dfs counter = dfs(1); //System.out.println("Node "+1+": "+counter); if(counter>0) log.write("Alice\n"); else log.write("Bob\n"); } log.flush();
} }
Load more conversations
Sort 14 Discussions, By:
Please Login in order to post a comment