## 116 - Unidirectional TSP

Moderator: Board moderators

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
Ok
a fibonacci series is like

Code: Select all

``1 1 2 3 5 8 13 ...``
Now if you trying to find n(th) fibonacci..
you may try recursion

Code: Select all

``````fib(int n){
if(n==1||n==2)return 1;
else return fib(n-1)+fib(n-2);
}``````
Here for fib(5)

Code: Select all

``````fib(5)=              fib(4)                          +                     fib(3)
fib(4) =     fib(3)        +  fib(2)             fib(3)=fib(2)+fib(1)
fib(3)=fib(1)+fib(2)
``````
the tree look like this

Code: Select all

``````
5
/        \
4          3
/   \       /  \
3     2     2    1
/ \
2  1``````
look at the tree
fib(3) calculated 2 times
fib(2) 3 times
fib(1) 2 times

these overlapping should be optimized by dp
see DP solution here using an array fib[n]

Code: Select all

``````fib=fib=1;
for(j=3;j<=n;j++)fib[j]=fib[j-1]+[j-2]``````
it is linear algorithm
do you understand this sample of DP approach?

OH yes you may visit here
http://online-judge.uva.es/board/viewtopic.php?t=10565
some more discussion is going there

Beenuxers
New poster
Posts: 6
Joined: Mon Mar 13, 2006 6:29 am
Location: Jakarta
Contact:
Hi, Arif... Thanks for ur sample and reference ... I can understand it... Now i'm gonna fix my code... Thx.... Do better for a better tomorrow.... Beenuxers
New poster
Posts: 6
Joined: Mon Mar 13, 2006 6:29 am
Location: Jakarta
Contact:

### Finally i got acc... :D

I have changed my dp technique, so i got acc... What i don't realize so far is i do not need to trace the path one by one, i only need to store the minimum value for the path... And also i just realized that the dp table can help me to print the path... ^^.
Last edited by Beenuxers on Sat May 27, 2006 7:56 am, edited 1 time in total.
Do better for a better tomorrow.... emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
it just spoils the program
so remove it immedieately
congaratulation for getting AC

Beenuxers
New poster
Posts: 6
Joined: Mon Mar 13, 2006 6:29 am
Location: Jakarta
Contact:
Ok... I've already removed my code... ^^.
Do better for a better tomorrow.... sangram
New poster
Posts: 8
Joined: Fri Jun 30, 2006 3:27 pm
Contact:

### Problem 116 - Presentation Error !

Can anyone please tell me what can be wrong in my code ? I am not posting it here as it is already accepted ... but I got a presentation error.

For the test input given on the problem page, I seem to be getting the exactly same output.

Dzhefri
New poster
Posts: 8
Joined: Mon May 15, 2006 8:46 am

### 116 - using DP, but still TLE

This, essentially, is my algorithm:
• Read data into a matrix (the data matrix)
Create another matrix (the sum matrix), the last column of which is copied from the data matrix
For each column (except the last) of the data matrix, starting from the last column:
• For each element of that column:
• Look at the corresponding position on the sum matrix, and then look at the 3 elements to the right (i.e., directly to the right, to the upper right, and the lower right). Select the lowest of these 3 values.
Into the corresponding position of the sum matrix (i.e., the position to the left of the 3 elements mentioned above), write (element selected above + current data-matrix element)
Select the element of the first column whose value is lowest, and return that.
Of course, it's slightly more complicated, because you have to keep track of the path that led to this minimum weight, but with all this taken into account, this algorithm is still O(n*m), (where m and n are the dimensions of the input) right? Why then do I always get TLE?? Here's my code:

Code: Select all

``````
#include <iostream>
#include <vector>
#include <deque>
#include <map>
using namespace std;

struct path_sum {
deque<int> path;
int sum;
path_sum(deque<int> p, int s): path(p), sum(s) {}
path_sum(path_sum ps, int p, int s) {
path = ps.path;
sum = ps.sum;
path.push_front(p);
sum += s;
}
};

//note that this would mess up if b is not positive
const int mod(int a, int b) {
if (a >= 0) return a%b;
else {
a += b;
return mod(a,b);
}
}

