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

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Thu Jun 27, 2002 3:55 pm

Hi!

You have a small mistake....

You have a table [1..100,1..10,1..2] while you should have [1..10,1..100,1..2]

If you change it you will have Accepted...

Good Luck :wink:

rascle
New poster
Posts: 20
Joined: Wed Mar 06, 2002 2:00 am

116

Post by rascle » Sat Jul 13, 2002 7:20 am

after rejudge..

I always got WA...

Can anyone give me some sample input and sample output..

thx... [/c]

youngwook
New poster
Posts: 5
Joined: Wed Jul 17, 2002 8:15 am
Location: Seoul

Wrong Answer...?

Post by youngwook » Wed Jul 17, 2002 1:38 pm

:o

what's wrong??

help me.. :cry:

[c]@BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: ******** 116 C "Dynamic Programming" */

main()
{
int row, col, i, j, path, a, b, c;
long weight[10][100];
long small;

while (scanf("%ld %ld", &row, &col) == 2)
{
for (i=0; i<row; i++)
for (j=0; j<col; j++)
scanf("%ld", &weight[j]);

for (j=col-2; j>=0; j--)
for (i=0; i<row; i++)
{
a = weight[(i-1+row)%row][j+1];
b = weight[j+1];
c = weight[(i+1)%row][j+1];
if (a < b) {
if (c < a)
weight[j] += c;
else
weight[j] += a; }
else {
if (b > c)
weight[j] += c;
else
weight[j] += b; }
}

path=0;
small=weight[path][0];
for (i=1; i<row; i++)
if (weight[0] < small) {
path=i; small=weight[path][0];
}
printf("%d", path+1);

for (j=1; j<col; j++)
{
i=path;
a = weight[(i-1+row)%row][j];
b = weight[j];
c = weight[(i+1)%row][j];
if (a < b) {
if (c < a)
path = (i+1)%row;
else if (c > a)
path = (i-1+row)%row;
else
path = ((i+1)%row < (i-1+row)%row) ? (i+1)%row : (i-1+row)%row; }
else if (a > b) {
if (b > c)
path = (i+1)%row;
else if (b < c)
path = i;
else
path = ((i+1)%row < i) ? (i+1)%row : i; }
else {
if (c < b)
path = (i+1)%row;
else
path = ((i-1+row)%row < i) ? (i-1+row)%row : i; }
printf(" %d", path+1);
}

printf("\n%ld\n", small);

}
}

@END_OF_SOURCE_CODE [/c]
Last edited by youngwook on Thu Jul 18, 2002 1:18 am, edited 1 time in total.

karl
New poster
Posts: 11
Joined: Tue Jul 16, 2002 1:03 pm

Post by karl » Wed Jul 17, 2002 8:27 pm

first of all:

don't send your acm-ID (21201...) here!


second:

what was judge's reply: WA or Compile Error?
I got compile error, because <stdio.h> wasn't included.


best wishes!

karl

vivid
New poster
Posts: 6
Joined: Tue Jul 16, 2002 6:31 pm

Post by vivid » Wed Jul 17, 2002 11:10 pm

What does Lexicographically mean?
For example what is first in lexicographical order
1 1 1 3 4
or
1 10 9 8 7
??
Maybe it is your problem?

youngwook
New poster
Posts: 5
Joined: Wed Jul 17, 2002 8:15 am
Location: Seoul

Post by youngwook » Thu Jul 18, 2002 1:23 am

karl wrote:first of all:

don't send your acm-ID (21201...) here!
ok.. thanx :D
karl wrote:what was judge's reply: WA or Compile Error?
I got compile error, because <stdio.h> wasn't included.
i got WA..
Your program has not solved the problem. It ran during 0.670 seconds.
.......!!

youngwook
New poster
Posts: 5
Joined: Wed Jul 17, 2002 8:15 am
Location: Seoul

Post by youngwook » Thu Jul 18, 2002 1:45 am

vivid wrote:What does Lexicographically mean?
For example what is first in lexicographical order
1 1 1 3 4
or
1 10 9 8 7
??
Maybe it is your problem?
i think '1 1 1 3 4' is right ans.
isn't it first? :o

wenzhi cai
New poster
Posts: 9
Joined: Sat Jun 29, 2002 10:59 am
Location: china
Contact:

question about 116

Post by wenzhi cai » Mon Jul 22, 2002 4:17 pm

