116 - Unidirectional TSP

[Julien Cornebise]

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]

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

[xbeanx]

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]

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]

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.

[ezra]

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]

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]

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)]

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]

try reading from stdin and writing to stdout.

[Sensor]

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]

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]

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]

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;
}

[shamim]

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.