612 - DNA Sorting

[Maddas]

Aaaargh, I confused maximum string length and maximum number of sequences in my code. The problem just didn't show for my input

Thanks a lot

[wanderley2k]

Where is mistake in my code?

[cpp]#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

typedef struct DNA_s DNA;
struct DNA_s
{
string seq;
int inversions;
};


bool operator<(const DNA& x, const DNA& y)
{
return x.inversions < y.inversions;
}

int value(char c) {
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'G') return 2;
if (c == 'T') return 3;
}

int main()
{
int inst, n, m, i, w, z, sumInversions;
string takeRead;

cin >> inst;

for (; inst > 0 ; --inst)
{
cin >> n >> m;
vector<DNA> set;
for (i = 0; i < m; i++) {
DNA tmp;
cin >> tmp.seq;

int count[4] = { 0, 0, 0, 0 };
sumInversions = 0;
for (w = 0; w < tmp.seq.size(); ++w)
{
count[value(tmp.seq[w])]++;
for (z = value(tmp.seq[w])+1; z < 4; ++z) { sumInversions += count[z]; }

/*
*if (tmp.seq[w] == 'A') { continue; }
*for (z = w; z < tmp.seq.size(); ++z)
*{
* if (value(tmp.seq[w]) > value(tmp.seq[z]))
* {
* sumInversions++;
* }
*}
*/
}
tmp.inversions = sumInversions;
set.push_back(tmp);
}

sort(set.begin(), set.end());

for (i = 0; i < set.size(); ++i) {
cout << set.seq << '\n';
}
if (inst-1 > 0) { cout << '\n'; }
}

return 0;
}
[/cpp]

[wanderley2k]

Where is mistake in my code? I tested with diverses input data and all answer is correct...

my code:
[cpp]#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

typedef struct DNA_s DNA;
struct DNA_s
{
string seq;
int inversions;
};


bool operator<(const DNA& x, const DNA& y)
{
return x.inversions < y.inversions;
}

int value(char c) {
if (c == 'A') return 0;
if (c == 'C') return 1;
if (c == 'G') return 2;
if (c == 'T') return 3;
}

int main()
{
int inst, n, m, i, w, z, sumInversions;
string takeRead;

cin >> inst;

for (; inst > 0 ; --inst)
{
cin >> n >> m;
vector<DNA> set;
for (i = 0; i < m; i++) {
DNA tmp;
cin >> tmp.seq;

int count[4] = { 0, 0, 0, 0 };
sumInversions = 0;
for (w = 0; w < tmp.seq.size(); ++w)
{
count[value(tmp.seq[w])]++;
for (z = value(tmp.seq[w])+1; z < 4; ++z) { sumInversions += count[z]; }

/*
*if (tmp.seq[w] == 'A') { continue; }
*for (z = w; z < tmp.seq.size(); ++z)
*{
* if (value(tmp.seq[w]) > value(tmp.seq[z]))
* {
* sumInversions++;
* }
*}
*/
}
tmp.inversions = sumInversions;
set.push_back(tmp);
}

sort(set.begin(), set.end());

for (i = 0; i < set.size(); ++i) {
cout << set.seq << '\n';
}
if (inst-1 > 0) { cout << '\n'; }
}

return 0;
}
[/cpp]

[wanderley2k]

I got AC with one tick!!!

[cpp]stable_sort(set.begin(), set.end());[/cpp]

it is correct!!

Thanks Gustavo and JP

Wanderley

** ALIVE THE SOCIALISM REVOLUTION **

[Minilek]

[EDIT]
I am dumb. I didn't realize this was a multiple input problem..

grrr...5 WA's for nothing!

AC now

While we're on the subject...
Does anyone have some speed tips for this problem?
I use modified counting sort to count inversions in O(n),
and before I qsort the arrays based on inversion count,
I memoize the inversion count for each string so that qsort
can just look it up in the array versus calling count_inversion()
multiple times for each string. This got me only down to .271s
but apparently there seem to be faster ways..anyone know
any ?
[/EDIT]

[Morning]

[cpp]
#include <iostream>
#include <cstring>
using namespace std;
int count(char str[51],int n)
{
int sum = 0;
for(int i = 0;i < n;i++)
{
for(int j = i + 1;j < n;j++)
{
if(str > str[j]){sum++;}
}
}
return sum;
}
int main()
{
int n,m,store[100],i,j,t;
char str[100][51],temp[51];


while(cin >> n >> m)
{
for(i = 0;i < m;i++)
{
cin >> str;
store = count(str,51);
}
//bubble sort
for(i = 0;i < m - 1;i++)
{
for(j = 0;j < m - i - 1;j++)
{
if(store[j] > store[j + 1])
{
t = store[j + 1];
store[j + 1] = store[j];
store[j] = t;
strcpy(temp,str[j + 1]);
strcpy(str[j + 1],str[j]);
strcpy(str[j],temp);
}
}
}
for(i = 0;i < m;i++){cout << str << endl;}
}
return 0;
}
[/cpp]

[dumb dan]

This is a multiple input problem!

[Morning]

