OJ Board

The Online Judge board
https://onlinejudge.org/board/

116 - Unidirectional TSP

https://onlinejudge.org/board/viewtopic.php?t=1114

Page 8 of 16

Update but still WA

Posted: Thu Jul 29, 2004 12:15 am
by omega
I recoded the whole blasted thing in C and still wrong answer!! I changed the algorithm slightly, but at the core it still does the same thing.

[c]#include <stdio.h>

const int MAX_ROWS = 10;
const int MAX_COLS = 100;

int main(void)
{
int a = 0, b = 0, c = 0;
int m = 0, n = 0, matrix[MAX_ROWS][MAX_COLS], path[MAX_ROWS][MAX_COLS], temp[MAX_ROWS];
int wne = 0, we = 0, wse = 0, smallest = 0, sp = 0, mw = 0;

while (scanf("%d%d", &m, &n) == 2)
{
for (a = 0; a < m; a++)
for (b = 0; b < n; b++)

scanf("%d", &matrix[a]);
if (n != 1)
{
for(a = n-2; a >= 0; a--)
{
for(b = 0; b < m; b++)
{
if(b == 0) wne = matrix[m-1][a+1];
else wne = matrix[b-1][a+1];
we = matrix[a+1];
if(b == (m-1)) wse = matrix[0][a+1];
else wse = matrix[b+1][a+1];
if ((b == 0 && wne < we && wne < wse) || (b > 0 && wne <= we && wne <= wse))
{
matrix[a]+=wne;
path[a] = b - 1;
}
else if ((b == (m-1) && we < wse) || (b < (m-1) && we <= wse))
{
matrix[a]+=we;
path[a] = b;
}
else
{
matrix[a]+=wse;
path[a] = b + 1;
}
if (path[a] == -1) path[a] = m-1;
else if (path[b][a] == m) path[b][a] = 0;
}
}
}
for (a = 0, smallest = matrix[0][0], sp = 0; a < m; a++)
{
if (matrix[a][0] < smallest)
{
smallest = matrix[a][0];
sp = a;
}
}
mw = matrix[sp][0];
printf("%d ", sp+1);
if (n > 1)
{
for (a = 0; a < n - 1; a++)
{
printf("%d ", path[sp][a]+1);
sp = path[sp][a];
if (a == (n - 2)) printf("\n");
}
}
else printf("\n");
printf("%d\n", mw);
}
return 0;
}[/c]

The changes did make the alogrithm faster, which right now only means I get WA 2.5 seconds faster! Help or comment anyone.

Fixed

Posted: Thu Jul 29, 2004 2:28 pm
by omega
I feel like a fool, it was an error in one of the if statments.

Posted: Wed Aug 04, 2004 5:51 pm
by Experimenter
Could anyone help me with mine?i've tried all the input I could find and the answer seems to be correct, but still i keep getting this rubbish WA. why is that?
thanks in advance.
[cpp]
#include <iostream>
#include <fstream>
using namespace std;

#ifndef ONLINE_JUDGE
ifstream fin ("input.txt");
ofstream fout("output.txt");
#define in fin
#define out fout
#else
#define in cin
#define out cout
#endif
#define min(a,b) (((a) < (b)) ? (a) : (b))
int Matrix[10][100],Sum[10][100],Backtrack[10][100];
int n,m;

inline int scale(int i)
{
if(i==-1) return m-1;
else
if(i==m) return 0;
else return i;
}

