Page 7 of 9

612 - DNA Sorting

Posted: Thu Aug 12, 2010 9:38 am
by smsampark
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
{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(f.readLine());

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

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

list = new String;
count = new int;
for(int j = 0; j < b; j++)
{
list[j] = f.readLine().trim();
}

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

}

Re: 612 - DNA Sorting - Java RunTime Error

Posted: Wed Sep 08, 2010 3:36 pm
by reyan
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;
}

Re: 612 - DNA Sorting

Posted: Wed Oct 06, 2010 7:58 pm
by fkrafi
Why WA?????

Code: Select all

Solved

Re: 612 - DNA Sorting

Posted: Sun Jan 23, 2011 8:29 pm
by 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;
}

Re: 612 - DNA Sorting

Posted: Mon May 14, 2012 8:43 pm
by 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;
}

Re: 612 - DNA Sorting

Posted: Mon May 14, 2012 11:17 pm
by brianfry713
Don't start the output with a blank line.

Re: 612 - DNA Sorting

Posted: Tue Jul 03, 2012 12:47 am
by 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

Re: 612 - DNA Sorting

Posted: Tue Jul 03, 2012 12:49 am
by mostafiz93

Re: 612 - DNA Sorting

Posted: Tue Jul 03, 2012 10:37 am
by brianfry713
Use stable_sort() instead of sort() on line 94.

Re: 612 - DNA Sorting - Java RunTime Error

Posted: Fri May 31, 2013 4:56 pm
by sabrina_tuli
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;
}

Re: 612 - DNA Sorting - Java RunTime Error

Posted: Wed Jun 12, 2013 1:18 am
by brianfry713
Run your code on the sample input.

Re: 612 - DNA Sorting

Posted: Sun Jun 16, 2013 4:19 pm
by hello
Why Submission Error ...... ? :oops:

Re: 612 - DNA Sorting

Posted: Mon Jun 17, 2013 11:27 pm
by brianfry713
Try a different problem.

Re: 612 - DNA Sorting

Posted: Fri Aug 30, 2013 10:24 pm
by brianfry713
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

Help!612 WA!why?

Posted: Wed Sep 18, 2013 11:26 am
by dennisorz

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