## 612 - DNA Sorting

Moderator: Board moderators

smsampark
New poster
Posts: 1
Joined: Thu Aug 12, 2010 9:35 am

### 612 - DNA Sorting

Hi all,

My code works fine on my computer but gets a runtime error on UVa. Could anyone please suggest what is wrong?

import java.util.*;
import java.io.*;

class DNASorting
{
public static void main(String[] args) throws IOException
{

int M = Integer.parseInt(st.nextToken());
int n, b;
String[] list;
int[] count;

for(int i = 0; i < M; i++)
{
n = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());

list = new String;
count = new int;
for(int j = 0; j < b; j++)
{
}

for(int j = 0; j < b; j++)
{
for(int x = 0; x < n-1; x++)
for(int y = x+1; y < n; y++)
if(list[j].charAt(x) > list[j].charAt(y))
count[j]++;
}
quicksort(list, count, 0, b-1);
for(int j = 0; j < b; j++)
System.out.println(list[j]);
if(i != M-1)
System.out.println();
}

f.close();
System.exit(0);

}

static void quicksort(String[] a, int[] b, int low, int high)
{
int i = low, j = high;
int pivot = b[(low+high)/2];

while (i <= j)
{
while (b < pivot)
{
i++;
}
while (b[j] > pivot)
{
j--;
}
if (i <= j)
{
exchange(a,b,i, j);
i++;
j--;
}
}
if (low < j)
quicksort(a,b,low, j);
if (i < high)
quicksort(a,b,i, high);
}

static void exchange(String[] a, int[] b, int i, int j)
{
String t = a;
int t2 = b;
a = a[j];
b = b[j];
a[j] = t;
b[j] = t2;
}

}

reyan
New poster
Posts: 2
Joined: Tue Jul 27, 2010 8:50 am

### Re: 612 - DNA Sorting - Java RunTime Error

please somebody tell me why i get wrong answer from the following code
#include <iostream>
#include <vector>
using namespace std;
#include <stdio.h>
char in[1100][600];
char out1[1100],out2[1100],out3;
int insert_sort(char arr1[600], int size)
{
char arr[600];
int i,j,key,c;
c=0;
for(j=0;j<size;j++)
{
arr[j]=arr1[j];
}
arr[j]='\0';
for(j=1;j<size;j++)
{
key=arr[j];
i=j-1;
while((i>=0)&&(arr>key))
{
arr[i+1]=arr;
i--;
c++;
}
arr[i+1]=key;
}
//cout<<c;
return c;
}
void take_input(int a)
{
int i;
for(i=0;i<a;i++)
{
gets(in);
}
}
int main ()
{
int i,j,k,l,m,n,q,r;
bool a=false;
bool a2=false;
scanf("%d",&i);
getchar();
while(i)
{
getchar();
scanf("%d",&j);
scanf("%d",&k);
getchar();
take_input(k);
//cout<<j<<k;
//cout<<in[0]<<endl<<in[1]<<endl<<in[2]<<endl;
for(l=0;l<k;l++)
{
m=insert_sort(in[l],j);
if(out3)
{
out1[out3]=l;
out2[out3]=m;
out3++;
n=out3-2;
q=out1[out3-1];
r=out2[out3-1];
while((n>=0)&&(out2[n]<=m))
{
out1[n+1]=out1[n];
out2[n+1]=out2[n];
n--;
}
out1[n+1]=q;
out2[n+1]=r;
}
else
{
out1[out3]=l;
out2[out3]=m;
out3++;
}
}
for(l=k-1;l>=0;l--)
{
if(a)cout<<endl;
if(!a)
{
a=true;
}
cout<<in[out1[l]];
}
out3=0;
i--;
}
return 0;
}

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

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

Md. Mijanur Rahman
New poster
Posts: 9
Joined: Thu Nov 13, 2008 2:08 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;
}``````

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 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;
}``````

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

### Re: 612 - DNA Sorting

Don't start the output with a blank line.
Check input and AC output for thousands of problems on uDebug!

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

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

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

### Re: 612 - DNA Sorting

Use stable_sort() instead of sort() on line 94.
Check input and AC output for thousands of problems on uDebug!

sabrina_tuli
New poster
Posts: 1
Joined: Fri May 31, 2013 4:14 pm

### Re: 612 - DNA Sorting - Java RunTime Error

