## 612 - DNA Sorting

Moderator: Board moderators

bolster
New poster
Posts: 16
Joined: Tue Oct 30, 2001 2:00 am
Is there some special case I am ignoring with this one?

I've got a struct with the string, and a parameter for initial list position, which I use as a tie-breaker in my compare function.

Is there something wrong with my unsortedness counter? Seems to be exactly what the problem asks for...

d->sort = 0;
for(i=0;i<len;++i) for(j=i+1;j<len;++j)
if(d->str > d->str[j]) ++d->sort;

This looks fine to me... perhaps the problem gives invalid strings? or are the letters not only in upper case?

Bolster

gilbert
New poster
Posts: 4
Joined: Wed Dec 12, 2001 2:00 am
Did you handle the special multiple test input?

chessmaster
New poster
Posts: 5
Joined: Sat Sep 28, 2002 3:46 pm

### 612-DNA SORTING WA

[pascal]
type tt=record
d:string;
pos:integer;
end;
var data:array[1..200] of tt;
d3:array[1..200]of INTEGER;
temp:tt;
var a,b,n,jb:integer;
function hitung(s:string):integer;
var a,b,c,d:integer;
se1,se2:set of char;
begin
se1:=[];
d:=0;
for a:=1 to N do begin
if not (upcase(s[a]) in se1)and
(upcase(s[a]) in ['G','C','A','T']) then
begin
se1:=se1+[upcase(s[a])];
se2:=[];
for b:=a+1 to N do begin
if (upcase(s)<upcase(s[a]))then
begin
inc(d);
end;
end;
end;
end;
hitung:=d;
end;
var min,z,jum,l:integer;
begin
for l:=1 to jum do begin
for a:=1 to jb do begin
data[a].pos:=a;
end;
for a:=1 to jb-1 do
for b:=a+1 to jb do begin
if hitung(data.d)>hitung(data[a].d) then
begin
temp:=data;
data:=data[a];
data[a]:=temp;
end;
end;
for a:=1 to jb-1 do
for b:=a+1 to jb do begin
if (hitung(data.d)=hitung(data[a].d))
and
(data.pos>data[a].pos) then begin
temp:=data;
data:=data[a];
data[a]:=temp;
end;
end;
for a:=JB DOWNto 1 do begin
writeln(data[a].d);
end;
writeln;
end;
end.[/pascal]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
In your function "hitung", looks like you only check only the first occurences of A, C, G, T.

If I interpreted "hitung" correctly:
- hitung('ACA') returns 0 .......... eventhough there's 1-reversal (CA).
- hitung('ACG') returns 0 .......... 0-reversal.

I'm sure in order to find out the 'sorted-degree' you have to count all reversed condition.

I might be wrong since I'm not too sure with Pascal sets there ...

Try this input and see what it will return:
3 3
ACA
ACG
ACG

Regards,
-turuthok-

zilnus
New poster
Posts: 9
Joined: Sat Mar 08, 2003 11:59 am

### 612 ???

[c]
#include <stdio.h>

typedef struct {
char string[51];
int nilai;
} liststring;

int main()
{
int i,n,m,count,j,key,k;
liststring data[101],temp;

scanf ("%d %d",&n,&m);
for (i=0;i<m;i++)
scanf ("%s",&(data.string));

/* Algoritma */

for (k = 0;k<m;k++) {
count = 0;
for (i = 0;i<n;i++) {
key = data[k].string;
for (j=i+1;j<=n-1;j++)
if (key > data[k].string[j]) count ++;
}
data[k].nilai = count;
}

for (i=0;i<m-1;i++) {
for (j=0;j<m-1;j++) {
if (data[j].nilai > data[j+1].nilai) {
temp = data[j];
data[j] = data[j+1];
data[j+1] = temp;
}
}
}
for (i=0;i<m;i++)
printf ("%s\n",data.string);

return 0;
}

Why my source wrong answer?I don't unsderstand[/c]

kenny1har
New poster
Posts: 7
Joined: Fri May 09, 2003 2:30 am

### 612 - can anyone help me

i don't understand why my program is wrong

[pascal]
program p612 (input,output);
type
dnaset=array[1..50] of string;
dnacountset=array[1..50] of integer;
var
m,n,j,k:integer;
ch:string;
dnacount:dnacountset;
dna:dnaset;

procedure ssort(z:integer;dna:dnaset);
var
n,j,k : integer;
x,y,temp :string;
begin
dnacount[z]:=0;
for j:=m downto 1 do
for k:=1 to j-1 do begin
x:=copy(dna[z],k,1);
y:=copy(dna[z],k+1,1);
if x>y then begin
writeln(x,' is greater than ',y);
dnacount[z]:=dnacount[z]+1;
delete(dna[z],k,2);
insert(y+x,dna[z],k);
end;
end;
writeln(z,'=',dnacount[z]);
end;

procedure psort(dna:dnaset);
var
j,k,temp :integer;
dnacount2:dnacountset;
begin
for j:=1 to n do
dnacount2[j]:=j;
for k:=1 to n do
for j:=1 to n-1 do
if dnacount[j]>dnacount[j+1] then begin
temp:=dnacount[j];
dnacount[j]:=dnacount[j+1];
dnacount[j+1]:=temp;

temp:=dnacount2[j];
dnacount2[j]:=dnacount2[j+1];
dnacount2[j+1]:=temp;
end;
for j:=1 to n do
writeln(dna[dnacount2[j]]);
end;

begin
while not eof(input) do begin
for j:=1 to n do begin
dna[j]:=copy(ch,1,m);
ssort(j,dna);
end;
psort(dna);
end;
end.
[/pascal]

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
It's multi input...

