11365 - Copying DNA

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

11365 - Copying DNA

Post by tobby » Sat Dec 01, 2007 7:15 pm

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.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sat Dec 01, 2007 7:22 pm

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
Last edited by rio on Sun Dec 02, 2007 3:10 pm, edited 1 time in total.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Sun Dec 02, 2007 2:50 pm

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?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Dec 02, 2007 3:10 pm

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
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Sun Dec 02, 2007 5:00 pm

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Dec 02, 2007 8:08 pm

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

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Tue Dec 04, 2007 5:50 am

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Dec 07, 2007 3:30 am

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

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby » Fri Dec 07, 2007 9:06 am

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
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 11365 - Copying DNA

Post by Angeh » Thu Sep 02, 2010 1:53 pm

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;
}
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

alofa
New poster
Posts: 2
Joined: Mon Sep 30, 2013 12:52 am

Re: 11365 - Copying DNA

Post by alofa » Thu Oct 10, 2013 1:50 am

why is the following test case returning 5.

Code: Select all

1
ACGT
AAACTTCAAAA

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11365 - Copying DNA

Post by brianfry713 » Thu Oct 10, 2013 11:49 pm

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.
Check input and AC output for thousands of problems on uDebug!

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

Re: 11365 - Copying DNA

Post by red_apricot » Thu Jul 03, 2014 4:19 pm

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.

Post Reply

Return to “Volume 113 (11300-11399)”