612 - DNA Sorting

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

612 - DNA Sorting

Post by smsampark » Thu Aug 12, 2010 9:38 am

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

}

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

Re: 612 - DNA Sorting - Java RunTime Error

Post by reyan » Wed Sep 08, 2010 3:36 pm

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

Post by fkrafi » Wed Oct 06, 2010 7:58 pm

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

Post by Md. Mijanur Rahman » Sun Jan 23, 2011 8:29 pm

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

Post by mathgirl » Mon May 14, 2012 8:43 pm

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

Post by brianfry713 » Mon May 14, 2012 11:17 pm

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

Post by mostafiz93 » Tue Jul 03, 2012 12:47 am

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

Post by mostafiz93 » Tue Jul 03, 2012 12:49 am


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

Re: 612 - DNA Sorting

Post by brianfry713 » Tue Jul 03, 2012 10:37 am

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

Post by sabrina_tuli » Fri May 31, 2013 4:56 pm

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

Post by brianfry713 » Wed Jun 12, 2013 1:18 am

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

Post by hello » Sun Jun 16, 2013 4:19 pm

Why Submission Error ...... ? :oops:
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

Post by brianfry713 » Mon Jun 17, 2013 11:27 pm

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

Post by brianfry713 » Fri Aug 30, 2013 10:24 pm

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?

Post by dennisorz » Wed Sep 18, 2013 11:26 am

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

Post Reply

Return to “Volume 6 (600-699)”