116 - Unidirectional TSP

[wsarzynski]

Somebody please help, where is the trap ?
Is lex smallest path the one with smallest row index in
previous column ?
Can i go from row with max index to row 0 ?
Maybe come traps in input, some chars to ignore or
no spaces between ints ?

[Robbie]

I don't know why my code got WA. Please help !
Here is it :


Program Pr_116;

const maxm =11;
maxn =101;
max =2147483647;
fi ='116.txt';
fo ='116.out';

type m1 =array[1..maxm,1..maxn]of longint;
m2 =array[1..maxm,1..maxn]of integer;

var a,l :m1;
m,n :longint;
test :longint;
min :longint;

Procedure Readfile;
var i,j :longint;
begin
read(m,n);

for i:=1 to m do
for j:=1 to n do read(a[i,j]);
end;

Procedure Process;
var i,j,u,k,li :integer;
pre :m2;
begin
fillchar(pre,sizeof(pre),0);

for i:=1 to m do
for j:=1 to n do
if j=n then l[i,j]:=a[i,j]
else l[i,j]:=max;

for j:=n downto 2 do
for i:=1 to m do
for k:=i-1 to i+1 do
begin
u:=k;
if u=0 then u:=m;
if u=m+1 then u:=1 ;

if l[u,j-1]>l[i,j]+a[u,j-1] then
begin
l[u,j-1]:=l[i,j]+a[u,j-1];
pre[u,j-1]:=i;
end
else if (l[u,j-1]=l[i,j]+a[u,j-1]) and (pre[u,j-1]>i) then
begin
pre[u,j-1]:=i;
end;
end;

min:=max ; li:=0;
for i:=1 to m do
if l[i,1]<min then
begin
min:=l[i,1] ;
li:=i;
end
else if l[i,1]=min then
if li=0 then li:=i;

write(li);
for j:=1 to n-1 do
begin
write(' ',pre[li,j]);
li:=pre[li,j];
end;
writeln;
write(min);
end;

Begin
{Assign(input,fi); reset(input);
Assign(output,fo); rewrite(output);}

test:=0;
while not eof(input) do
begin
Readfile;

if (m=0) and (n=0) then break;
inc(test);
if test>1 then writeln;
Process ;
end;

{ close(output);
close(input);}
end.[/pascal][/code]

[vcm]

Hi there,
can any one help me ?
i don't know why this code always gives me wrong answer.
I used dynamic programming, an used long int, and i have tested with some more cases (random cases)
Thanks!

[cpp]
/* #: 116
* Title: Unidirectional TSP
* Technique: dynamic programming
*/
#include <iostream.h>
#include <algorithm>
using namespace std;
typedef unsigned short idx;
typedef long myint;

const short MAXN = 110;
const short MAXM = 110;

myint table [MAXN][MAXM];
idx nn, mm;

bool readNextTable ()
{
if (cin.eof ()) return false;
cin >> nn >> mm;
if (cin.eof ()) return false;
idx j,i;
// reads the table in inverse and transpose form
for (j=0; j<nn; j++) {
for (i=0; i<mm; i++) {
cin >> table [mm-i-1][j];
if (cin.eof ()) return false;
}
}
return true;
}
void printTable ()
{
idx j, i;
for (j=0; j<mm; j++) {
for (i=0; i<nn; i++) {
cout << table [j] << " ";
}
cout <<endl;
}
}
idx getNext (idx i)
{
if (i==(nn-1))
return 0;
return i+1;
}
idx getPrev (idx i)
{
if (i==0)
return nn-1;
return i-1;
}
idx min2 (myint* vv, idx i, idx j)
{
if (vv == vv [j])
return i<j?i:j;
return vv <vv [j]?i:j;
}
idx min3 (myint* vv, idx i)
{
return min2 ( vv, min2 (vv,getPrev (i),i), getNext (i) );
}
void print (myint* vv)
{
idx i;
for (i=0; i<nn; i++)
cout << vv << " ";
cout <<endl;
}
void getMinCost1 (myint* ant, myint* nxt)
{
idx i,k;
for (i=0; i<nn; i++) {
k = min3 (ant, i);
nxt += ant [k];
}
// print (nxt);
}
idx getMinCost ()
{
idx j;
for (j=1;j<mm;j++) {
getMinCost1 (table [j-1], table [j]);
}
return min_element (table [mm-1], table [mm-1]+nn-1)-table [mm-1];
}
void getPath (idx way)
{
short j;
cout << way+1 << " ";
for (j=mm-2; j>=0; j--) {
way = min3 (table [j], way);
cout << way+1 << " ";
}
cout << endl;
}

