116 - Unidirectional TSP

[hank]

I give you some test data,and hope it will be helpful.

input data

Code: Select all

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

output data

Code: Select all

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

[ec3_limz]

My code works for all the sample test cases provided by hank, but I still get WA. Please help!

[cpp]#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct T_path { int col[100]; };
int rows, cols;

inline int intcmp(const void *a, const void *b) {
return *(int*)a - *(int*)b;
}

int pathcmp(const void *va, const void *vb) {
T_path *a = (T_path*)va;
T_path *b = (T_path*)vb;
int i;

for (i = 0; i < cols; i++)
if (a->col != b->col)
return a->col - b->col;

return 0;
}

int main() {
T_path path[10];
int map[10][100], extends[3];
int best[10][100], src[10][100], min, npath;
int i, j, k;

while (scanf("%d%d", &rows, &cols) == 2) {
for (i = 0; i < rows; i++)
for (j = 0; j < cols; j++)
scanf("%d", &map[j]);

for (i = 0; i < rows; i++)
best[0] = map[0];

for (i = 1; i < cols; i++)
for (j = 0; j < rows; j++) {
for (k = 0; k < 3; k++)
extends[k] = (j + rows + k - 1) % rows;
qsort(extends, 3, sizeof(int), intcmp);

best[j] = INT_MAX;
for (k = 0; k < 3; k++)
if (best[extends[k]] + map[j] < best[j][i]) {
best[j][i] = best[extends[k]][i - 1] + map[j][i];
src[j][i] = extends[k];
}
}

min = INT_MAX;
for (i = 0; i < rows; i++)
if (best[i][cols - 1] < min)
min = best[i][cols - 1];

npath = 0;
for (i = 0; i < rows; i++)
if (best[i][cols - 1] == min) {
for (j = i, k = cols - 1; k >= 0; j = src[j][k], k--)
path[npath].col[k] = j + 1;
npath++;
}

qsort(path, npath, sizeof(T_path), pathcmp);

for (i = 0; i < cols; i++) {
if (i > 0)
printf(" ");
printf("%d", path[0].col[i]);
}
printf("\n%d\n", min);
}

return 0;
}[/cpp]

[epsilon0]

i got accepted on first try. this problem is easy!

do you take care of the lexicographic order?

[szymcio2001]

Same with me. I've covered all these points too, but I still get WA :/.

And so do I. But finally I found an input that my program didn't solve:

Code: Select all

input:
5 4
9 1 9 9
1 9 9 9
9 9 9 9
1 1 1 1
9 9 1 9

output:
2 1 4 5
4

Maybe it will help someone.

[szymcio2001]

Sorry, the output is of course:

Code: Select all

2 1 5 4
4

[Rodrigo]

Hi

Thanks for your reply, but mine solves that one too.

I gave up on this problem a long time ago, I'm definitely waiting for a re-judgement.

Rodrigo

[saiqbal]

u can try the following 2 inputs and outputs:

Code: Select all

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

in last case, all the 1' s should be in one line

good luck
-sohel

[ec3_limz]

Got me a WA. Same story. Please help me or donate some sample test data.

[cpp]#include <limits.h>
#include <stdio.h>
#include <string.h>

int nrow, ncol, map[10][100];
int dptab[10][100], pre[10][100], path[100], best[100], min;

bool input() {
int i, j;

if (scanf("%d%d", &nrow, &ncol) != 2)
return false;

for (i = 0; i < nrow; i++)
for (j = 0; j < ncol; j++)
scanf("%d", &map[j]);

return true;
}

void trace(int i, int j) {
if (j > 0)
trace(pre[j], j - 1);
path[j] = i + 1;
}

void cmp() {
int i;

for (i = 0; i < ncol; i++)
if (path != best) {
if (path < best)
memcpy(best, path, sizeof(best));
break;
}
}

