116 - Unidirectional TSP

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

Post by wsarzynski » Sat Oct 12, 2002 2:08 am

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
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

Need helps !!!

Post by Robbie » Sun Oct 13, 2002 5:17 am

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
New poster
Posts: 1
Joined: Thu Oct 31, 2002 3:00 pm

116 unidirectional tsp help!

Post by vcm » Fri Nov 01, 2002 9:50 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Dec 16, 2002 8:12 pm

:cry: 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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Dec 17, 2002 8:48 am

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

Regards
Dominik

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Tue Dec 17, 2002 12:09 pm

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... :lol:

I didn't handle special cases though

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

Post by Larry » Tue Dec 17, 2002 12:40 pm

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

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

Post by Dominik Michniewski » Tue Dec 17, 2002 1:25 pm

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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

116 - Lexicography order

Post by titid_gede » Thu Dec 19, 2002 5:39 pm

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

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev » Thu Dec 19, 2002 5:55 pm

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

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Sat Dec 21, 2002 2:48 pm

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 :evil: ),but I think this is a test case that many program will make mistake.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sun Dec 22, 2002 4:45 pm

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
New poster
Posts: 14
Joined: Sun Jul 07, 2002 12:03 am
Location: Brazil
Contact:

Post by Rodrigo » Mon Dec 23, 2002 4:30 am

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon Dec 23, 2002 1:07 pm

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
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Thu Jan 02, 2003 1:32 pm

First, make your code more simpler to read

Post Reply

Return to “Volume 1 (100-199)”