ayaw
New poster
Posts: 18
Joined: Fri May 23, 2003 3:52 pm
Contact:
anyone can catch my mistakes???

this is my code :

Code: Select all

``````#include <stdio.h>
#include <string.h>

char buffer[50][101];
int  inv[50];

value(char a) {
if(a=='A') return 0;
if(a=='C') return 1;
if(a=='G') return 2;
if(a=='T') return 3;
return -1;
}
inversion(char *a) {
int i,j,count=0;
for(i=0;i<strlen(a)-1;i++)
for(j=i+1;a[j];j++) {
if(value(a[i]) > value(a[j])) count++;
}
return count;
}

void sort(int n) {
char buf[101];
int i,j;
for(i=0;i<n-1;i++)
for(j=0;j<n-1;j++) if(inv[j]>inv[j+1]) {
inv[j]^=inv[j+1]^=inv[j]^=inv[j+1];
strcpy(buf,buffer[j]);
strcpy(buffer[j],buffer[j+1]);
strcpy(buffer[j+1],buf);
}
}

main() {
int i,j,n,m,multiple;
scanf("%d",&multiple);
for(i=0;i<multiple;i++) {
scanf("%d %d\n",&m,&n);
for(j=0;j<n;j++) {
scanf("%s",buffer[j]);
inv[j] = inversion(buffer[j]);
}
sort(n);
if(i!=0) printf("\n");
for(j=0;j<n;j++) printf("%s\n",buffer[j]);
}
return 0;
}
``````
peace...

Max108
New poster
Posts: 5
Joined: Wed Jun 11, 2003 11:24 pm

### 612 WA help!!

Hi, i just wrote this code for the 612 DNA sorting problem, no matter what imput i select to test my program it ALWAYS gives me the CORRECT answer but when i submit the program the judge says WA.

[cpp]

#include <fstream.h>
#include <string.h>
#include <stdlib.h>

{
int peso;
int orden;
char *palabra;
};

int main(void)
{
//ifstream cin;
//cin.open("texto.txt");
int longitud;
int numStrings;
int auxPeso;
int pruebas;
cin>>pruebas;

while (pruebas){
cin>>longitud;
cin>>numStrings;
char *auxString = new char[longitud+1];

for(int t=0; t<numStrings; t++){
cin.ignore();
}

for(int k=0; k<numStrings; k++)
for(int m=0; m<longitud-1; m++)
for(int j=m+1; j<longitud; j++)

for(int q=0; q<numStrings-1; q++)
for(int j=q+1; j<numStrings; j++)

}

do
{

for(int f=0; f<numStrings-1; f++)

}
}

for( int w=0; w<numStrings; w++)
cout<<endl;

pruebas--;

}

return 0;
}
[/cpp]

Can someone tellme whats wrong? im considering multiple inputs and all that stuff but nothing I also know that this solution is wide too big but Im to lazzy to write this again, maybe Im not considering some critical inputs but i have tryed a lot.

I even compared the results of my program with the results of this correct code. Both are giving the same answer but mine is getting WA...

[cpp]

#include <iostream.h>
#include <string.h> using namespace std;
#include <fstream.h>

int main(){
int cases,i;
cin>>cases;
for (i=1;i<=cases;i++){
char dat[102][52]={0};
int col,row;
int c,r,a;
int inver[102] = {0};

cin>>col>>row;
for (r=1;r<=row;r++){
cin>>dat[r];
for (c=0;c<col-1;c++)
for (a=c+1;a<col;a++)
if (dat[r][a]<dat[r][c]) inver[r]++;
}

int max=0;
for (r=1;r<=row;r++)
if (inver[r]>max) max = inver[r];

for (a=0;a<=max;a++)
for (r=1;r<=row;r++)
if (inver[r]==a){
for (c=0;c<col;c++)
cout<<dat[r][c];
cout<<endl;
}
cout<<endl; //new line
}
return 0; //end program
}
[/cpp]

Tatiana Favaro
New poster
Posts: 2
Joined: Sun Nov 02, 2003 4:10 am
Location: ES - Brasil
Contact:

### 612 - WA ?

[pascal]

Program t612;
var
m, n : Integer;
i, j, q, p : integer;
Maior : Integer;

DNA : array [0..50, 0..100] of Char;
count : array [0..100] of Integer;
order : array [0..100] of Integer;

Begin
while not eof do
begin

//input
For i:=0 to m do
For j:=0 to n do

For i:= 0 to n do
count := 0;
end;

//counter
For i:=0 to m do
For j:=0 to n-1 do
For q:=j+1 to n do
if DNA[q] > DNA[j] then
count := count;

//order
Maior:= count[0];

For i:= 0 to m do begin
For j:= 1 to m do
if count[j] > Maior then begin
Maior := count[j];
order := j;
end;
count[order] := -1;
end;

//printer
For i:= 0 to m do begin //indice do order = linha
For j:=0 to n do
write(DNA[order][j]);
writeln( );
end;

End.
[/pascal]

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am
I can give you input/output.
Mail me.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 612 - DNA Sorting - WA After rejudgement

What's new in the data set that's crucial? Can someone give me test cases? Thanks.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
what is the possibility that the judge had made a mistake or that it is not a logical error?
otherwise I'll learn a very good lesson because I can see nothing to this problem that all 800 people but 4 missed.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I want what's change after rejudgement too....
I don't see any trap in this problem but got WA (or TLE - I don't get report) after rejudgement ...

Best regards
DM
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)

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China
AC makes me feels good,
But WA makes me thinks hard.