[Practice Mode] HackerCup-2013 Round-1 :: Security

Lession-7: Match finding is always an easy job, If you know HopCraft-Karp algorithm.

Lession-8: Lexicographic means Lexicographic, nothing else. You have a very small meta-dictionary Keep that in Mind. :P

Lession-9: Continue to read standard algorithms. :D

Lession-10: If you think that it can be fixed, It can be fixed.

// =====================================================================================
//       Filename:  security.cpp
//    Description:  
//        Created:  02/03/2013 01:22:50 AM
//         Author:  BrOkEN@!
// ====================================================================================

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>
#include<ctime>

#define TIMER 1
#define NIL 0
#define INFINITE 1000
#define KMAX 101
#define MMAX 51
#define FOR(i,a,b) for(typeof(a) i=(a); i <= (b); i++) 
using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;
typedef set<VI> vS;

char k1[KMAX],k2[KMAX];
int m=0,l=0;
bool dp[MMAX][MMAX];
int H[2*MMAX][3];



bool compare(int a,int b){
 int x=l*a,y=l*b;
 for(int i=0;i<l;i++){
  if( (k1[x+i]!='?') && (k2[y+i]!='?') && (k1[x+i]!=k2[y+i])){
   return false;
  }
 }
 return true;
}


bool bfs(){
 queue<int> Q;
 FOR(v,1,m){
  if(H[v][1]==NIL){
   H[v][0]=0;
   Q.push(v);
  }else{
   H[v][0]=INFINITE;
  }
 }
 H[NIL][0]=INFINITE;
 while(!Q.empty()){
  int v=Q.front();Q.pop();
  if(H[v][0] < H[NIL][0]){
   FOR(u,1,m){
    if(v<=m && dp[v-1][u-1] && H[H[u+m][2]][0]==INFINITE){
     H[H[u+m][2]][0]=H[v][0]+1;
     Q.push(H[u+m][2]);
    }else if(v>m && dp[u-1][v%m -1] && H[H[u][2]][0]==INFINITE){
     H[H[u][2]][0]=H[v][0]+1;
     Q.push(H[u][2]);
    }
   }
  }
 }
 return (H[NIL][0]!=INFINITE);
}


bool dfs(int v){
 if(v!=NIL){
  FOR(u,1,m){
   if(v<=m && dp[v-1][u-1] && (H[H[u+m][2]][0]==H[v][0]+1) && dfs(H[u+m][2])){
    H[u+m][2]=v;
    H[v][1]=u+m;
    return true;
   }else if(v>m && dp[u-1][v%m -1] && (H[H[u][2]][0]==H[v][0]+1) && dfs(H[u][2])){
    H[u][2]=v;
    H[v][1]=u;
    return true;
   }
  }
  H[v][0]=INFINITE;
  return false;
 }
 return true;
}

bool hopCK(){
 FOR(i,0,2*m){H[i][0]=INFINITE;H[i][1]=NIL;H[i][2]=NIL;}
 
 int matching=0;
 
 while(bfs()){
  FOR(v,1,m){
   if((H[v][1]==NIL) && dfs(v)){ matching++; }
  }
 }

 return (matching==m); 
}

bool solve(){
 l=strlen(k1)/m;
 
 FOR(i,0,m-1){FOR(j,0,m-1){dp[i][j]=compare(i,j);}}

 if(!hopCK()){return false;} // Do you there won't be a matching exists, then just quit :P

 FOR(i,0,strlen(k1)){
  if(k1[i]=='?'){
   k1[i]='a';
   while(k1[i]<='f'){ 
    FOR(j,0,m-1){dp[i/l][j]=compare(i/l,j);}
    if(hopCK()){ break; }
    k1[i]++;
   }
   if(k1[i]=='g'){ return false; }
  }
 }
 
 return true;
}

int main(){
 clock_t t=clock(); 
 int T=0;
 scanf("%d",&T);
 FOR(t,1,T){
  scanf("%d\n%s\n%s",&m,k1,k2);
  if( solve())
   printf("Case #%d: %s\n",t,k1);
  else
   printf("Case #%d: IMPOSSIBLE\n",t);
 }
  
 t=clock()-t;
 printf ("It took me %ld clicks (%f seconds).\n",t,((float)t)/CLOCKS_PER_SEC); 
 return 0;
}