11365 - Copying DNA
Moderator: Board moderators
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.
Do you have some very good heuristic functions? Or do you have any good insights? Thanks.
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
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.
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 ...
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;)
Beliefs are not facts, believe what you need to believe;)
Re: 11365 - Copying DNA
why is the following test case returning 5.
Code: Select all
1
ACGT
AAACTTCAAAA
-
- 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!
-
- 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
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"...
EDIT: Got AC now with a BFS. i.e. the judges' data does not contain such cases.
Code: Select all
2
AGCAT
ACACCACAT
AGCCAT
ACACCACAT
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