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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Jan 28, 2004 9:58 am

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

Post by howardcheng » Thu Jan 29, 2004 5:20 pm

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.

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Thu Jan 29, 2004 8:40 pm

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

Post by eloha » Wed Feb 25, 2004 5:04 am

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

Post by eloha » Thu Feb 26, 2004 9:59 am

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]

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Thu Feb 26, 2004 4:39 pm

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:

Post by Dejarik » Sun Mar 14, 2004 1:57 pm

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
New poster
Posts: 8
Joined: Fri Apr 16, 2004 6:27 pm
Location: Rzesz

Post by Klechu » Fri Apr 16, 2004 6:35 pm

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:

Post by Dejarik » Sat Apr 17, 2004 12:31 am

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
New poster
Posts: 11
Joined: Sat Apr 03, 2004 1:45 am

612 - DNA Sorting - WA, why?

Post by Maddas » Sat Apr 24, 2004 11:46 am

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

Post by Klechu » Sat Apr 24, 2004 12:50 pm

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Apr 24, 2004 12:54 pm

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

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

Post by Maddas » Sat Apr 24, 2004 2:27 pm

Yup, my program only accepts multiple input things.

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

Post by Maddas » Mon Apr 26, 2004 12:18 pm

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:

Post by Dejarik » Mon Apr 26, 2004 3:26 pm

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

Post Reply

Return to “Volume 6 (600-699)”