## 612 - DNA Sorting

Moderator: Board moderators

### Re: 612 - DNA Sorting

Why WA?????
Code: Select all
`Solved`
Last edited by fkrafi on Tue Mar 01, 2011 2:43 pm, edited 1 time in total.
fkrafi
New poster

Posts: 13
Joined: Wed Sep 15, 2010 1:36 pm

### Re: 612 - DNA Sorting

My mind is out..Why WA. I've got it 10 times.
but it seems ok. Plz Plz Plz help me.
Here is my code.
Code: Select all
`#include<stdio.h>int main(){  char a[105][105],ch;  int b[105][2]={0},i,j,n,m,p,test;  scanf("%d",&test);     for(int k=1;k<=test;k++)  {        scanf("%d %d",&n,&m);      ch=getchar();    for(i=0;i<m;i++)   {   for(j=0;j<n;j++)           scanf("%c",&a[i][j]);         ch=getchar();   }     for(p=0;p<m;p++)   {   b[p][0]=p;      for(i=0;i<n-1;i++)        for(j=i+1;j<n;j++)           if(a[p][i]>a[p][j])b[p][1]++;                              }   for(j=1;j<m;j++)      {      int ins=b[j][1],t=b[j][0];      i=j-1;      while((i>=0) && (ins<b[i][1]))         {         b[i+1][1]=b[i][1];b[i+1][0]=b[i][0];         i=i-1;         }      b[i+1][1]=ins;b[i+1][0]=t;      }   for(i=0;i<m;i++)   {     int x=b[i][0];     for(j=0;j<n;j++)                     printf("%c",a[x][j]);     printf("\n");    } if((k>=1)&&(k<test))printf("\n");  }   return 0;}`
Md. Mijanur Rahman
New poster

Posts: 9
Joined: Thu Nov 13, 2008 2:08 pm

### Re: 612 - DNA Sorting

I checked my code with sample I/O and the inputs posted previously. Can someone pls tell me why I m getting WA ?

Code: Select all
`#include<vector>#include<iostream>#include<math.h>#include<string>#include<algorithm>#include<stdio.h>using namespace std;class node{public:   string a;   int inver;   node(string,int);};node::node(string i,int y){   a = i;   inver = y;}bool compare(const node& a,const node& b){   return a.inver < b.inver;}int merge(string& a,int p,int q,int r){   int n1 = q - p + 1;   int n2  = r - q;   string l,right;   l = a.substr(p,n1);   right = a.substr(q+1,n2);   int i=0,j=0;   int inversions = 0;   bool counted = false;   for(int k = p; k <= r;k++)   {      if(!counted && ( (i >= l.length() && j < right.length()) || (j < right.length() && right[j] < l[i]) ) )      {            inversions = inversions + n1 - i;         counted = true;      }      if(j >= right.length() || (i<l.length() && l[i] <= right[j]))      {         a[k] = l[i];         i++;      }      else if(i >= l.length() || (j<right.length() && l[i] > right[j]))      {         a[k] = right[j];         j = j + 1;         counted = false;      }   }   return inversions;}int inversions(string& a,int p,int r){   int inver = 0;   if(p < r)   {      int q = floor((double)(p+r)/2);      inver = inver + inversions(a,p,q);      inver = inver + inversions(a,q+1,r);      inver = inver + merge(a,p,q,r);   }   return inver;}int main(){   int t,re;   re = scanf("%d",&t);   string empty;   bool first = false;   while(t--)   {      getline(cin,empty);      getline(cin,empty);      string a;      int n,m;      re = scanf("%d %d",&n,&m);      vector<node> input;      while(m--)      {         cin >> a;         string copy(a);         int i = inversions(copy,0,n-1);         input.push_back(node(a,i));      }      stable_sort(input.begin(),input.end(),compare);      if(first)         first = false;      else         printf("\n");      for(int i=0;i<input.size();i++)         cout << input[i].a << "\n";   }   return 0;}`
mathgirl
New poster

Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

### Re: 612 - DNA Sorting

Don't start the output with a blank line.
brianfry713
Guru

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

### Re: 612 - DNA Sorting

I'm getting WA in this problem.
I used divide and conquer algorithm to find the inversion number and then sorted the strings accordingly.
can anyone find any bug in my code?

here is my code:

Code: Select all
`removed`
Last edited by mostafiz93 on Tue Jul 03, 2012 11:40 am, edited 1 time in total.
mostafiz93
New poster

Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 612 - DNA Sorting

mostafiz93
New poster

Posts: 31
Joined: Thu Nov 24, 2011 12:08 am

### Re: 612 - DNA Sorting

Use stable_sort() instead of sort() on line 94.
brianfry713
Guru

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

### Re: 612 - DNA Sorting

Why Submission Error ...... ?
Code: Select all
`#include<cstdio>#include<sstream>#include<cstdlib>#include<cctype>#include<cmath>#include<algorithm>#include<set>#include<queue>#include<stack>#include<list>#include<iostream>#include<fstream>#include<numeric>#include<string>#include<vector>#include<cstring>#include<map>#include<iterator>#define LLU long long unsigned int#define LLD long long double#define FOR(i,N) for(int i=0;i<(N);i++)#define Vec vector<int>#define Vit vector<int>::iteratorusing namespace std;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int i=0;int flag=0;scanf("%d",&i);vector<int>v; map<string,int>PM;   int l,n;   while(i--){        cout<<endl;        scanf("%d%d\n",&l,&n);    v.clear();    for(int i=0;i<n;i++){    string s;    getline(cin,s);   // map<string,int>MP;    int count=0;    for(int j=0;j<l;j++)        {                //            cout<<s[j]<<" "<<endl;            for(int m=j+1;m<l;m++){                if(s[j]>s[m]){                        count++;            //                        cout<<s[m]<<count<<" ";                }            }        //            cout<<endl<<count<<endl;        }       // MP[s]=count;        v.push_back(count);        PM[s]=count;    }   // map<int,string>PM = flip_map(MP);   sort(v.begin(),v.end());   for(int i=0;i<n;i++){  for(map<string,int>::iterator it=PM.begin();it!=PM.end();it++)        if(v[i]==it->second)cout<<it->first<<endl;;        }   }    return 0;}`
hello
New poster

Posts: 7
Joined: Sun Mar 10, 2013 7:29 pm

### Re: 612 - DNA Sorting

Try a different problem.
brianfry713
Guru

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

Previous