Unsolved: Jumping Monkey & Assembly Line from SWERC

Today there will be no solution for solved problem, rather I would post my approach, code and test data for 2 unsolved problems in recent SWERC contest and you are invited find flaws in my solution.

Jumping Monkey

This is an interesting problem. I've used bitmask DP to solve it. Each state represents the possible locations of the monkey. Now if we shoot a particular tree, if there was a monkey in the tree, it will die and cannot move to neighboring tress. If the monkey was in any other tree, it will move to any of its adjacent trees (including the one we've just shot).



Another thing to note is that if the input graph is not a tree, then it will not be possible to kill the monkey as it can always move in a cycle.

I'm getting wrong answer in this problem. Here's my code -

#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++)

vector<int> adj[MAXN+2];
int dp[(1<<MAXN)+5];
int pre[(1<<MAXN)+5];
int shoot[(1<<MAXN)+5];
int n,m;

int go(int st) {
 if(dp[st] != -1) return dp[st];
 if(st == 0) return dp[st] = 0;

 int &ret = dp[st];
 ret = INF;
 int i,j,k,cur;
 int nstate;

 rep(i,n) { 
  nstate = 0;
  rep(j,n) if(j !=i && (st & (1<<j))) {
   rep(k,adj[j].size()) nstate |= (1<<adj[j][k]);
  }

  cur = go(nstate) + 1;
  if(cur < ret) {
   ret = cur;
   shoot[st] = i;
   pre[st] = nstate;
  }
 }
 return ret;
}

void print(int st) {
 if(st == 0) return;
 printf(" %d",shoot[st]);
 print(pre[st]);
}

int main()
{
 int i;
 int a,b;
 int ret;
 while(scanf(" %d %d",&n,&m)==2) {
  if(n == 0 && m == 0) break;
  assert(n>=1 && n<=21);
  memset(adj,0,sizeof(adj));
  rep(i,n) adj[i].clear();
  rep(i,m) {
   scanf(" %d %d",&a,&b);
   assert(a>=0 && a<n && b>=0 && b<n && a!=b);
   adj[a].push_back(b);
   adj[b].push_back(a);
  }
  if(m != n-1) { printf("Impossible\n"); continue; }
  memset(dp,-1,sizeof(dp));
  memset(pre,-1,sizeof(pre));
  memset(shoot,-1,sizeof(shoot));
  ret = go((1<<n)-1);
  if(ret == INF) { printf("Impossible\n"); continue; }
  assert(ret < INF);
  printf("%d:",ret);
  print((1<<n)-1); printf("\n");
 }
 return 0;
}

Here's the input I've tested on -

17 16
0 2
0 3
2 1
2 5
2 6
3 7
3 4
3 8
5 9
6 10
6 11
6 12
10 14
10 15
11 16
8 13

2 1
0 1

3 3
0 1
1 2
2 0

4 3
0 1
2 3
1 3

1 0

8 7
7 0
0 1
1 2
1 3
3 4
3 5
3 6

8 7
0 1
1 2
2 3
3 4
4 5
5 6
6 7

21 20
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20

11 10
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

12 11
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11


0 0

And here's the output -

20: 8 3 0 2 5 2 6 10 6 11 10 6 11 6 2 5 2 0 3 8
2: 0 0
Impossible
4: 1 3 3 1
1: 0
6: 0 1 3 0 1 3
12: 1 2 3 4 5 6 6 5 4 3 2 1
38: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
18: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
20: 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1

Assembly Line

This is a dynamic programming problem. The states are [start index, end index, character I want to make]. To calculate the result of each state, I've split the sequence in different positions and tried to make different characters in the two portions and then combined them to check whether it is possible for the 2 characters from each portion to make the character I want and if possible whether it is optimal in cost.

I'm getting Time Limit Exceeded in this problem. Here's my source -

#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cassert>
using namespace std;

#define INF 302345678
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define rep(i,n) for(i=0;i<(n);i++)

vector<string> parse(const string& s,const string& delim=" ") {
 vector<string>res;
 string t;
 for(int i=0;i!=s.size();i++) {
  if(delim.find(s[i]) != string::npos) {
   if(!t.empty()) {
    res.push_back(t);
    t="";
   }
  }
  else t+=s[i];
 }
 if(!t.empty()) res.push_back(t);
 return res;
}

#define MAXK 26
#define MAXN 200

int n; //input character ordering sequence length
char ch[MAXK+3]; //input character ordering sequence
int pos[200]; //position of a lower case letter in the input sequence..like pos['e'] = 1 in the 2nd sample
char tran[MAXK+3][MAXK+3]; //character part of input matrix
int cost[MAXK+3][MAXK+3]; //number part of input matrix

int dp[MAXN+2][MAXN+2][MAXK+2]; //dp table
char s[MAXN+5]; //query string
int L; //query string length

vector< pair<int,int> > from[MAXK+2]; //pairs that produces a particular character
 
int go(int st, int en, char final) {
 if(st > en) return INF;
 if(dp[st][en][final-'a'] != -1) return dp[st][en][final-'a'];
 if(st == en) {
  if(s[st] == final) return dp[st][en][final-'a'] = 0;
  return dp[st][en][final-'a'] = INF;
 }
 if(st+1 == en) { //actually don't need to include it as base condition...but just as an optimization
  if(tran[pos[s[st]]][pos[s[en]]] == final) {
   return dp[st][en][final-'a'] = cost[pos[s[st]]][pos[s[en]]];
  }
  else return dp[st][en][final-'a'] = INF;
 }

 int &ret = dp[st][en][final-'a'];
 ret = INF;
 int i,j;//,k;
 int r1,r2;
 int p = pos[final];
 for(j = st; j < en; j++) {
  rep(i,from[p].size()) {
   r1 = go(st,j,ch[from[p][i].first]);
   if(r1 == INF) continue;
   r2 = go(j+1,en,ch[from[p][i].second]);
   ret = min(ret, r1 + r2 + cost[from[p][i].first][from[p][i].second]);
  }
  /*
  rep(i,n) {
   rep(k,n) if(tran[i][k] == final) {
    r1 = go(st,j,ch[i]);
    if(r1 == INF) continue;
    r2 = go(j+1,en,ch[k]);
    ret = min(ret, r1 + r2 + cost[i][k]);
   }
  }*/
 }
 return ret;
}

int main()
{
 vector<string> t;
 int i,j;
 string res;
 int q;
 int cur, ret;
 bool f = 0;
 char temp[100];
 while(scanf("%d",&n)==1) {
  if(n == 0) break;
  if(!f) f = 1;
  else printf("\n");
  //input processing
  rep(i,n) { scanf(" %c",&ch[i]); pos[ch[i]] = i; from[i].clear(); }
  rep(i,n) rep(j,n) {
   scanf(" %s",s);
   t = parse(s,"-");
   cost[i][j] = atoi(t[0].c_str());
   tran[i][j] = t[1][0];
   from[pos[t[1][0]]].push_back( make_pair(i,j) );
  }

  //queries
  scanf(" %d",&q);
  rep(i,q) {
   scanf(" %s",s);
   L = strlen(s);
   memset(dp,-1,sizeof(dp));
   res = "";
   ret = INF;
   rep(j,n) {
    cur = go(0,L-1,ch[j]);
    if(cur < ret) {
     ret = cur;
     sprintf(temp,"%d",ret);
     res = temp;
     res += "-";
     res += ch[j];
    }
   }
   assert(ret < INF);
   printf("%s\n",res.c_str());
  }
 } 
 return 0;
}