i was totally confused.

The first line of a multiple input file is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

I didn't see a integer N in the first line in the Sample input,but i still change my code to
[cpp]
#include <iostream>
#include <cstring>
using namespace std;
int count(char str[51],int n)
{
int sum = 0;
for(int i = 0;i < n;i++)
{
for(int j = i + 1;j < n;j++)
{
if(str > str[j]){sum++;}
}
}
return sum;
}
int main()
{
int N,n,m,store[100],i,j,t;
char str[100][51],temp[51];

cin >> N;
while(N--)
{
cin >> n >> m;
for(i = 0;i < m;i++)
{
cin >> str;
store = count(str,51);
}
//bubble sort
for(i = 0;i < m - 1;i++)
{
for(j = 0;j < m - i - 1;j++)
{
if(store[j] > store[j + 1])
{
t = store[j + 1];
store[j + 1] = store[j];
store[j] = t;
strcpy(temp,str[j + 1]);
strcpy(str[j + 1],str[j]);
strcpy(str[j],temp);
}
}
}
for(i = 0;i < m;i++){cout << str << endl;}
}
return 0;
}
[/cpp]
still got WA,pliz,why??

[dumb dan]

store = count(str,51);

I think you want to change that to

store = count(str,n);

Besides that you'll get a PE if you don't seperate each case with a blank line.

[Morning]

dumb dan,thanx
u always help me

[hsuyt831]

i use merge sort to solve this problem
but i can't figure out why i get WA
could someone help me ??

[c]
#include <stdio.h>
#include <stdlib.h>

int count;

struct measure{
int ans;
int num;
};
typedef struct measure Measure;
void mergeSort(char[],int, int);
void merge(char[],int, int, int);
void sort(Measure[], int);



int main(){

int m,n;
int k,i,j;
char input[1000][1000], A[1000];
Measure result[1000];

scanf("%d %d\n",&n,&m);
for(i=0;i<m;i++){
scanf("%s",&input);
}

for(i=0;i<m;i++)
result.num=i;

for(i=0;i<m;i++){
for(j=0;j<n;j++)
A[j]=input[j];
count=0;
mergeSort(A,0,n-1);
result.ans=count;
}

sort(result,m);
for(i=0;i<m;i++){
k=result.num;
for(j=0;j<n;j++)
printf("%c",input[k][j]);
printf("\n");
}
return 0;
}

void mergeSort(char A[],int p,int r){

int q;

if(p<r){
q=(p+r)/2;
mergeSort(A,p,q);
mergeSort(A,q+1,r);
merge(A,p,q,r);
}
}

void merge(char A[],int p,int q, int r){

int i,j,k;
int n1,n2;
char L[501],R[501];

n1=q-p+1;
n2=r-q;

for(i=0;i<n1;i++)
L=A[p+i];
for(j=0;j<n2;j++)
R[j]=A[q+1+j];
L[n1]='Z';
R[n2]='Z';
i=0;
j=0;
for(k=p;k<=r;k++){
if(L<=R[j]){
A[k]=L;
i++;
}
else{
A[k]=R[j];
j++;
count=count+(n1-i);
}
}
}

void sort(Measure A[], int size){

int i,pass;
Measure hold;

for(pass=1;pass<size;pass++)
for(i=0;i<size-1;i++)
if(A.ans > A[i+1].ans){
hold = A;
A[i] = A[i+1];
A[i+1] = hold;
}
}
[/c]

[Heartattack!]

My code works perfectly on my machine. I compiled it with vc++.net. Running on the judge it gave a run time error: "invalid memory reference". Could someone please tell me what's wrong? The algo is simple. I get the input, check for the sortedness through the bubble sort check, qsort the data and print it out.....only not on the judge
Please help. Thanks in advance:
[cpp]

// p612.DNA Sorting.cpp : Defines the entry point for the console application.
//

@begin_of_source_code

/* @JUDGE_ID: ****** 612 C++ */

#include "stdio.h"


struct str
{
int Srtdnes;
char seq[51];
};

int Cmp(const void *x,const void *y)
{
int a=((str*)x)->Srtdnes;
int b=((str*)y)->Srtdnes;
return a-b;
}

void main(void)
{
int length,lines;

scanf("%d%d",&length,&lines);


str *a=(str*)malloc(sizeof(str)*lines);

for(int i=0;i<lines;i++)
{
scanf("%s",a.seq);
a.Srtdnes=0;
for(int j=1;j<length;j++)
for(int k=0;k<j;k++)
if(a.seq[j]<a.seq[k])
a.Srtdnes++;
}
qsort(a,lines,sizeof(str),Cmp);

for(int i=0;i<lines;i++)
puts(a.seq);



}


@end_of_source_code

[/cpp]

[UFP2161]

It's a multiple input problem (the blue checkmark next to the problem's name in the volume's index).

http://online-judge.uva.es/problemset/minput.html

[Heartattack!]

Thanks, I'll try it with multiple input. It was really silly of me to miss the blue tick....

[Raiyan Kamal]

are you sure you are taking care of the ' multiple input ' - thing properly ?