int main() {
int x, y;
while (cin >> x) {
cin >> y;
vector<vector<int> > matrix;
for (int i = 0; i < x; ++i) {
vector<int> iv;
for (int j = 0; j < y; ++j) {
int temp;
cin >> temp;
iv.push_back(temp);
}
matrix.push_back(iv);
}

map<int, map<int, path_sum> > bp_matrix; //best path matrix, i.e., info on the best path from that element

//initialize the last column of bp_matrix
for (int i = 0; i < x; ++i) {
deque<int> temp_id;
temp_id.push_front(i);
path_sum temp_ps(temp_id, matrix[i][y-1]);
bp_matrix[i][y-1] = temp_ps;
}

//fill in the rest of bp_matrix
for (int i = y - 2; i >= 0; --i) {//for each column
for (int j = 0; j < x; ++j) { //for each element in each column
//find the optimal element whose y is one more than this
//and whose x is mod(+- 1 of this, x)
int opt_elem = mod(j - 1, x); //i.e., the x coordinate of the presumed optimal element
//which we initialize with 1 less
//comare the assumed opt_elem to the other two possibilities
for (int k = 0; k <= 1; ++k) {
if (bp_matrix[opt_elem][i+1].sum > bp_matrix[mod(j+k,x)][i+1].sum) {
opt_elem = mod(j+k,x);
} else if ((bp_matrix[opt_elem][i+1].sum == bp_matrix[mod(j+k,x)][i+1].sum) && (mod(j+k,x) < opt_elem)) {
opt_elem = mod(j+k, x);
}
}

path_sum temp_ps(bp_matrix[opt_elem][i+1], j, matrix[j][i]);
bp_matrix[j][i] = temp_ps;
}
}

//find the optimal path and report

int opt_path = 0;
for (int i = 1; i < x; ++i) {
if (bp_matrix[i].sum < bp_matrix[opt_path].sum) {
opt_path = i;
}
}

for (int i = 0; i < bp_matrix[opt_path].path.size(); ++i) {
cout << bp_matrix[opt_path].path[i]+1 << " ";
}
cout << endl << bp_matrix[opt_path].sum << endl;
}
}

``````

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

anyone pls help me.......... i got several wa in 116...
i tried to solve it dynamically... by storing possible paths with respedtive costs and for paths i stored a parent array...
from the last column i traversed back for lexicografically smallest path...
my output is okay for all the inputs found in this board....
i cant find what i'm missing...
help pls.........
source code's here:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 105

typedef struct
{
long in;
long long val;
}
beta;

int comp(const void *a,const void *b)
{
beta *x,*y;

x=(beta *)a;
y=(beta *)b;

if( x->val == y->val) return (int)(x->in - y->in);
return (int)(x->val - y->val);
}
beta tt;
char min_path[N],temp[N];
long all_paths[N][N],end,r,c,count,point;
long long all[N][N],mat[N][N],pre[N][N],cost;
void print_path(long row,long col);

void main()
{
//freopen("hati.txt","r",stdin);
long i,j,k=0;

while( scanf("%ld%ld",&r,&c) == 2)
{
if(k !=0) printf("\n");
k++;
for(i=0; i<r; i++)
for(j=0; j<c; j++) scanf("%lld",&mat[i][j]);

for(i=0; i<r; i++)
{
all[i]=mat[i];
pre[i]=-1;
}

for(i=1; i<c; i++)
{
for(j=0; j<r; j++)
{
tt.in=(r+j-1)%r;
tt.val=all[(r+j-1)%r][i-1];

tt.in=j;
tt.val=all[j][i-1];

tt.in=(j+1)%r;
tt.val=all[(j+1)%r][i-1];

qsort(tt,3,sizeof(beta),comp);

all[j][i]=mat[j][i]+ tt.val;
pre[j][i]=tt.in;
}
}
cost=all[c-1];
end=0;

for(i=1; i<r; i++)
{
if( all[i][c-1] < cost )
{
cost=all[i][c-1];
end=i;
}
}
count=0;
for(i=end; i<r; i++)
{
if( all[i][c-1] == cost)
{
print_path(i,c-1);
count++;
}
}
for(i=0; i<c; i++) min_path[i]=(char)(all_paths[i]+'0');
min_path[i]='\0';
point=0;
for(i=0; i<count; i++)
{
for(j=0; j<c; j++) temp[j]=(char)(all_paths[i][j]+'0');
temp[j]='\0';
if( strcmp(temp,min_path) < 0)
{
strcpy(min_path,temp);
point=i;
}
}
for(i=0; i<c; i++)
{
if( i != 0)printf(" %ld",all_paths[point][i]+1);
else printf("%ld",all_paths[point][i]+1);
}

printf("\n%lld",cost);

}
}

