Page 1 of 16

Posted: Fri Mar 29, 2002 5:19 am
by 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.

Posted: Fri Mar 29, 2002 9:23 am
by 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.

Posted: Fri Mar 29, 2002 6:30 pm
by C8H10N4O2
I have a way to enumerate A solution. It just isn't the lexicographically smallest.

Posted: Fri Mar 29, 2002 9:55 pm
by 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.

Posted: Fri Mar 29, 2002 11:31 pm
by 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]);
	}
}

Posted: Sat Mar 30, 2002 7:46 am
by ftomi
You should start with the last column, not the first. Then, you can select the starting field easy.

Posted: Sat Mar 30, 2002 10:39 pm
by C8H10N4O2
What if there are multiple paths within each starting field?

Posted: Sun Mar 31, 2002 12:06 am
by 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.

Posted: Mon Apr 01, 2002 1:41 pm
by C8H10N4O2
Thanks. I will give it a try.

Posted: Wed Apr 03, 2002 1:39 pm
by C8H10N4O2
Thanks again, problem solved.

116-What is lexicographically smallest path?

Posted: Tue Apr 16, 2002 11:27 pm
by 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.

Posted: Wed Apr 17, 2002 5:30 am
by 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.

Posted: Wed Apr 17, 2002 7:20 am
by 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;
}

Posted: Wed Apr 17, 2002 10:20 am
by hsihsiwu
I got it.
Thanks you guys very much.

help in Problem 116

Posted: Fri May 24, 2002 3:35 pm
by mark00lui
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]