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

omega
New poster
Posts: 5
Joined: Tue Jul 27, 2004 5:37 pm

Update but still WA

Post 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.

omega
New poster
Posts: 5
Joined: Tue Jul 27, 2004 5:37 pm

Fixed

Post by omega »

I feel like a fool, it was an error in one of the if statments.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post 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]
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

unbelievable!

Post 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]
it would be great if you replied this post. really.

backslash null
New poster
Posts: 8
Joined: Tue Nov 11, 2003 11:02 pm

Post 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;

Blueteeth
New poster
Posts: 4
Joined: Tue Nov 09, 2004 10:28 pm

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

Billy
New poster
Posts: 3
Joined: Wed Nov 03, 2004 11:40 am

Re: Fixed

Post 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 ???

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

Post 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

Digit
New poster
Posts: 5
Joined: Sat Jan 15, 2005 7:06 pm

Post 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

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

Post 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.
Last edited by wanderley2k on Wed Jan 03, 2007 5:17 pm, edited 1 time in total.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

critical i/o for 116

Post by emotional blind »

i need some critical input for 116
plz help me

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post 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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post 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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

i think its a mistake isnt it?
so the page should be updated..

wk
New poster
Posts: 7
Joined: Tue Jul 20, 2004 4:49 am

Post 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....

Post Reply

Return to “Volume 1 (100-199)”