int main()
{
bool fl = true;
while(fl)
{
if(!(in>>m>>n)) fl = false;
else
{
int i,j,i1,i2,iC,ic;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++) in>>Matrix[j];
Sum[n-1] = Matrix[n-1];
}
for(j=n-2; j >= 0; j--)
for(i=0;i<m;i++)
{
i1 = scale(i-1),i2 = scale(i+1);
if(Sum[j+1] < Sum[i1][j+1]) ic = i;
else if(Sum[j+1] == Sum[i1][j+1]) ic = min(i,i1);
else ic = i1;

if(Sum[ic][j+1] < Sum[i2][j+1]);
else if(Sum[ic][j+1] == Sum[i2][j+1]) ic = min(ic,i2);
else ic = i2;

Backtrack[j] = ic;
Sum[j] = Sum[ic][j+1] + Matrix[j];
}
for(ic=i=0;i<m-1;i++)
if(Sum[ic][0] > Sum[0]) ic = i;
out<<(ic+1);
for(j=1,iC=ic;j<n;j++)
ic = Backtrack[ic][j-1], out<<' '<<(ic+1);
out<<endl<<Sum[iC][0]<<endl;
}
}
return (0);
}[/cpp]

unbelievable!

Posted: Wed Aug 04, 2004 6:25 pm
by Experimenter
I cann't believe it! did you see where my mistake was? instead of m-1 in the next to last for loop there should be m.
I really cannot believe it. this is the modified code.:-|
[cpp]
#include <iostream>
#include <fstream>
using namespace std;

#ifndef ONLINE_JUDGE
ifstream fin ("input.txt");
ofstream fout("output.txt");
#define in fin
#define out fout
#else
#define in cin
#define out cout
#endif
#define min(a,b) (((a) < (b)) ? (a) : (b))
int Matrix[10][100],Sum[10][100],Backtrack[10][100];
int n,m;

inline int scale(int i)
{
if(i==-1) return m-1;
else
if(i==m) return 0;
else return i;
}

int main()
{
bool fl = true;
while(fl)
{
if(!(in>>m>>n)) fl = false;
else
{
int i,j,i1,i2,iC,ic;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++) in>>Matrix[j];
Sum[n-1] = Matrix[n-1];
}

for(j=n-2; j >= 0; j--)
for(i=0;i<m;i++)
{
i1 = scale(i-1),i2 = scale(i+1);
if(Sum[j+1] < Sum[i1][j+1]) ic = i;
else if(Sum[j+1] == Sum[i1][j+1]) ic = min(i,i1);
else ic = i1;

if(Sum[ic][j+1] < Sum[i2][j+1]);
else if(Sum[ic][j+1] == Sum[i2][j+1]) ic = min(ic,i2);
else ic = i2;

Backtrack[j] = ic;
Sum[j] = Sum[ic][j+1] + Matrix[j];
}
for(ic=i=0;i<m;i++)
if(Sum[ic][0] > Sum[0]) ic = i;
out<<(ic+1);
for(j=1,iC=ic;j<n;j++)
ic = Backtrack[ic][j-1], out<<' '<<(ic+1);
out<<endl<<Sum[iC][0]<<endl;
}
}
return (0);
}
[/cpp]

Posted: Sun Nov 21, 2004 12:07 pm
by backslash null
My output is:

1 2 3 4 5 6 7 8 9 10 11 12 1 2
14

and got AC,

good luck;

Posted: Mon Nov 22, 2004 5:55 am
by Blueteeth
F**K , I hate "Invalid Memory Reference" , till now every problem i submit i get runtime error
please please please say to me what to do
it's a fairly simple and clear code please tell me
[cpp]#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;

/* GOLBALS */
int** mat;
int rows,cols; // dimensions
struct path{
string p;
int w;
path():w(0) {}
};

path** dynamic; // to hold data necessary for dynamic programming
/* */

string to_str (int i)
{
stringstream s;
s << i;
return s.str();
}

bool smaller(string& sm , string& big)
{
istringstream iss(sm);
istringstream isb(big);
int sm_n,big_n;
while ( !iss.eof() && !isb.eof() )
{
iss >> sm_n;
isb >> big_n;
if ( sm_n > big_n )
return false;
}
return true;
}


inline void dealloc_mat()
{
for (int i=0 ; i<rows ; i++)
{
delete[] mat;
delete[] dynamic;
}
}

