OJ Board

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

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

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

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-

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

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]

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

anyone can catch my mistakes???

this is my code :

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]

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]

I can give you input/output.
Mail me.

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

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.

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

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