Page 3 of 16
Posted: Sat Oct 12, 2002 2:08 am
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 ?

### Need helps !!!

Posted: Sun Oct 13, 2002 5:17 am
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;

var i,j :longint;
begin

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

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

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

### 116 unidirectional tsp help!

Posted: 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;

{
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;
//printTable ();
k = getMinCost ();
getPath (k);
cout << table [mm-1][k] <<endl;
}
return 0;
}
[/cpp]

Posted: Mon Dec 16, 2002 8:12 pm
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

Posted: 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

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

I didn't handle special cases though

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

Posted: 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

### 116 - Lexicography order

Posted: Thu Dec 19, 2002 5:39 pm
according to lexicography order, which is come first between :
1, 2, 1, 10
1, 2, 1, 2

Posted: Thu Dec 19, 2002 5:55 pm
Second one (yeah, in this problem "lexicography" means "select lowest number").

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

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

Posted: Mon Dec 23, 2002 4:30 am
Same with me. I've covered all these points too, but I still get WA :/.

Posted: 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
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