Page 1 of 1

11365 - Copying DNA

Posted: Sat Dec 01, 2007 7:15 pm
by 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.

Posted: Sat Dec 01, 2007 7:22 pm
by 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

Posted: Sun Dec 02, 2007 2:50 pm
by 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?

Posted: Sun Dec 02, 2007 3:10 pm
by 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

Posted: Sun Dec 02, 2007 5:00 pm
by tobby
Thanks. I get ac with IDA*. My BFS solution still times out. :(

Posted: Sun Dec 02, 2007 8:08 pm
by sclo
I did it with straight DP (BFS) with a bit of pruning.

Posted: Tue Dec 04, 2007 5:50 am
by 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.

Posted: Fri Dec 07, 2007 3:30 am
by sclo
The solution are posted at the NCPC 2007 website, so I think you can study their pruning strategies.

Posted: Fri Dec 07, 2007 9:06 am
by 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.

Re: 11365 - Copying DNA

Posted: Thu Sep 02, 2010 1:53 pm
by 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;
}

Re: 11365 - Copying DNA

Posted: Thu Oct 10, 2013 1:50 am
by alofa
why is the following test case returning 5.

Code: Select all

1
ACGT
AAACTTCAAAA

Re: 11365 - Copying DNA

Posted: Thu Oct 10, 2013 11:49 pm
by 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.

Re: 11365 - Copying DNA

Posted: Thu Jul 03, 2014 4:19 pm
by 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.