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

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Mon Jan 20, 2003 3:48 pm

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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

Help!

Post by ec3_limz » Thu Jan 23, 2003 2:09 pm

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
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Thu Jan 30, 2003 6:20 pm

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

do you take care of the lexicographic order?
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Post by szymcio2001 » Thu Mar 13, 2003 3:04 pm

Rodrigo wrote: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.

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

Post by szymcio2001 » Thu Mar 13, 2003 3:07 pm

Sorry, the output is of course:

Code: Select all

2 1 5 4
4

Rodrigo
New poster
Posts: 14
Joined: Sun Jul 07, 2002 12:03 am
Location: Brazil
Contact:

Post by Rodrigo » Sun Mar 16, 2003 7:26 am

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

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Sun Mar 16, 2003 6:27 pm

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
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

#116 - Unidirectional TSP (WA) -- ?!?!?!?!

Post by ec3_limz » Sat Apr 05, 2003 7:12 am

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]

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Sun Apr 06, 2003 2:08 pm

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
New poster
Posts: 2
Joined: Wed Apr 16, 2003 11:27 pm

TSP trouble

Post by benreisner » Thu Apr 17, 2003 12:52 am

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Apr 17, 2003 7:52 am

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Thu May 01, 2003 9:17 am

My program pass all the test data mention above, but I still got WA :cry:
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
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu May 01, 2003 4:26 pm

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.
Kalo mau kaya, buat apa sekolah?

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Sat May 31, 2003 10:05 am

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

Angga :)

ivec
New poster
Posts: 8
Joined: Tue May 27, 2003 2:41 pm
Contact:

pb 116 Unidirectional TSP -- what lexicographic order?

Post by ivec » Mon Jun 09, 2003 12:38 pm

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)

Post Reply

Return to “Volume 1 (100-199)”