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
C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Fri Mar 29, 2002 5:19 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:

Post by ftomi » Fri Mar 29, 2002 9:23 am

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
Location: Pasadena, CA

Post by C8H10N4O2 » Fri Mar 29, 2002 6:30 pm

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:

Post by ftomi » Fri Mar 29, 2002 9:55 pm

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
Location: Pasadena, CA

Post by C8H10N4O2 » Fri Mar 29, 2002 11:31 pm

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[0][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:

Post by ftomi » Sat Mar 30, 2002 7:46 am

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
Location: Pasadena, CA

Post by C8H10N4O2 » Sat Mar 30, 2002 10:39 pm

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:

Post by ftomi » Sun Mar 31, 2002 12:06 am

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
Location: Pasadena, CA

Post by C8H10N4O2 » Mon Apr 01, 2002 1:41 pm

Thanks. I will give it a try.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Apr 03, 2002 1:39 pm

Thanks again, problem solved.

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

116-What is lexicographically smallest path?

Post by hsihsiwu » Tue Apr 16, 2002 11:27 pm

"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
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Apr 17, 2002 5:30 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:

Post by Stefan Pochmann » Wed Apr 17, 2002 7:20 am

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

Post by hsihsiwu » Wed Apr 17, 2002 10:20 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

Post by mark00lui » Fri May 24, 2002 3:35 pm

The WA problem confused me at all!!! :evil:
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[0]+=smallest;
	array[1]=path;
}

int main(void)
{
	int maxcol=0, maxrow=0;
	
	while(2==scanf("%d %d", &maxcol, &maxrow))
	{
		long array[100][10][2];
		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][0]);
				array[ccol][crow][1]=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[2]={array[uppercol][crow+1][0], uppercol+1},
					 middle[2]={array[middlecol][crow+1][0], middlecol+1},
					 down[2]={array[downcol][crow+1][0], 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[0][0][0], path=1, ccol=1; ccol<maxcol; ccol++)
			if(array[ccol][0][0]<minsum)
			{
				minsum=array[ccol][0][0];
				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][1];
			printf(" %d", path);
		}

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

	}
	
	return 0;
}[/c]

Post Reply

Return to “Volume 1 (100-199)”