612 - DNA Sorting

[bolster]

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]

Your count appears correct.
Did you handle the special multiple test input?

[chessmaster]

[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
readln(jum);
for l:=1 to jum do begin
readln(input);
readln(input,n,jb);
for a:=1 to jb do begin
readln(input,data[a].d);
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]

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]

[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]

i don't understand why my program is wrong
please give any comments ....

[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
read(m,n);
readln;
for j:=1 to n do begin
readln(ch);
dna[j]:=copy(ch,1,m);
ssort(j,dna);
end;
psort(dna);
end;
end.
[/pascal]

[little joey]

It's multi input...
Read all about it at http://acm.uva.es/problemset/minput.html.

[ayaw]

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;
}

[Max108]

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>

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



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



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


for(int t=0; t<numStrings; t++){
ArrCadenas[t].palabra = new char[longitud+1];
cin.ignore();
cin.getline( ArrCadenas[t].palabra, longitud+1);
ArrCadenas[t].peso = 0;
ArrCadenas[t].orden = t;
}




for(int k=0; k<numStrings; k++)
for(int m=0; m<longitud-1; m++)
for(int j=m+1; j<longitud; j++)
if(ArrCadenas[k].palabra[m] > ArrCadenas[k].palabra[j])
ArrCadenas[k].peso += 1;



for(int q=0; q<numStrings-1; q++)
for(int j=q+1; j<numStrings; j++)
if(ArrCadenas[q].peso > ArrCadenas[j].peso){
strcpy(auxString,ArrCadenas[q].palabra);
strcpy(ArrCadenas[q].palabra,ArrCadenas[j].palabra);
strcpy(ArrCadenas[j].palabra,auxString);
auxPeso = ArrCadenas[q].peso;
ArrCadenas[q].peso = ArrCadenas[j].peso;
ArrCadenas[j].peso = auxPeso;
auxPeso = ArrCadenas[q].orden;
ArrCadenas[q].orden = ArrCadenas[j].orden;
ArrCadenas[j].orden = auxPeso;

}


do
{

verdad = 0;
for(int f=0; f<numStrings-1; f++)
if( ArrCadenas[f].peso == ArrCadenas[f+1].peso)
if(ArrCadenas[f].orden > ArrCadenas[f+1].orden){

strcpy(auxString,ArrCadenas[f].palabra);
strcpy(ArrCadenas[f].palabra,ArrCadenas[f+1].palabra);
strcpy(ArrCadenas[f+1].palabra,auxString);

auxPeso = ArrCadenas[f].orden;
ArrCadenas[f].orden = ArrCadenas[f+1].orden;
ArrCadenas[f+1].orden = auxPeso;

verdad=1;
}
}
while(verdad==1);


for( int w=0; w<numStrings; w++)
cout<<ArrCadenas[w].palabra<<endl;
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]

I'm getting WA for my program. Does anyone have some thinking about this???

[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
readln(m,n);

//input
For i:=0 to m do
For j:=0 to n do
read(DNA[j]);

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]

I can give you input/output.
Mail me.

[Larry]

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

[yiuyuho]

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]

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

[Zhao Le]

The data has changed.
http://online-judge.uva.es/board/viewtopic.php?t=4932