612 - DNA Sorting

[Dominik Michniewski]

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 ...

[howardcheng]

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]

I had asked Carlos and he told me the rejudgement was wrong, please wait, it'll be rejudged again soon.

Saludos,
HoraPe

[eloha]

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]

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]

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)
{

[Dejarik]

I'm also getting Wrong Answer in this problem. I'm reading some of your replies talking about "rejudgement". What is this?

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

Thanks in advance!

[Klechu]

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]

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

[Maddas]

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]

I have found mistake (very stupid) in my code & get AC -
Thenk`s for help
Klechu

[shamim]

This is a blue tick problem, did you consider multiple input format.

[Maddas]

Yup, my program only accepts multiple input things.

[Maddas]

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]

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