116 - Unidirectional TSP

[C8H10N4O2]

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]

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]

I have a way to enumerate A solution. It just isn't the lexicographically smallest.

[ftomi]

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]

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]

You should start with the last column, not the first. Then, you can select the starting field easy.

[C8H10N4O2]

What if there are multiple paths within each starting field?

[ftomi]

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]

Thanks. I will give it a try.

[C8H10N4O2]

Thanks again, problem solved.

[hsihsiwu]

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

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]

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]

I got it.
Thanks you guys very much.

[mark00lui]

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