int *sort(int a[3]) {
int *rv = new int[3];

if (a[0] < a[1]) {
if (a[1] < a[2])
rv[0] = a[0], rv[1] = a[1], rv[2] = a[2];
else if (a[0] < a[2])
rv[0] = a[0], rv[1] = a[2], rv[2] = a[1];
else
rv[0] = a[2], rv[1] = a[0], rv[2] = a[1];
}
else {
if (a[0] < a[2])
rv[0] = a[1], rv[1] = a[0], rv[2] = a[2];
else if (a[1] < a[2])
rv[0] = a[1], rv[1] = a[2], rv[2] = a[0];
else
rv[0] = a[2], rv[1] = a[1], rv[2] = a[0];
}

return rv;
}

void dp() {
int from[3], i, j, k;

for (i = 0; i < nrow; i++)
dptab[0] = map[0];

for (i = 1; i < ncol; i++)
for (j = 0; j < nrow; j++) {
for (k = 0; k < 3; k++)
from[k] = (j + nrow + (k - 1)) % nrow;
memcpy(from, sort(from), sizeof(int) * 3);

dptab[j] = INT_MAX;
for (k = 0; k < 3; k++)
if (dptab[from[k]] + map[j][i] < dptab[j][i]) {
dptab[j][i] = dptab[from[k]][i - 1] + map[j][i];
pre[j][i] = from[k];
}
}

min = INT_MAX;
for (i = 0; i < nrow; i++)
if (dptab[i][ncol - 1] < min)
min = dptab[i][ncol - 1];

best[0] = INT_MAX;
for (i = 0; i < nrow; i++)
if (dptab[i][ncol - 1] == min) {
trace(i, ncol - 1);
cmp();
}
}

void output() {
int i;

for (i = 0; i < ncol; i++) {
if (i > 0)
printf(" ");
printf("%d", best[i]);
}
printf("\n%d\n", min);
}

int main() {
#ifndef ONLINE_JUDGE
freopen("input.dat", "r", stdin);
freopen("output.dat", "w", stdout);
#endif

while (input()) {
dp();
output();
}

return 0;
}[/cpp]

[saiqbal]

you'll find some test i/o in previous posts. here are some links:
http://acm.uva.es/board/viewtopic.php?t=1114&start=15
and
http://acm.uva.es/board/viewtopic.php?t=1114

good luck
-sohel

[benreisner]

Hi, sorry for the length, but im confused:

So i have been trying to get Unidirectional TSP working using java.
my DP algorithim first marks the distance to every cell in the matrix using a column first order. as i discover a cell I decide which of the three possible approaches to that cell would be best. marking the total distance and the parent(s). After the whole matrix has been discovered, I find the best possible end points.

I now travel backwards for each column. I find the best distances that are reachable (i can get to a possibility the next column) in each column, and i mark them as possibilities and keep going to the previous columns.

Now i have marked all cells which lie upon a best possible best path.

Lexicagraphically means dictionary order right? so i want the first column to have the lowest possible number, and so forth, giving preference to earlier column. So that an ordering or possibile paths is
1543
3333
4321
assuming they are all valid paths with an equal distance that is the minimal for the matrix.

we should return 1543 right?
i start with nothing commited. so i travel along the valid cells matrix, starting at the first column, for each column.

I take the lowest numbered cell that is reachable(I can get to it from the previously commited cell), and i commit that cell to my list.

so i have matrices like

input:

9 1 9 9
1 9 9 9
9 9 9 9
1 1 1 1
9 9 1 9

Distance
9 2 11 12
1 10 11 20
9 10 11 12
1 2 3 4
9 10 3 12

in path 0=not in path, 1 = in path
0 1 0 0
1 0 0 0
0 0 0 0
1 1 1 1
0 0 1 1


And my program reports a path
2 1 5 4
with weight=4


I initially failed the test inputs in this thread. My code did not produce the first lexi ordered one. I then rewrote my discovery process (to what i described above). I now solve all of the input in the thread almost instantly.

My code still gave WA, so i tried rewriting my input method, to not be concerned with reading lines.

It then gave me a TLE, and after tuning my new input method, I got a WA after 9.5 seconds. Anybody have any ideas, any new input, any suspected problems in my algorithim, any help?

