612 - DNA Sorting

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

}

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

[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/ ... t/612i.txt
output : http://www.csie.nctu.edu.tw/~chchu/acm/ ... t/612o.txt

[brianfry713]

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

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

[brianfry713]

Run your code on the sample input.

[hello]

Why Submission Error ...... ?

Code: Select all

[brianfry713]

Try a different problem.

[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

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