inline void alloc_mat ()
{
mat = new int*[rows];
dynamic = new path*[rows];

for (int i=0 ; i<rows ; i++)
{
mat = new int[cols];
dynamic = new path[cols];
}
}


inline void get_input(istream& in)
{
for (int i=0 ; i<rows ; i++)
{
for (int j=0 ; j<cols ; j++)
in >> mat[j];
}

/* initialize dynamic last column */
for (int k=0 ; k<rows ; k++)
{
dynamic[k][cols-1].p += to_str(k+1);
dynamic[k][cols-1].w += mat[k][cols-1];
}
}


path get_min_path(int beg_r , int beg_c)
{
if ( dynamic[beg_r][beg_c].w != 0 )
return dynamic[beg_r][beg_c];

path target,temp;
//int new_beg_r = beg_r;

target = get_min_path(beg_r,beg_c+1);

if ( beg_r+1 >= rows )
temp = get_min_path(beg_r+1-rows,beg_c+1);
else
temp = get_min_path(beg_r+1,beg_c+1);

if ( (temp.w < target.w) || (temp.w == target.w && smaller(temp.p,target.p)) )
target = temp;

if ( beg_r-1 < 0 )
temp = get_min_path(beg_r-1+rows,beg_c+1);
else
temp = get_min_path(beg_r-1,beg_c+1);

if ( (temp.w < target.w) || (temp.w == target.w && smaller(temp.p,target.p)) )
target = temp;

// append itself to the path found
target.p.insert(target.p.begin(),' ');
target.p = to_str(beg_r+1) + target.p;
target.w += mat[beg_r][beg_c];

dynamic[beg_r][beg_c] = target;
return target;
}

int main()
{
path min_p;
path temp;

while ( !cin.eof() )
{
cin >> rows >> cols;
alloc_mat();
get_input(cin);
min_p = get_min_path(0,0);
for (int i=1 ; i<rows ; i++)
{
temp = get_min_path(i,0);
if ( (temp.w < min_p.w) || (temp.w == min_p.w && smaller(temp.p,min_p.p)) )
min_p = temp;
}
cout << min_p.p << endl << min_p.w << endl;
dealloc_mat();
}
cin.get();
return 0;
}
[/cpp]

Re: Fixed

Posted: Tue Nov 30, 2004 2:34 am
by Billy
omega wrote:I feel like a fool, it was an error in one of the if statments.
in what "if statment" is the error ???

Posted: Sun Jan 23, 2005 3:16 pm
by wanderley2k
My code get correct output for all inputs too.

If anyone have tricks or can search any error in my code.

Code: Select all

#include <iostream>
#include <stdlib.h>
using namespace std;

#define MN 10
#define MM 100

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORI(i,j,n) for(int i=j;i<n;i++)
#define DEBUG(x)

int lin, col, dp[MN][MM], pai[MN][MM], seq[MN][MM];

int v(int i, int l) {
	if (i < 0) i += l;
	return i % l;
}

void caminho(int i, int c, int seq[MM]) {
	for (; c>=0; c--) {
		seq[c] = i;
		i = pai[i][c];
	}
}

int min3(int a, int b, int c) {
	int min = a;
	if (b < min) min = b;
	if (c < min) min = c;
	
	return min;
}

