612 - DNA Sorting

[fkrafi]

Why WA?????

Code: Select all

Solved


[Md. Mijanur Rahman]

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;
}

[mathgirl]

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;
}

[brianfry713]

Don't start the output with a blank line.

[mostafiz93]

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


[mostafiz93]

I've also checked my program with this I/O :

input : http://www.csie.nctu.edu.tw/~chchu/acm/online/v6/test/612i.txt
output : http://www.csie.nctu.edu.tw/~chchu/acm/online/v6/test/612o.txt

[brianfry713]

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

[hello]

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>::iterator

using 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;
}


[brianfry713]

Try a different problem.