[Dominik Michniewski]

Be carefully when you must go from first row to last and from last to first ... espesially if weight of paths are the same

Maybe this help you

DM

[yatsen]

My program pass all the test data mention above, but I still got WA
Can anyone tell me what's wrong, or give me more test data?
[c]#include <stdio.h>

typedef struct node
{
int row,weight;
} node;
int m,n,a[10][100],t[10][100],p[10][100],path[101],path2[101];

int sort_function( const void *a, const void *b)
{
node *p,*q;
p=(node *)a; q=(node *)b;
if(p->weight < q->weight) return -1;
else if(p->weight > q->weight) return 1;
else return p->row - q->row ;
}

int picksmall(int *temp)
{
int i,si=0,small=temp[0];
for(i=1; i<3; i++)
if(temp<small)
{ small=temp; si=i; }
return si;
}
int path2small()
{
int i,j,k;
for(j=1; j<n; j++)
{
if(path[j]<path2[j]) return 0;
if(path[j]>path2[j])
{
for(k=1; k<n; k++) path[k]=path2[k];
return 1;
}
}
return 0;
}
void main()
{
int i,j,k,temp[3],min,imin;
node s[3];
/*freopen("in116","r",stdin);*/
while(scanf("%d %d",&m,&n)==2)
{
for(i=0; i<m; i++)
for(j=0; j<n; j++) scanf("%d",&a[j]);
if(m==1)
{
for(j=k=0; j<n; j++) k += a[0][j];
printf("1");
for(j=1; j<n; j++) printf(" 1");
printf("\n%d\n",k);
continue;
}
for(i=0; i<m; i++) { t[0]=a[0]; p[0]=i; }
for(j=1; j<n; j++)
{
for(i=0; i<m; i++)
{
s[0].row=(i-1)%m; if(s[0].row<0) s[0].row += m;
s[1].row=i;
s[2].row=(i+1)%m;
s[0].weight=p[s[0].row][j-1];
s[1].weight=p[s[1].row][j-1];
s[2].weight=p[s[2].row][j-1];
qsort(s,3,sizeof(s[0]),sort_function);
temp[0]=t[s[0].row][j-1]+a[j];
temp[1]=t[s[1].row][j-1]+a[j];
temp[2]=t[s[2].row][j-1]+a[j];

k=picksmall(temp);
t[j]=temp[k];
p[i][j]=s[k].row;
}
}
for(imin=0,min=t[0][n-1],i=1; i<m; i++)
if(t[i][n-1]<min) { min=t[i][n-1]; imin=i;}
for(i=imin,j=n-1; j>=1; j--)
{
path[j]=p[i][j];
i=path[j];
}
for(i=0; i<m; i++)
{
if(t[i][n-1]==min)
{
for(k=i,j=n-1; j>=1; j--)
{
path2[j]=p[k][j];
k=path2[j];
}
if(path2small()) imin=i;

}
}

for(j=1; j<n; j++) printf("%d ",path[j]+1);
printf("%d\n",imin+1);
printf("%d\n",min);
}
}[/c]

[titid_gede]

i didnt check your code, since i'm in internet cafe now, but have you try matrix with dimension 1 X N, 2 X N, N X 1, N X 2? i think that's the special case in this problem. and my ac prog didnt use sorthing, only DP.

[angga888]

I also got WA with my code in PASCAL, but after I translated it to C language, I got AC.
I don't know why, cause I use the same algorithm, but the OJ gives different result.

Angga

[ivec]

I'm hitting WA on 116, and have doubts on what the lexicographic order is supposed to be.
Could someone with AC let me know what is the correct output for the following input ?
[quote]
10 9
2 1 2 1 1 1 1 1 2
1 2 1 2 1 2 1 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
1 2 1 2 1 2 1 2 2
[/quote]
Which is the lexicographically smallest sequence: ?
2 1 2 1 1 1 1 1 1
10 1 10 1 10 1 10 1 10
10 1 10 1 1 1 1 1 1

(my code otherwise solves all samples provided here in previous posts)