## 116 - Unidirectional TSP

Moderator: Board moderators

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

### Update but still WA

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

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
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?
[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!

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
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
F**K , I hate "Invalid Memory Reference" , till now every problem i submit i get runtime error
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

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
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
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
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
Contact:

### critical i/o for 116

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:
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
Contact:
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``````

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