116 - Unidirectional TSP

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

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

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

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

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

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]

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

in what "if statment" is the error ???

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

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]

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.

[emotional blind]

i need some critical input for 116
plz help me

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

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]

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

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