## 612 - DNA Sorting

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
We know, that data was changed. But problem is: what in new data is different from old one?
It's strange that in one moment 800 people (in which are famous names) changing your status from Acc to other ...

Best regards
DM

PS. In problem description I don't see any changes - limits or algorithms ...
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

howardcheng
Learning poster
Posts: 71
Joined: Thu Aug 21, 2003 1:56 am
I was a judge for the contest that used this problem originally, and my judge's solution no longer works after rejudgement. I suppose that my judge's solution could be wrong, but when everyone else is wrong after the rejudgement, my guess is that there is something wrong with the data set.

horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires
I had asked Carlos and he told me the rejudgement was wrong, please wait, it'll be rejudged again soon.

Saludos,
HoraPe

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
Can anyone tell me what's wrong with my code?
[c]
#include <stdio.h>
struct s
{ int serno;
char dna[51];
int inversion;
}a[100];
int n,m;

int getdna(char x)
{
switch(x)
{ case 'A': return 0;
case 'C': return 1;
case 'G': return 2;
case 'T': return 3;
default : abort();
}
}

int count_sort(char *str)
{ int i,j,k,invers=0,count[4]={0,0,0,0};
for(i=0; str; i++)
{
k=getdna(str);
count[k]++;
for(j=k+1; j<4; j++)
invers += count[j];
}
return invers;
}

int sort_function( const void *a, const void *b)
{
struct s *p=(struct s *)a, *q=(struct s *)b;
if(p->inversion > q->inversion) return 1;
else if(p->inversion < q->inversion) return -1;
else
{ if(p->serno > q->serno) return -1;
else return 1;
}
}

void main()
{
int testcase,t,i;

/*freopen("in612.txt","r",stdin);*/
scanf("%d",&testcase);
for(t=1; t<=testcase; t++)
{ if(t>1) printf("\n");
scanf("%d %d",&n,&m);
for(i=0; i<m; i++)
{
scanf("%s",&a.dna);
a.serno=i;
a.inversion=count_sort(a.dna);
}
qsort(a,m,sizeof(a[0]),sort_function);
for(i=0; i<m; i++) printf("%s\n",a.dna);
}
}
[/c]

eloha
New poster
Posts: 38
Joined: Thu Oct 31, 2002 8:24 am
Location: Taiwan
I just modify my sort function and got AC.
Why?
The following is my new sort function:
[c]
int sort_function( const void *a, const void *b)
{
struct s *p=(struct s *)a, *q=(struct s *)b;
if(p->inversion != q->inversion)
return p->inversion - q->inversion;
else
return p->serno - q->serno;
}
[/c]

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
If two or more strings are equally sorted, list them in the same order they are in the input file.
Actually, at first you were doing the reverse thing, that is list the strings in reversed order when they are equally ....
So in the previous code, the sort function would have been
[cpp]int sort_function( const void *a, const void *b)
{
Istiaque Ahmed [the LA-Z-BOy]

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Example of input:

Code: Select all

``````10 8
AACATGAAGG
BBDBUFBBHH
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
CCECVGCCII
3 3
ACC
ACG
ACA``````
Example of output:

Code: Select all

``````CCCGGGGGGA
AACATGAAGG
BBDBUFBBHH
CCECVGCCII
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA
ACC
ACG
ACA``````

Klechu
New poster
Posts: 8
Joined: Fri Apr 16, 2004 6:27 pm
Location: Rzesz
Hello, although my answer was not rejudgeg I still get WA too. Maybe my answer is really a "tank" but on my computer works correctly

[cpp]#include <stdio.h>
#include <stdlib.h>
char tab[100][51];
unsigned wartosc[100]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,};

int main()
{
int dlogosc;
int ilosc;
while(scanf("%d%d",&dlogosc,&ilosc)==2)
{
for(int i=0;i<ilosc;i++)
{
scanf("%s",&tab[0]);

for(int j=0;j<dlogosc-1;j++)
{
int k=1;
for(;k<dlogosc;k++)
{
if(tab[j+k]<tab[j])wartosc++;
}
}
}

for(int num=0;num<15000;num++)
{

for(int mum=0;mum<ilosc;mum++)if(wartosc[mum]==num)printf("%s\n",tab[mum]);
}
}

return 0;

}[/cpp]

Thanks for help
PS Like you sow - I am not really good programer :(

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:
Instead of posting your code, you may want to post some input/output samples executed with your program and we can compare them in order to find differences. I got AC in this problem and we can check where may be the bug.

Joan

New poster
Posts: 11
Joined: Sat Apr 03, 2004 1:45 am

### 612 - DNA Sorting - WA, why?

Hi. I'm getting WA for problem 612, but I don't know why. I tested my program against a reasonably large (and in my opinion complete) input/output combination, and my program gets everything right (newlines and so too).

I'd like to ask whether anybody minds giving me some sample input/output to test my program against, help is appreciated a lot, thanks!

Klechu
New poster
Posts: 8
Joined: Fri Apr 16, 2004 6:27 pm
Location: Rzesz
I have found mistake (very stupid) in my code & get AC -
Thenk`s for help
Klechu

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
This is a blue tick problem, did you consider multiple input format.

New poster
Posts: 11
Joined: Sat Apr 03, 2004 1:45 am
Yup, my program only accepts multiple input things.

New poster
Posts: 11
Joined: Sat Apr 03, 2004 1:45 am
Can anybody give ma few "tricky" sample inputs? I tested my program against a very large input file and all the outputs were correct.
I'm really stumped

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:
That's my input:

Code: Select all

``````3

10 13
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GGGGGGGGGG
GATCAGATTT
CCCGGGGGGA
TTTTTTTTTT
ATCGATGCAT
AAAAAAAAAA
CCCCCCCCCC
ACGTACGTAC
CGTACGTACG
TGCATGCATG

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT

10 13
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GGGGGGGGGG
GATCAGATTT
CCCGGGGGGA
TTTTTTTTTT
ATCGATGCAT
AAAAAAAAAA
CCCCCCCCCC
ACGTACGTAC
CGTACGTACG
TGCATGCATG``````
and that's my output:

Code: Select all

``````GGGGGGGGGG
TTTTTTTTTT
AAAAAAAAAA
CCCCCCCCCC
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ACGTACGTAC
ATCGATGCAT
CGTACGTACG
TGCATGCATG
TTTTGGCCAA
TTTGGCCAAA

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

GGGGGGGGGG
TTTTTTTTTT
AAAAAAAAAA
CCCCCCCCCC
CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ACGTACGTAC
ATCGATGCAT
CGTACGTACG
TGCATGCATG
TTTTGGCCAA
TTTGGCCAAA``````
I hope it helps...

Joan