116  Unidirectional TSP
Moderator: Board moderators

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
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 inputreading routine, then got AC back...
Did you try to mail the administrators ?
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 inputreading routine, then got AC back...
Did you try to mail the administrators ?

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

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
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
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

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
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
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

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
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.
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.

 Experienced poster
 Posts: 145
 Joined: Sat Feb 23, 2002 2:00 am
 Location: Paris, France
 Contact:
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
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

 Experienced poster
 Posts: 114
 Joined: Wed Jul 30, 2003 10:30 pm
 Location: Newfoundland, Canada (St. John's)
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
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

 New poster
 Posts: 5
 Joined: Wed Oct 22, 2003 3:29 am
 Location: dhaka
 Contact:
116::::HELP!!!!!!
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=(i1+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=c2; 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<c1; i++){
ansrow=path[ansrow][i];
printf("%ld ",(ansrow+1));
}
printf("\n");
printf("%ld\n",ans);
}
}
[/cpp]
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=(i1+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=c2; 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<c1; i++){
ansrow=path[ansrow][i];
printf("%ld ",(ansrow+1));
}
printf("\n");
printf("%ld\n",ans);
}
}
[/cpp]
Unidirectional TSP(116)
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,i1];
sm:=m;
end
else
begin
t:=b[j1,i1];
sm:=j1;
end;
if t>b[j,i1] then
begin
t:=b[j,i1];
sm:=j;
end else
if t=b[j,i1] then
if findi(sm,i1)>findi(j,i1) then sm:=j;
if j=m then
begin
if t>b[1,i1] then
begin
t:=b[1,i1];
sm:=1;
end else
if t=b[1,i1] then
if findi(1,i1)<findi(sm,i1) then
begin
sm:=1;
t:=b[1,i1];
end;
end
else
if t>b[j+1,i1] then
begin
t:=b[j+1,i1];
sm:=j+1;
end else
if t=b[j+1,i1] then
if findi(j+1,i1)<findi(sm,i1) then
begin
t:=b[j+1,i1];
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}
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,i1];
sm:=m;
end
else
begin
t:=b[j1,i1];
sm:=j1;
end;
if t>b[j,i1] then
begin
t:=b[j,i1];
sm:=j;
end else
if t=b[j,i1] then
if findi(sm,i1)>findi(j,i1) then sm:=j;
if j=m then
begin
if t>b[1,i1] then
begin
t:=b[1,i1];
sm:=1;
end else
if t=b[1,i1] then
if findi(1,i1)<findi(sm,i1) then
begin
sm:=1;
t:=b[1,i1];
end;
end
else
if t>b[j+1,i1] then
begin
t:=b[j+1,i1];
sm:=j+1;
end else
if t=b[j+1,i1] then
if findi(j+1,i1)<findi(sm,i1) then
begin
t:=b[j+1,i1];
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}

 Learning poster
 Posts: 82
 Joined: Thu Oct 10, 2002 1:15 pm
 Location: St. Johns, Canada
 Contact:
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
http://www.acmbeginner.tk
M H Rasel
CUET Old Sailor
116 WA??
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
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

 New poster
 Posts: 22
 Joined: Fri Jan 04, 2002 2:00 am
116 WA.. Correct on all posted input in the forums
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;
}