void print_path(long row,long col)
{
if( pre[row][col]== -1 )
{
all_paths[count][col]=row;
return;
}
print_path((long)pre[row][col],col-1);
all_paths[count][col]=row;
return;
}
``````
thanks ........

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

### Re: 116 wa..........asking for help!!

I don't know what is wrong in your code, but please check this input.
BJM wrote:http://online-judge.uva.es/board/viewto ... 4&start=15

Code: Select all

``````4 29
1 -1 0 0 1 -1 -1 -1 1 1 0 1 -1 -1 -1 0 -1 -1 1 -1 1 0 0 -1 0 -1 1 1 0
-1 1 0 -1 -1 0 1 0 -1 -1 -1 -1 1 1 0 -1 -1 0 -1 -1 1 -1 1 0 -1 1 0 1 -1
0 0 1 0 -1 1 0 0 1 1 0 -1 1 1 -1 -1 1 0 0 1 1 0 -1 1 0 -1 -1 1 1
1 -1 -1 -1 -1 -1 0 0 0 1 -1 0 0 0 -1 -1 0 -1 0 1 0 -1 1 0 1 1 -1 0 1
``````
Output is :

Code: Select all

``````2 1 4 4 3 4 1 1 2 2 2 2 1 1 1 2 1 1 2 1 4 4 1 1 2 1 4 1 2
-25
``````
By the way,
you should not make new thread if there are any same threads already in the board, as you know.

Best regards.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
hi all for this problem i use left to right dynamic programming so i m getting the
total minimum cost but i m not getting how to find out lexicographically
shortest path .here is my code ....plz explain ur
algorithm to find lexicographically shortest path.i could not understand ur algorithm sunnycare .my program works fine if one path exist but if more than one path exist then
it's not giving lexicographically smallest path.what i m doing is
i m finding last column(n-1) minimum value and note down the row number (let
it be i).now in second last column(n-2) i searched out minmium value in row
i-1,i and i+1 becoz of problem property. and i keep doing this until i reach
the 0th column.doing this i m not getting what i suppose to find out
...lexicographically smallest path.plz help...

Code: Select all

``````#include<stdio.h>

int min1(int k,int m,int n)
{
int min;
min=k;
if(min>m)
min=m;
if(min>n)
min=n;
return(min);
}
main()
{

int m1,a,i,j,m,n,min,k,arr,t,min2,t1,t2,t3,v1;
while(scanf("%d%d",&m,&n)==2)
{
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);

for(i=0;i<m;i++)
m1[i]=a[i];
for(j=1;j<n;j++)
for(i=0;i<m;i++)
m1[i][j]=a[i][j]+min1(m1[(i+m-1)%m][j-1],m1[i][j-1],m1[(i+1)%m][j-1]);

/*for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%d    ",m1[i][j]);
printf("\n");
}
printf("\n");*/
min2=m1[n-1];
k=0;
for(i=1;i<m;i++)
if(m1[i][n-1]<min2)
{
min2=m1[i][n-1];
k=i;

}
//printf("k=%d min=%d\n",k+1,min2);
arr[n-1]=k;
//printf("min=%d arr[%d]=%d\n",min2,n-1,arr[n-1]);
for(j=n-2;j>=0;j--)
{
//printf("j=%d ",j);
min=m1[(arr[j+1]+m-1)%m][j];
t1=(arr[j+1]+m-1)%m;
t=t1;
if(min>m1[arr[j+1]][j])
{
min=m1[arr[j+1]][j];
t2=arr[j+1];
t=t2;
}
else if(min==m1[arr[j+1]][j])
{
t2=arr[j+1];
if(t1>t2)
t=t2;
else
t=t1;
}

if(min>m1[(arr[j+1]+1)%m][j])
{
min=m1[(arr[j+1]+1)%m][j];
t3=(arr[j+1]+1)%m;
t=t3;

}

else if(min==m1[(arr[j+1]+1)%m][j])
{
t3=(arr[j+1]+1)%m;
if(t>t3)
t=t3;
}
arr[j]=t;
//printf("min=%d arr[%d]=%d\n",min,j,t);
}

for(i=0;i<=n-1;i++)
printf("%d ",arr[i]+1);
printf("\n%d\n",min2);
}
}``````
[/color]

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Calculate the table from right to left. Then it would be easier to find the lexicographically smallest path.
Ami ekhono shopno dekhi...
HomePage