Can anyone tell me what does "Lexicographically" mean?
Is sequence "1 2 3 4" less than "4 3 2 1"? :(

User avatar
Chung Ha, Yun
New poster
Posts: 19
Joined: Tue Jul 16, 2002 5:56 pm
Location: Seoul
Contact:

Lexicographically

Post by Chung Ha, Yun » Tue Jul 23, 2002 5:35 am

Sequence "1,2,3,4" is less than "4,3,2,1" Lexicographically.

Answer sequence is minimum Lexicographically sequence...^^;;;

wenzhi cai
New poster
Posts: 9
Joined: Sat Jun 29, 2002 10:59 am
Location: china
Contact:

Post by wenzhi cai » Tue Jul 23, 2002 10:48 am

Then I really can't understand why I get WA.Is there anything tricky in this problem? :(

przygoda
New poster
Posts: 7
Joined: Fri Aug 09, 2002 12:26 pm
Location: Poland

116 - Unidirectional TSP

Post by przygoda » Fri Aug 09, 2002 12:31 pm

Please help me
What is wrong with my code ???

Code: Select all

[/pascal]
  program od_nowaaaa;

   var
   t:array[1..10,1..110] of longint;
    k:array[1..10,1..110,1..2] of longint;
     i1,min,pom,n,m,i,j,a:longint;
      wynik,posrednik:array[1..110] of longint;

  procedure prepare;
   begin

   for i:=1 to n do
    for j:=1 to m do begin
     k[i,j,1]:=2147483647;
      k[i,j,2]:=15;
       end;
    end;

 begin

    while not eof do begin
     readln(n,m);
      prepare;
       i:=1;j:=0;
     while (i<>n) or (j<>m) do begin
      while not eoln do begin
       read(a);
        inc(j);
       if j > m then begin
         inc(i);
          j:=1;
           end;
       t[i,j]:=a;
        end;
         readln;
          end;

     for i:=1 to n do
      k[i,1,1]:=t[i,1];

    for j:=1 to m-1 do
     for i:=1 to n do begin

      pom:=i-1;
      if pom=0 then pom:=n;

     if k[pom,j+1,1] > k[i,j,1]+t[pom,j+1] then begin
         k[pom,j+1,1]:=k[i,j,1]+t[pom,j+1] ;
          k[pom,j+1,2]:=i;
           end
     else
       if (k[pom,j+1,1] = k[i,j,1]+t[pom,j+1]) and (k[pom,j+1,2] > i) then
           k[pom,j+1,2]:=i;

     pom:=i;

       if k[pom,j+1,1] > k[i,j,1]+t[pom,j+1] then begin
         k[pom,j+1,1]:=k[i,j,1]+t[pom,j+1] ;
          k[pom,j+1,2]:=i;
           end
     else
       if (k[pom,j+1,1] = k[i,j,1]+t[pom,j+1]) and (k[pom,j+1,2] > i) then
           k[pom,j+1,2]:=i;

    pom:=i+1;
     if pom > n then pom:=1;

         if k[pom,j+1,1] > k[i,j,1]+t[pom,j+1] then begin
         k[pom,j+1,1]:=k[i,j,1]+t[pom,j+1] ;
          k[pom,j+1,2]:=i;
           end
     else
       if (k[pom,j+1,1] = k[i,j,1]+t[pom,j+1]) and (k[pom,j+1,2] > i) then
           k[pom,j+1,2]:=i;

     end;

  min:=2147483647 ;
                   for i:=1 to 105 do   wynik[i]:=11;

   for i:=1 to n do
     if k[i,m,1] < min then min:=k[i,m,1] ;

     for i:=1 to n do
      if k[i,m,1] = min then   begin

    i1:=i;
     posrednik[m+1]:=i;

       for pom:=m  downto  1  do begin
      posrednik[pom]:=k[i1,pom,2];
       i1:=k[i1,pom,2];
        end;

    i1:=m+2;
   while wynik[i1]= posrednik[i1] do dec(i1);
    if wynik[i1] > posrednik[i1] then
     for i1:=1 to m+2 do
      wynik[i1]:=posrednik[i1];

       end;

    for i:=2 to m do
     write(wynik[i],' ');
      write(wynik[m+1]);
       writeln;
        writeln(min);

   for i:=1 to 105 do posrednik[i]:=11;




 end;
end.
Please help me

zerocool
New poster
Posts: 7
Joined: Wed May 15, 2002 10:30 am
Location: Kaohsiung,Taiwan
Contact:

Post by zerocool » Tue Sep 10, 2002 4:51 pm

Input :
6 8
9 1 9 9 1 1 1 1
1 9 9 1 9 9 9 9
9 9 1 9 9 1 1 1
1 1 9 9 1 9 9 9
9 9 9 1 9 9 9 9
9 9 1 9 9 9 9 9

Output
2 1 6 5 4 3 3 3
8

Try Try ..^_^..I wish this can help you..
A mediocrityboy

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

Post by Dominik Michniewski » Thu Sep 12, 2002 8:23 am

I got the same result as you post, but I got WA after rejudgement too.... Is any trap (after rejudgement) in this problem ??

Dominik Michniewski

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Post by arc16 » Sat Sep 14, 2002 6:13 am

Please help...
I'm getting TLE by using DFS. :cry:
Is there any faster method?

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar » Thu Sep 19, 2002 5:33 pm

arc16 wrote:I'm getting TLE by using DFS.
Is there any faster method?
I think that this problem can be solved using DP. And i think that DP is a LOT more efficient that DFS.

Hope this can help.
Those Who Don't Know History are doomed to repeat it

Post Reply

Return to “Volume 1 (100-199)”