int main() {
	int sd[3][MM];

	while(cin >> lin >> col) {
		FOR(i,lin) FOR(j,col) {
			seq[i][j] = 2<<29;
			cin >> dp[i][j];
		}
		
		FORI(j,1,col) FOR(i,lin) {
			int iLI = i, iDS = (i+lin-1) % lin, iDI = (i+1) % lin;
			int vLI = dp[iLI][j-1];
			int vDS = dp[iDS][j-1];
			int vDI = dp[iDI][j-1];
			
			int min = min3(vLI, vDS, vDI);
			
			if (vLI == min && vDS != min && vDI != min) {
				dp[i][j] += vLI;
				pai[i][j] = iLI;
				
				continue;
			}
			if (vLI != min && vDS == min && vDI != min) {
				dp[i][j] += vDS;
				pai[i][j] = iDS;
				
				continue;
			}
			if (vLI != min && vDS != min && vDI == min) {
				dp[i][j] += vDI;
				pai[i][j] = iDI;
				
				continue;
			}
			FOR(k,col) sd[0][k] = sd[1][k] = sd[2][k] = (2<<29);
			if (vLI == min) caminho(iLI, j-1, sd[0]);
			if (vDS == min) caminho(iDS, j-1, sd[1]);
			if (vDI == min) caminho(iDI, j-1, sd[2]);

			int imin = -1;
			FOR(k,3) {
				if (k == 0 && vLI != min) continue;
				if (k == 1 && vDS != min) continue;
				if (k == 2 && vDI != min) continue;
				
				if (imin == -1) {
					imin = k; continue;
				}
				
				FOR(kk, j) if (sd[k][kk] < sd[imin][kk]) {
					imin = k; break;
				}
			}
			if (imin == 0) {
				dp[i][j] += vLI;
				pai[i][j] = iLI;
			}
			if (imin == 1) {
				dp[i][j] += vDS;
				pai[i][j] = iDS;
			}
			if (imin == 2) {
				dp[i][j] += vDI;
				pai[i][j] = iDI;
			}
		}
		
		DEBUG(
			cout << "Pai\n";
			FOR(i,lin) {
				cout << endl;
				FOR(j,col) printf("%2d ", pai[i][j]);
			}
			cout << "\n\nDP";
			FOR(i,lin) {
				cout << endl;
				FOR(j,col) printf("%2d ", dp[i][j]);
			}		
			cout << endl << endl;
		);	
		
		int min = 0;
		FOR(i,lin) if (dp[i][col-1] < dp[min][col-1])
			min = i;
		FOR(i,lin) if (dp[i][col-1] == dp[min][col-1]) {
			caminho(i, col-1, seq[i]);
			
			FOR(j,col) if (seq[i][j] < seq[min][j]) {
				min = i; break;
			}			
		}
				
		FOR(i,col) {
			if (i > 0) cout << " ";
			cout << (seq[min][i]+1);
		}
		cout << endl << dp[min][col-1] << endl;
	}
	return 0;
}
Thanks!


Wanderley

Posted: Thu Jan 27, 2005 10:30 am
by Digit
Try this:

Code: Select all

Input:

4 4
3 3 3 3
3 3 3 3
3 3 3 1
1 1 1 1
4 4
3 3 3 1
3 3 3 3
3 3 3 1
1 1 1 1
4 4
3 3 
3 1 3 3 3 
3 3 3 3 1 1 
1 1 1
4 6
1 1 1 3 3 1
3 3 3 1 3 1
1 1 1 1 1 3
3 3 3 3 1 1

Output:

4 4 4 3
4
4 4 4 1
4
4 4 4 1
4
1 1 1 2 3 2
6

Posted: Thu Jan 27, 2005 11:11 am
by wanderley2k
Thanks Digit but I change the form to make the DP and got AC.


I make DP right to left and now I dont need to make search for lexico.

critical i/o for 116

Posted: Tue Feb 15, 2005 5:00 pm
by emotional blind
i need some critical input for 116
plz help me

Posted: Tue Feb 15, 2005 7:10 pm
by Larry
Taken from http://www.algorithmist.com/index.php/UVa_116 :

Input:

