11365 - Copying DNA

[tobby]

Could anyone give me some good ideas of how to solve this problem efficiently? My BFS is slow; it gets TLE.

Do you have some very good heuristic functions? Or do you have any good insights? Thanks.

[rio]

I haven't solve it yet, but I think DP would work.
Maximum 2^18 (= 262144) states, which is feasible.

EDIT : DP worked. But simpled implemented DP may get TLE. You need a little device.
-----
Rio

[tobby]

Any bigger hints?

I think a BFS with bitmask works just like DP, doesn't it?

I think it makes sense to do all "copying from S" before any "copying from T". Would this idea help cut down the run time?

[rio]

You're right. BFS and DP is same for this problem.
I just categorized it as DP.

I didn't try, but A* or IDA* might work.
-----
Rio

[tobby]

Thanks. I get ac with IDA*. My BFS solution still times out.

[sclo]

I did it with straight DP (BFS) with a bit of pruning.

[tobby]

Could anyone share their tricks in how to prune?

I guess my way to find neighbouring states is too slow. My runtime is 1.3 s.

[sclo]

The solution are posted at the NCPC 2007 website, so I think you can study their pruning strategies.

[tobby]

I cannot download the solution sketches pdf file from the official site. But I improved my code a bit and now it runs under 1 second.
My BFS takes 2.5 seconds.

[Angeh]

HI Experts, my BFS Solution Code Exceeds Time Limit
Could Some One Give some Hints For the Solution ...
or send his code for me ( angeh.a2@gmail.com )
Thanks Soooo much ...

Code: Select all

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
char str[20],target[20];
long long toi(char c){
	switch (c){
		case 'A':return 1L;
		case 'C':return 2L;
		case 'G':return 3L;
		case 'T':return 4L;
		default:return 0L;
	}
}
long long encode(char str[],int n){
	long long res=0;
	FOR(i,n)res|= (toi(str[n-i-1])<<(i*3));
	return res;
}
void print(long long in ,int n){
	for(int i=n-1 ;i>=0;--i)
		printf("%d ", ((in>>(i*3))&7) );
	putchar('\n');
}
long long reverse(long long in,int n ){
	long long res=0;
	FOR(i,n)	res = (((in>>(3*i))&7)|(res<<3));
	return res;
}
int main(){
	int cas;
	freopen("in.txt","r",stdin);
	scanf("%d",&cas);
	FOR(ca,cas){
		scanf("%s%s",str,target);
		int slen=strlen(str);
		int tlen=strlen(target);
		int t1=0,t2=0;
		FOR(i,slen) t1|= (toi(str[i])<< (4*toi(str[i]) )) ;
		FOR(i,tlen) t2|= (toi(target[i])<< (4*toi(target[i]) )) ;
		if(t1!=t2)printf("impossible\n");
		else{
			queue<long long> Q;
			map<long long , int> mark;
			//map<long long , long long > parent;
			//puts(str);
			long long S=encode(str,slen);
			long long SR=reverse(S,slen);
			long long Goal=encode(target,tlen);
			//printf("%lld %lld %lld \n",S,SR,Goal);
			long long temp=0;
			Q.push(temp);
			mark[temp]=0;
			//parent[temp]=-1;
			//BFS
			while(Q.empty()==false ){
				temp = Q.front(); Q.pop();
				int f=0;
				long long Trev = reverse(temp,tlen);
				for(int l=tlen;l>0 && f<10 ;--l){
					bool found = false;
					FOR(ll,tlen-l+1){
						long long T=temp;
						if( ((T>>(3*ll))&((1L<<l*3)-1))!=0)continue;
						else {
							long long G=((Goal>>(3*ll))&((1L<<l*3)-1));
							FOR(ls,slen-l+1){
								long long ss=((S>>(3*ls))&((1L<<l*3)-1));
								if( G==ss ){
									long long TT= (T|(G<<(3*ll)));
									if(mark.count(TT))continue;
									found=true;
									Q.push(TT);		
									mark[TT]=mark[T]+1;
									//parent[TT]=T;
								}
							}
							FOR(ls,slen-l+1){
								long long ss=((SR>>(3*ls))&((1L<<l*3)-1));
								if( G==ss ){
									long long TT= (T|(G<<(3*ll)));
									if(mark.count(TT))continue;
									Q.push(TT);found=true;		
									mark[TT]=mark[T]+1;
									//parent[TT]=T;
								}
							}

							FOR(ls,tlen-l+1){
								long long ss=((temp>>(3*ls))&((1L<<l*3)-1));
								if( G==ss ){
									long long TT= (T|(G<<(3*ll)));
									if(mark.count(TT))continue;
									Q.push(TT);		found=true;
									mark[TT]=mark[T]+1;			
									//parent[TT]=T;
								}
							}
							FOR(ls,tlen-l+1){
								long long ss=((Trev>>(3*ls))&((1L<<l*3)-1));
								if( G==ss ){
									long long TT= (T|(G<<(3*ll)));
									if(mark.count(TT))continue;
									Q.push(TT);		found=true;
									mark[TT]=mark[T]+1;
									//parent[TT]=T;
								}
							}
							if( mark.count(Goal) )break;
						}
					}
					if(found)f++;
				}
			}
			if(mark.count(Goal)){
				printf("%d\n",mark[Goal]);
				/*while( Goal!=-1 ){
					print(Goal,tlen);
					Goal=parent[Goal];
				}*/
			}else printf("notFound\n");
		}
	}
	return 0;
}

[alofa]

why is the following test case returning 5.

Code: Select all

1
ACGT
AAACTTCAAAA

[brianfry713]

Code: Select all

S=ACGT

Get ......CA... by copying and reversing "AC" from S.
Get .....TCA... by copying "T" from S.
Get .....TCAA.. by copying "A" from S.
Get .....TCAAAA by copying "AA" from the partial T.
Get AAACTTCAAAA by copying and reversing "TCAAA" from the partial T.

[red_apricot]

My code outputs 3 for the following two cases

Code: Select all

2
AGCAT
ACACCACAT
AGCCAT
ACACCACAT

Since the source string S of the second case is richer than that of the first case, my output does make sense. Still, uvatoolkit.com replies "3 4".
My code gets WA. How come?

EDIT: On my way to the MWE I found that uvatoolkit's output for the following is also "3 4"...

Code: Select all

2
CAT
ACACCACAT
CCAT
ACACCACAT

EDIT: Got AC now with a BFS. i.e. the judges' data does not contain such cases.