## 116 - Unidirectional TSP

Moderator: Board moderators

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
How I do I generate the solutions in lexicographical order? I try to use a solution matrix but it exceeds the timelimit. I have already a working DP solution, I just can't find a way to enumerate all the solutions and find the lexicographically smallest.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
If you will find the good DP algorithm (O(n*m)), you will find the way to print out the lexicographically smallest path. Consider that you shouldn't enumerate all the minimal paths, you are to determine theirs weight, and only one path.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
I have a way to enumerate A solution. It just isn't the lexicographically smallest.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
It's hard to help without telling the whole algorithm.
Try to use the following DP algorithm:
if the board is M*N, solve the problem first the Nth column, then the boart from N-1th column to Nth column, an so on. Finally, if you store the correct datas, it's easy to tell the lexicographically smallest path, with minimal weight.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
I know the DP part. How do you determine which is the right path?

If you have your optimized matrix as:
3 6 9
3 6 9

Do you choose the top 9 or the bottom 9.

Here is my code:

Code: Select all

``````#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int> > X,D;
vector<int> S;
int M,N;

int V(int i,int j)
{
int A,B,C,S;
if(j<=0)
return 0;
A=X[i][j-1];
B=X[(i+M-1)%M][j-1];
C=X[(i+1)%M][j-1];
S=A<(B<C?B:C)?A:(B<C?B:C);
D[i][j]=1;
if(A==S)D[i][j]*=2;
if(B==S)D[i][j]*=3;
if(C==S)D[i][j]*=5;
return S;
}

void makesols(int n,int l,vector<int> R)
{
R.push_back(l+1);

if(n==0)
{
reverse(R.begin(),R.end());
if(S.empty())
S=R;
else
if(R<S)
S=R;
return;
}

if(D[l][n]%2==0)
makesols(n-1,l,R);
if(D[l][n]%3==0)
makesols(n-1,(l+M-1)%M,R);
if(D[l][n]%5==0)
makesols(n-1,(l+1)%M,R);
}

void main()
{
int i,j,k,m;
vector<int> R;

while(scanf("%d%d",&M,&N)!=EOF)
{
X=vector<vector<int> >(M,vector<int>(N,0));
D=X;
R.clear();
S.clear();
for(i=0;i<M;i++)
for(j=0;j<N;j++)
scanf("%d",&X[i][j]);
for(j=1;j<N;j++)
{
for(i=0;i<M;i++)
{
X[i][j]+=V(i,j);
}
}

m=X[N-1];
for(i=1;i<M;i++)
{
if(X[i][N-1]<m)m=X[i][N-1];
}
for(i=0;i<M;i++)
{
if(X[i][N-1]==m)
{
makesols(N-1,i,R);
k=i;
}
}
for(i=0;i<S.size();i++)
{
if(i)
printf(" ");
printf("%d",S[i]);
}

printf("n%dn",X[k][N-1]);
}
}
``````

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
You should start with the last column, not the first. Then, you can select the starting field easy.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
What if there are multiple paths within each starting field?

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
First, you should select the topmost field with minimal path-weight at the first collumn. Then, you should select the tompost field with minimal weight what is reachable from the currect field, and so on.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Thanks. I will give it a try.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Thanks again, problem solved.

hsihsiwu
New poster
Posts: 9
Joined: Fri Apr 12, 2002 2:27 am

### 116-What is lexicographically smallest path?

"If there is more than one path of minimal weight the path that is lexicographically smallest should be output."
Above is from question.

My English is not very good,so I don't understand What is lexicographically smallest path?Can you make an example?

Thanks.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Sure thing. Lexicographically means in order.
Thus:
1 2 3 4 is lexicographically smaller than 4 2 1 3.

Think of it as alphabetical or numerical sorting. If all the solutions were put in an array, and then sorted, which would be first.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
I think that's a bit misleading. And how is he supposed to know how to sort it when he doesn't understand the comparison?

I'd say, a list A=(a1,...,an) is lexicographically smaller than a list B=(b1,...,bm) if they are the same at the beginning (ai=bi for 1<=i<k) and then either
1) n=k-1 and m>=k (i.e., A ends and B doesn't) or
2) n>=k and m>=k and ak<bk (i.e. the next element of A is smaller than the next of B).

Or, to state it in a formal language:

Code: Select all

``````bool lexicoSmaller ( int a[], int n, int b[], int m ) {
for( int i=0; i<n && i<m; ++i )
if( a[i] != b[i] )
return a[i] < b[i];
return n < m;
}
``````

hsihsiwu
New poster
Posts: 9
Joined: Fri Apr 12, 2002 2:27 am
I got it.
Thanks you guys very much.

mark00lui
New poster
Posts: 6
Joined: Wed May 22, 2002 6:49 pm
Contact:

### help in Problem 116

The WA problem confused me at all!!! The sample input which my program can do in right way, but the judge gave me WA......

there is the code

Code: Select all

``````[c]
#include<stdio.h>

void WriteSumAndPath(long array[], long *upper, long *middle, long *down)
{
long smallest=*middle, path=*(middle+1);
long uppersum=*upper, middlesum=*middle, downsum=*down;
long upperpath=*(upper+1), middlepath=*(middle+1), downpath=*(down+1);

/*compare the smaller value*/
if(uppersum<middlesum)
{
smallest=uppersum;
path=upperpath;
}
/*get the small list path when the smaller value equit*/
else if(uppersum==middlesum)
path=(upperpath>middlepath)? middlepath: upperpath;

/*compare the smallest value*/
if(downsum<uppersum&&downsum<middlesum)
{
smallest=downsum;
path=downpath;
}
/*get the smaller path when the smaller value equit*/
else if(downsum==uppersum&&downsum<middlesum)
path=(downpath>upperpath)? upperpath: downpath;
else if(downsum==middlesum&&downsum<uppersum)
path=(downpath>middlepath)? middlepath: downpath;

array+=smallest;
array=path;
}

int main(void)
{
int maxcol=0, maxrow=0;

while(2==scanf("%d %d", &maxcol, &maxrow))
{
long array;
int ccol=0, crow=0;
long minsum=0;
int path=0;

for(ccol=0; ccol<maxcol; ccol++) /*scan*/
for(crow=0; crow<maxrow; crow++)
{
scanf("%d", &array[ccol][crow]);
array[ccol][crow]=ccol+1; /*set the initial path value*/
}

for(crow=maxrow-2; crow>=0; crow--)/*do the sum start at last two row and end at the first row*/
for(ccol=0; ccol<maxcol; ccol++)
{
/*count the suitable colume value*/
int uppercol=(ccol-1<0)? maxcol-1: ccol-1,
middlecol=ccol,
downcol=(ccol+1>=maxcol)? 0: ccol+1;
/*gave the sum and list path from the next row*/
long upper={array[uppercol][crow+1], uppercol+1},
middle={array[middlecol][crow+1], middlecol+1},
down={array[downcol][crow+1], downcol+1};

/*write in the sum and path*/
WriteSumAndPath(array[ccol][crow], upper, middle, down);
}

/*the smallest value in the row1 is the smallest sum answer*/
for(minsum=array, path=1, ccol=1; ccol<maxcol; ccol++)
if(array[ccol]<minsum)
{
minsum=array[ccol];
path=ccol+1;
}

printf("%d", path);
for(crow=0; crow<maxrow-1; crow++)
{
/*the second elemtry is the path of the next row and can find recursivly*/
path=array[path-1][crow];
printf(" %d", path);
}

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

}

return 0;
}[/c]``````