Code: Select all

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10 9 10
12 14 
1 2 2 1 1 1 1 1 1 1 1 1 1 2 
1 1 2 2 1 1 1 1 1 1 1 1 1 1 
1 1 1 2 2 1 1 1 1 1 1 1 1 1 
1 1 1 1 2 2 1 1 1 1 1 1 1 1 
1 1 1 1 1 2 2 1 1 1 1 1 1 1 
1 1 1 1 1 1 2 2 1 1 1 1 1 1 
1 1 1 1 1 1 1 2 2 1 1 1 1 1 
1 1 1 1 1 1 1 1 2 2 1 1 1 1 
1 1 1 1 1 1 1 1 1 2 2 1 1 1 
1 1 1 1 1 1 1 1 1 1 2 2 1 1 
1 1 1 1 1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 2 2
4 7
1 2 -3 4 -2 1 5
-1 3 5 -2 6 -3 4
2 1 3 -2 -1 3 1
3 -3 4 2 -3 4 3
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10
9 10
5 6
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5
3 4
1 2 3 4
1 2 3 4
1 2 3 4
5 5
1 5 10 6 3
5 1 8 4 11
10 12 5 2 9
7 3 20 5 8
4 1 5 12 6
5 10
11 53 34 73 18 53 99 52 31 54
4 72 24 6 46 17 63 82 89 25
67 22 10 97 99 64 33 45 81 76
24 71 46 62 18 11 54 40 17 51
99 8 57 76 7 51 90 92 51 21
5 10
11 53 1 73 18 53 99 52 31 54
4 72 54 6 46 17 63 82 89 25
67 22 80 97 99 64 33 45 81 76
24 71 46 62 18 11 54 40 17 51
99 8 57 76 7 51 90 92 51 21
5 6
-3 -4 -1 -2 -8 -6
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4
10 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output:

Code: Select all

1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19
2 2 3 4 5 6 7 8 9 10 11 12 1 2
14
1 4 1 2 1 2 3
-11
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19
1 1 1 1 1 1
6
1 1 1 1
10
1 2 3 2 1
14
2 3 3 2 1 2 3 4 4 5
188
1 5 1 2 1 2 3 4 4 5
172
4 3 2 3 3 4
-49
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100

Posted: Fri Feb 25, 2005 4:12 pm
by emotional blind
For the input

Code: Select all

For the input
12 14 
1 2 2 1 1 1 1 1 1 1 1 1 1 2 
1 1 2 2 1 1 1 1 1 1 1 1 1 1 
1 1 1 2 2 1 1 1 1 1 1 1 1 1 
1 1 1 1 2 2 1 1 1 1 1 1 1 1 
1 1 1 1 1 2 2 1 1 1 1 1 1 1 
1 1 1 1 1 1 2 2 1 1 1 1 1 1 
1 1 1 1 1 1 1 2 2 1 1 1 1 1 
1 1 1 1 1 1 1 1 2 2 1 1 1 1 
1 1 1 1 1 1 1 1 1 2 2 1 1 1 
1 1 1 1 1 1 1 1 1 1 2 2 1 1 
1 1 1 1 1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 1 1 1 1 1 1 2 2
output should be

Code: Select all

1 2 3 4 5 6 7 8 9 10 11 12 1 2
14
But your output is

Code: Select all

2 2 3 4 5 6 7 8 9 10 11 12 1 2 
14

Now, problem description of 116 says
For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive. No path's weight will exceed integer values representable using 30 bits.
For each specification the number of rows will be between 1 and 10 inclusive; the number of columns will be between 1 and 100 inclusive. No path's weight will exceed integer values representable using 30 bits.
but in this particular set you give the number of rows
above 10 which is 12 (mistake?)

thanks anyway

Posted: Sat Feb 26, 2005 3:11 pm
by emotional blind
i think its a mistake isnt it?
so the page should be updated..

Posted: Wed Mar 02, 2005 12:29 am
by wk
funny, your answer seems incorrect as much as
the original answer.
if the lexicographicaly smaller path is to be printed, then note
that 12 is smaller than 2, so the path should go
1 12 11 10 10....
All times are UTC+02:00
Page 8 of 16

Powered by phpBB® Forum Software © phpBB Limited