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

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

### 11365 - Copying DNA

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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
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:
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
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:
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
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

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

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

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

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.