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

Post Reply
Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Thu Aug 21, 2003 3:15 pm

I've just tried two things : first in C, replacing scanf("%d"...) by a hand made function to deal such things as "- 3". WA. I then tried with cin >>, changing my prog to C++. WA too :(
I'm a bit confused. I read in earlier threads that some people also had troubles with reading input on this very problem. Some even had AC before the rejudging that happenned some monthes ago, and then got WA when it happened. They changed the input-reading routine, then got AC back...
Did you try to mail the administrators ?

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Thu Aug 21, 2003 3:29 pm

That's weird : I tried to TLE when token == "- " but it did not happen... ??

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Thu Aug 21, 2003 3:33 pm

Well I increased my input buffer and I am no longer getting an exception.

But I still have WA. :(

So I'm wondering if it is the same problem others are facing. I'm going to check out some more posts here and see if I can figure it out.

BTW, I have an accepted C++ version if you are interested. But it is exactly the same as my above java program, so you won't be seeing anything new.

I'm giving up on this.... As far as I'm concerned, my program is correct. If you ever find out where your problem is I'd love to know!

Greg

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Thu Aug 21, 2003 4:35 pm

I can't figure out what's wrong with my program neither... I'd be interested by your C++ AC code if you don't mind... To avoid posting it on the forum, here's my mail if it doesn't annoy you to send it to me :
julien.cornebise@wanadoo.fr
I'll thus be able to check the reading of the input...
If I ever understand what's going wrong, I 'll tell you ! Thanks :)

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Thu Aug 21, 2003 5:20 pm

Well, I hate to admit that I am a total idiot.

My first problem with the exception was fixed by increasing the input buffer. The reason I was getting WA was because inside one of my if() statements I was comparing the wrong vars.

In my code, the line reading
} else if(costs[(minPos+1)%m][j] == min && minPos < tmp) {
should be
} else if(costs[(minPos+1)%m][j] == min && (minPos+1)%m < tmp) {

Damnit I am such a goof.

Well, if you want any help with your program I'd be happy to try. Although, I must admit that after spending so much time looking at my own code I'd probably just miss the bug anyway.

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by ezra » Mon Aug 25, 2003 6:23 pm

at the first time i always get wa too,cause i construct the dp from leftside to rightside. And then my generous frient told me to reverse it. And when i contruct from rightside to leftside i got AC..
if you got the same trouble as mine, try to follow my friend's advice.
Sorry for bad english....

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Mon Aug 25, 2003 6:43 pm

Hi ezra and xbeanx
I have finally rewritten my source from scratch, now doing it from right to left, as you did in your code Greg, and I got AC too.
I'm still wondering why my Left to right failed (given that I stored the path and compared it lexicographically every time...).... Anyway, must be a dumb thing.
Thks once again for your help Greg :)

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Mon Aug 25, 2003 6:53 pm

I also tried this from left to right, and it works that way also. The only thing is, when printing, you have to read it from right to left.

Either way it can be done, but if you do it right to left first, you can simply print the solution. If you do it left to right first, the solution must be pushed onto a stack and printed as popped.

Does that make sense? Not to me. :) hehe

shamim(aiub)
New poster
Posts: 5
Joined: Wed Oct 22, 2003 3:29 am
Location: dhaka
Contact:

116::::HELP!!!!!!

Post by shamim(aiub) » Tue Nov 04, 2003 1:23 pm

I got WA.But I didn't find any mistake.
Plz somebody tell me why did i got WA?

[cpp]
#include<stdio.h>

long m[20][110],a[20][110],path[20][110];
long row,r,c;

long min(long i,long j){
long t,s=9999999;
t=(i-1+r)%r;
if(a[t][j+1]<s){
s=a[t][j+1];
row=t;}
if(a[j+1]<=s){
if(a[j+1]<s) row=i;
else if(i<row) row=i;
s=a[j+1];
}
t=(i+1)%r;
if(a[t][j+1]<=s){
if(a[t][j+1]<s) row=t;
else if(t<row) row=t;
s=a[t][j+1];
}
return s;
}



void main()
{
long i,j,ans,ansrow;
freopen("E:\\acm\\116.in","r",stdin);
freopen("E:\\acm\\116.out","w",stdout);
while(scanf("%ld%ld",&r,&c)!=EOF){
for(i=0; i<r; i++)
for(j=0; j<c; j++){
scanf("%ld",&m[j]);
a[j]=m[j];}
ans=9999999;
for(j=c-2; j>=0; j--)
for(i=0; i<r; i++){
row=999;
a[j]+=min(i,j);
path[j]=row;
if(j==0&&a[j]<ans){
ans=a[j]; ansrow=i;}
}
printf("%ld ",(ansrow+1));
for(i=0; i<c-1; i++){
ansrow=path[ansrow][i];
printf("%ld ",(ansrow+1));
}
printf("\n");
printf("%ld\n",ans);
}
}
[/cpp]

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Wed Nov 05, 2003 6:30 pm