int main ()
{
idx k;
while (readNextTable ()) {
//printTable ();
k = getMinCost ();
getPath (k);
cout << table [mm-1][k] <<endl;
}
return 0;
}
[/cpp]

[Larry]

It seems like I've tried all these cases relating to this problem, as well as testing tons and tons of border cases, can someone tell me if there's a trap or some really good sample output? Thanks

[Dominik Michniewski]

In my opinion some trouble make matrix with 1xN and 2xN ... if I handle it specially, I got Accepted after rejudgement ....

Regards
Dominik

[junjieliang]

I was having problems with outputting the lexicographically smallest route, but I got AC after fixing that. I think that's the major problem everyone else is facing as well...

I didn't handle special cases though

[Larry]

I rewrote it from scratch and got it AC.. I also didn't check for the 1XN or 2XN.

[Dominik Michniewski]

I made first time small mistake with 2xN matrix ... This was a reason, why I write my last message ) if I add one condition to two if's everything was OK. So I don't handle it special too ... I see that I wrong write my thoughts )

Regards
Dominik

[titid_gede]

according to lexicography order, which is come first between :
1, 2, 1, 10
1, 2, 1, 2

[Ivan Golubev]

Second one (yeah, in this problem "lexicography" means "select lowest number").

[FlyDeath]

I think everyone get WA can try this:

Code: Select all

input:
6 7
1 9 9 1 9 9 9
9 1 1 9 9 9 9
9 9 9 9 1 1 1
9 9 9 1 9 9 9
9 9 1 9 9 9 9
9 1 9 9 1 1 1

output:
1 2 2 1 6 6 6
7

Althought I still get WA(I'm trying to find the mistake ),but I think this is a test case that many program will make mistake.

[titid_gede]

i use DP, and after rejudgement i get WA. I get the same result as you post and i 've tried matrix 1xn, 2xn and nx1. and my code works. i didnt know what's wrong with my code .
firstly, i thought that the problem is in lexicography order which i thought 1, 2, 1, 10 come first than 1, 2, 1, 2. but not so.
Then i thought that perhaps data type which i use. although the path weight will not exceed integer value 30 bit, but perhaps on the way to the result it will exceed it, then i use bigger data type, but the result was the same, WA.
til now, i have no idea what's the mistake with my code .

[Rodrigo]

Same with me. I've covered all these points too, but I still get WA :/.

[little joey]

hi all,
been struggeling with this one for quite some time too, but finaly solved it by considering possible quirks in the input. my first code got accepted before rejudge and looked something like:

[pascal]while not eof do begin
readln(rows,columns);
for row:=1 to rows do for column:=1 to columns do read(m[row,column]);
{rest of code, calculating smallest weight and writing answer}
end;[/pascal]

after rejudge it suddenly got WA. now i changed it to:

[pascal]while not eof do begin
readln(rows,columns);
for row:=1 to rows do for column:=1 to columns do read(m[row,column]);
readln;
{rest of code, calculating smallest weight and writing answer}
end;[/pascal]

and got AC again!

has to do with extra spaces at the end of an input line, i guess.

happy hunting.

[sidky]

First, make your code more simpler to read