btw, I don't think you can solve this in this approach, because, in this approach, the nodes will be discovered in depth-first order.So I resorted to good old Breadth First Search and my program got accepted in 4.678 seconds which was worst among others. I tried to optimize it in all possible ways (except for IO optimization). The run times and tweaks in my next submissions were -
Let's say, the nodes are discovered in this order:
v1 v2 v3 v4 v5 v6 v7 ... vp .. vq
Let's say, vq has only one next state, vp.
So, dp[vp] = INF
Now, let's assume, it is possible to reach vp in a shorter path:
v1 v2' v3' ... vq
now, it can visit vp, but since dp[vq] has already been calculated as INF, it will not proceed any further. So, this may lead to a suboptimal solution (or probably no solution)
Runtime | Optimizations |
---|---|
4.100 | Stopped shooting at positions where there is no monkey |
1.570 | Converted the vector to simple array |
0.709 | Converted all the data types to the most efficient possible [integers to chars for index variables, result array etc.] |
0.693 | Converting the most used variables to register |
0.723 | At this stage I tried to pre-compute for each integer the positions where it has a '1' bit and store those positions in an array. This really backfired in spite of reduction in loop instructions as array indexing was increased |
0.281 | Here, I've observed that I can remove one inner loop. Instead of shooting one tree at a time, I can shoot all the tree at once and later remove the effect of an particular tree to get the state for that tree |
One important note, I've found that even on a tree (the graph is tree), it is sometimes not possible to kill the monkey. I can't think such a case. Can you find any?
Here's my final source code -
/* Problem Name : Jumping Monkey Problem Number : Live Archive 4959 Link : http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4959 Problem Type : BFS, Optimization Difficulty : 7 / 10 Interest : 8 / 10 Complexity : O(N*2^N) Date : November 29, 2010 */ #include<vector> #include<cstdio> #include<cassert> using namespace std; #define MAXN 21 #define INF 10234567 #define min(a,b) (((a) < (b)) ? (a) : (b)) #define rep(i,n) for(i=0;i<(n);i++) char d[(1<<MAXN)]; //distance array...final output int pre[(1<<MAXN)]; char shoot[(1<<MAXN)]; char n; int m; int Q[(1<<MAXN)]; char adj[MAXN+2][MAXN+2];//adjacency list in array form char ct[MAXN+2]; // counter for adjacency list //4.678 -> 4.100 -> 1.570 -> .709-> .693 -> .723 -> 0.281 char counter[MAXN+2]; int bfs() { register int sz = 0, cur = 0; register char i,j; register int st, nstate, cur_state; Q[sz++] = (1<<n) - 1; memset(d,-1,sizeof(d)); d[(1<<n)-1] = 0; while(cur < sz) { st = Q[cur++]; memset(counter,0,sizeof(counter)); cur_state = 0; rep(i,n) if(st & (1<<i)) { rep(j,ct[i]) { counter[adj[i][j]]++; cur_state |= (1<<adj[i][j]); } } rep(i,n) if(st & (1<<i)) { nstate = cur_state; rep(j,ct[i]) { if(counter[adj[i][j]]-1<=0) nstate &= ~(1<<adj[i][j]); } if(d[nstate] == -1) { d[nstate] = d[st] + 1; Q[sz++] = nstate; pre[nstate] = st; shoot[nstate] = i; if(nstate == 0) return d[nstate]; } } } return INF; } void print(int st) { if(st == (1<<n)-1) return; print(pre[st]); printf(" %d",shoot[st]); } int main() { int i; int a,b; int ret; while(scanf(" %d %d",&n,&m)==2) { if(n == 0 && m == 0) break; memset(adj,0,sizeof(adj)); rep(i,n) ct[i] = 0; rep(i,m) { scanf(" %d %d",&a,&b); adj[a][ct[a]++] = b; adj[b][ct[b]++] = a; } if(m != n-1) { printf("Impossible\n"); continue; } ret = bfs(); if(ret == INF) { printf("Impossible\n"); continue; } printf("%d:",ret); print(0); printf("\n"); } return 0; }
In response to "
ReplyDeleteOne important note, I've found that even on a tree (the graph is tree), it is sometimes not possible to kill the monkey. I can't think such a case. Can you find any?
":
A tree with 3 branches of 3 nodes each, connected to a central node,
cannot be solved:
/-c--d--e
a--f--g--h
\-i--j--k