I am also getting runtime error, pls anyone tell me where is the bug? is there any critical input output?
#include<stdio.h>
#include<string.h>
int main()
{
long i,j,m,n,c,chng=0,sort[60],var;
char str[60][60],temp[60][60],t,final[60];
while(1)
{
scanf("%ld %ld",&n,&m);
for(i=0;i<m;i++)
{
scanf("%s",&str);
}
for(i=0;i<m;i++)
{
c=0;
strcpy(temp,str);
while(c<=n)
{
for(j=0;j<n-1;j++)
{
if(temp[j]>temp[j+1])
{
chng++;
t=temp[j];
temp[j]=temp[j+1];
temp[j+1]=t;
}
}
c++;
}
sort=chng;
chng=0;
}
for(i=0;i<m;i++)
for(j=0;j<m-1;j++)
{
if(sort[j]>sort[j+1])
{
var=sort[j];
sort[j]=sort[j+1];
sort[j+1]=var;
strcpy(final,str[j]);
strcpy(str[j],str[j+1]);
strcpy(str[j+1],final);
}
}
for(i=0;i<m;i++)
{
printf("%s\n",str[i]);
}

}
return 0;
}

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

### Re: 612 - DNA Sorting - Java RunTime Error

Run your code on the sample input.
Check input and AC output for thousands of problems on uDebug!

hello
New poster
Posts: 25
Joined: Sun Mar 10, 2013 7:29 pm

### Re: 612 - DNA Sorting

Why Submission Error ...... ?
Last edited by hello on Thu Jun 20, 2013 4:00 am, edited 1 time in total.

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

### Re: 612 - DNA Sorting

Try a different problem.
Check input and AC output for thousands of problems on uDebug!

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

### Re: 612 - DNA Sorting

Input:

Code: Select all

``````10

7 5
CTGAGCC
GCCACGG
TATGCGT
ATCTCGT
GGCTGTT

7 2
GTAATCG
AGGATAG

5 5
AGATC
TATGT
AACTC
TCCTC
AGCGC

1 3
C
T
T

6 1
ATTCCT

6 3
CCAAGC
TTATGA
AACCCC

8 7
GACGTGTG
AGGCTCCA
AGTGAGGA
GTTTCAGT
ATGTAAAA
GCCAAAAA
CAGCGTTC

3 9
GAC
TAC
CGG
TGG
TTT
CTT
CAA
AAG
TGA

5 8
TAATC
TTACA
GGCCA
GCCAG
GAGGA
TAGTC
ACCGC
AAGAC

3 6
TAA
AGC
CGT
TCG
GCA
GAT
``````
AC output:

Code: Select all

``````GGCTGTT
ATCTCGT
GCCACGG
TATGCGT
CTGAGCC

AGGATAG
GTAATCG

AACTC
AGATC
TATGT
AGCGC
TCCTC

C
T
T

ATTCCT

AACCCC
CCAAGC
TTATGA

GACGTGTG
CAGCGTTC
AGTGAGGA
GTTTCAGT
ATGTAAAA
AGGCTCCA
GCCAAAAA

CGG
TTT
CTT
AAG
GAC
TAC
TGG
CAA
TGA

ACCGC
AAGAC
TAATC
GAGGA
GCCAG
TAGTC
TTACA
GGCCA

CGT
AGC
GAT
TAA
TCG
GCA
``````
Check input and AC output for thousands of problems on uDebug!

dennisorz
New poster
Posts: 9
Joined: Wed Aug 14, 2013 6:04 pm

### Help!612 WA!why?

Code: Select all

``````#include<iostream>
#include<string.h>
#include<stdio.h>
#include<vector>
using namespace std;
vector<char> DNA[101];
int rank[100][2];
void initial(int n,int m){
for(int i=0;i<m;i++){
rank[i][0]=0;
rank[i][1]=i;
}
for(int j=0;j<m;j++)
DNA[j].clear();
}
void func(int n,int m){
int count=0;
for(int i=0;i<m;i++){
for(int x=0;x<n;x++){
for(int y=x+1;y<n;y++){
if((int)DNA[i][x]>(int)DNA[i][y])
count++;
}
}
rank[i][0]=count;
count=0;
}
}
void bubblesort(int n)
{
int i, j, temp, a;
for (i = n - 1; i > 0; i--)
{
for (j = 0; j <= i - 1; j++)
{
if (rank[j][0] > rank[j + 1][0])
{
temp = rank[j][1];
a	 = rank[j][0];
rank[j][1] = rank[j + 1][1];
rank[j][0] = rank[j + 1][0];
rank[j + 1][1] = temp;
rank[j + 1][0] = a;
}
}
}
}
void print(int m){

for(int i=0;i<m;i++){
for(int j=0;j<DNA[rank[i][1]].size();j++)
cout <<DNA[rank[i][1]][j];
cout<<endl;
}

}
int main(){
int n,m,C;
int f=0;
char s;
cin>>C;
for(int i=0;i<100;i++)
rank[i][1]=i;
for(int i=0;i<C;i++){
if(f==1)
cout<<endl;
cin>>n>>m;
for(int j=0;j<m;j++){
for(int k=0;k<n;k++){
cin>>s;
DNA[j].push_back(s);
}
}
func(n,m);
bubblesort(m);
cout<<endl;
print(m);
initial(n,m);
}
return 0;
} ``````