try reading from stdin and writing to stdout.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Sensor
New poster
Posts: 4
Joined: Tue Nov 18, 2003 10:01 pm

Unidirectional TSP(116)

Post by Sensor » Sun Nov 23, 2003 9:57 pm

Please, help me.
This program passed all my tests but...
I have Worng Answer :(((
Can anybody give me a test where my program gives WA!
Thanks!

{@BEGIN_OF_SOURCE_CODE}
{ @JUDGE_ID: 37828FF 116 Pascal}
program proga;
var i,j:integer;
m,n,t,sm,min,posit:integer;
a,b,c:array[1..10,1..100] of integer;
{ p:array[1..10] of string[100];}
res:string;
{c - s kakogo ryada priskol; b - tekushaya tsena}

function findi(i,k:integer):string;
var j,z:integer;
t:string;
cc:char;
begin
t:='';
z:=i;
for j:=k downto 1 do
begin
t:=t+chr(z);
z:=c[z,j];
end;
for j:=1 to length(t) div 2 do
begin
cc:=t[j];
t[j]:=t[length(t)-j+1];
t[length(t)-j+1]:=cc;
end;
findi:=t;
end;

begin
while not eof(input) do
begin
read(m);
read(n);
for i:=1 to m do
for j:=1 to n do
read(a[i,j]);

for i:=1 to m do
begin
b[i,1]:=a[i,1];
c[i,1]:=i;
{ p:='';}
end;

for i:=2 to n do
for j:=1 to m do
begin
if j=1 then
begin
t:=b[m,i-1];
sm:=m;
end
else
begin
t:=b[j-1,i-1];
sm:=j-1;
end;
if t>b[j,i-1] then
begin
t:=b[j,i-1];
sm:=j;
end else
if t=b[j,i-1] then
if findi(sm,i-1)>findi(j,i-1) then sm:=j;
if j=m then
begin
if t>b[1,i-1] then
begin
t:=b[1,i-1];
sm:=1;
end else
if t=b[1,i-1] then
if findi(1,i-1)<findi(sm,i-1) then
begin
sm:=1;
t:=b[1,i-1];
end;
end
else
if t>b[j+1,i-1] then
begin
t:=b[j+1,i-1];
sm:=j+1;
end else
if t=b[j+1,i-1] then
if findi(j+1,i-1)<findi(sm,i-1) then
begin
t:=b[j+1,i-1];
sm:=j+1;
end;
b[j,i]:=a[j,i]+t;
c[j,i]:=sm;
{ p[j]:=p[sm]+chr(sm);}
end;

min:=b[1,n];
res:=findi(1,n);
{posit:=1;}
for i:=2 to m do
begin
if min>b[i,n] then
begin
min:=b[i,n];
res:=findi(i,n);
end
else
if min=b[i,n] then
if res>findi(i,n) then
res:=findi(i,n);
end;

for i:=1 to n do write(ord(res),' ');
writeln;
writeln(min);
end;
end.
{@END_OF_SOURCE_CODE}

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master » Mon Jan 05, 2004 6:26 am

I am not a pascal programmer. But you can get help from the following site.
http://www.acmbeginner.tk

M H Rasel
CUET Old Sailor

kgs
New poster
Posts: 1
Joined: Wed Feb 04, 2004 12:20 am

116 WA??

Post by kgs » Wed Feb 04, 2004 12:31 am

My program passes all test from this board, but I'm still getting WA. Why?
Could sb give me critical input?

Sorry for my english :>

[there was ACC code]

I've removed my code. It got ACC when I change reading input method, I've written own function with deals with spaces at the end of input but before EOF. If you use Pasacal and got WA in this problem you should do the same thing I've done.

There is this function:

[pascal]
function get_int : longint;
var
c : char;
r : longint;
minus : boolean;
begin
r := 0;
repeat
if eof(input) then halt(0);
read(c);
until c in ['0'..'9', '-'];
if c = '-' then
begin
read(c);
minus := TRUE;
end else
minus := FALSE;
while c in ['0'..'9'] do begin
r := 10*r + ord(c) - ord('0');
read(c);
end;
if minus then get_int := -r else get_int := r;
end;

begin
m := get_int;
n := get_int;
...
end;
[/pascal]

greetings, kgs

SilentStrike
New poster
Posts: 22
Joined: Fri Jan 04, 2002 2:00 am

116 WA.. Correct on all posted input in the forums

Post by SilentStrike » Sat Jun 19, 2004 10:09 am

Does someone have lots of test cases? I've tried everything I've seen on the board, and I've tried lots of 1xn, 2xn, nx1, and nx2 cases, and they have all worked.

Code: Select all

// http://acm.uva.es/p/v1/116.html

#include <iostream>
#include <climits>
using namespace std;

int rows; // 1 <= rows <= 10
int cols; // 1 <= cols <= 1000

const int max_rows = 1020;
const int max_cols = 1020;
int in[max_rows][max_cols];
int prev[max_rows][max_cols];
int sum[max_rows][max_cols];
int back[max_rows][max_cols];

void show_graph(int g[max_rows][max_cols]) {
  for (int i = 1; i <= rows; ++i) {
    for (int j = 1; j <= cols; ++j) {
      cout << g[i][j] << '\t';
    }
    cout << '\n';
  }
  cout << '\n';
}

int wrap_row(int dir, int i) {
  int selected_row = i + dir;
  if (selected_row == 0) selected_row = rows;
  if (selected_row > rows) selected_row = 1;
  return selected_row;
}

void play() {

  for (int i = 1; i <= rows; ++i) {
    sum[i][1] = in[i][1];
  }

  for (int j = 2; j <= cols; ++j) {
    for (int i = 1; i <= rows; ++i) {
      int best_sum=INT_MAX;
      for (int dir = -1; dir <= 1; ++dir) {
        int selected_row = wrap_row(dir, i);
        int selected_sum = in[i][j] + sum[selected_row][j - 1];
        if (selected_sum < best_sum) best_sum = selected_sum;
      }
      for (int dir = -1; dir <= 1; ++dir) {
        int selected_row = wrap_row(dir, i);
        int selected_sum = in[i][j] + sum[selected_row][j - 1];
        if (selected_sum == best_sum) prev[i][j] |= (1 << (dir + 1));
      }
      sum[i][j] = best_sum;
    }
  }
  
  int min_sum = sum[1][cols];
  for (int i = 1; i <= rows; ++i)
    if (sum[i][cols] < min_sum) min_sum = sum[i][cols];

  for (int i = 1; i <= rows; ++i) 
    if (sum[i][cols] == min_sum) back[i][cols] = 1;

  for (int j = cols; j > 1; --j) 
    for (int i = 1; i <= rows; ++i) 
      if (back[i][j]) 
        for (int k = 0; k < 3; ++k) 
          if (prev[i][j] & (1 << k)) {
            int back_track_row = wrap_row(k - 1, i);
            back[back_track_row][j - 1] = 1;
          }
  
  /*show_graph(sum);
  show_graph(prev);
  show_graph(back);*/

  int lex_best_row;
  for (int i = 1; i <= rows; ++i) 
    if (back[i][1]) {
      lex_best_row = i;
      break;    
    }
  
  if (cols == 1) {
    cout << lex_best_row << '\n' << min_sum << '\n';
    return;
  }
  cout << lex_best_row << ' ';
  for (int j = 2; j <= cols; ++j) {
    int cur_best_row=INT_MAX;
    for (int dir = -1; dir <= 1; ++dir) {
      int next_row = wrap_row(dir, lex_best_row);
      if (back[next_row][j]) {
        if (next_row < cur_best_row) cur_best_row = next_row;
      }
    }
    lex_best_row = cur_best_row;
    cout << lex_best_row;
    if (j != cols)  cout << ' ';
    else cout << '\n';
  }
  
  //show_graph(sum);
  cout << min_sum << '\n';
}

int main() {

  while (cin >> rows >> cols) {
    for (int i = 1; i <= rows; ++i) {
      for (int j = 1 ; j <= cols; ++j) {
        cin >> in[i][j];
        back[i][j] = prev[i][j] = 0;
      }
    }
    play();
  }

  return 0;
}

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Jun 19, 2004 2:10 pm

Well, I can't help you much, but to share some frustration. I am also getting WA. Mycode also passes, all the sample I/O I got from all sources.

I tried all sorts of combination, again and again, including the problem of lexicographical order. Till, today I have not solved the problem. :cry:

Post Reply

Return to “Volume 1 (100-199)”