niangjun
New poster
Posts: 3
Joined: Mon Dec 18, 2006 11:40 am
My prog worked for all the input given, but it still get WA, who can help me?

Code: Select all

``````program acm116;
type aa=array[1..100] of integer;
var a,d:array[1..100,1..100] of integer;
f:array[1..10,1..100] of longint;
rec1:aa;
m,n:integer;    cost:longint;
num:integer;

procedure init;
var i,j,k:integer;
begin
fillchar(a,sizeof(a),0);
for i:=1 to m do
for j:=1 to n do read(a[i,j]);
end;

procedure calc;
var i,j,k,l,h:integer;
o:array[1..3] of integer;
begin
fillchar(f,sizeof(f),0);
for i:=1 to m do f[i,n]:=a[i,n];
for j:=n-1 downto 1 do
for i:=1 to m do
begin
if (i>1) then o:=i-1 else o:=m;
if (i<m) then o:=i+1 else o:=1;
o:=i;
f[i,j]:=f[o,j+1];
for k:=2 to 3 do if (f[o[k],j+1]<f[i,j]) then f[i,j]:=f[o[k],j+1];
f[i,j]:=f[i,j]+a[i,j];
end;
end;

procedure backtrack;
var i,j,k,h,x:integer;      l:longint;
o:array[1..3] of integer;
begin
cost:=f[1,1];
for i:=2 to m do if (cost>f[i,1]) then cost:=f[i,1];
k:=1;
while (k<=m) and (cost<>f[k,1]) do k:=k+1;
rec1:=k;
l:=cost-a[k,1];
for j:=2 to n do
begin
if (k>1) then o:=k-1 else o:=m;
if (k<m) then o:=k+1 else o:=1;
o:=k;
x:=m+1;
for h:=1 to 3 do if (f[o[h],j]=l) and (o[h]<x)
then x:=o[h];
k:=x;
rec1[j]:=k;
l:=l-a[k,j];
end;
end;

procedure output;
var i:integer;
begin
for i:=1 to n-1 do write(rec1[i],' ');
writeln(rec1[n]);
writeln(cost);
end;

begin
while not eof do
begin
m:=0; n:=0;
if(m*n<>0) then begin
init;
calc;
backtrack;
output;
end;
end;
end.
``````
Thanks!

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
thnkx for reply and sorry for late response ....
i did not get how to calculate table from right to left ...plz tell me the algorithm ....

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Imagine that you have to go from right to left. So,

Code: Select all

``````table[i][j] = min( table[(i+1)%row][j+1], table[i%row][j+1], table[(i-1)%row][j+1] );
mark[i][j] = i-1 or i or i+1 (which contains the least value)``````
Now the least value in the 0th column will be the starting position. And continue your process using the mark array.

Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm
In my code i changed:

Code: Select all

``        scanf("%d",&T[i][j]);``
to:

Code: Select all

``        scanf("%d",&T[i][m-j+1]);``

Code: Select all

``````    for(j=1; j<m; j++){
printf("%d ",O[j]);
} printf("%d\n",O[m]);``````
to:

Code: Select all

``````    for(j=m; j>1; j--){
printf("%d ",O[j]);
} printf("%d\n",O);``````
And i get ACC 