Page 4 of 16

Posted: Mon Jan 20, 2003 3:48 pm
by 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

Help!

Posted: Thu Jan 23, 2003 2:09 pm
by 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]

Posted: Thu Jan 30, 2003 6:20 pm
by epsilon0
i got accepted on first try. this problem is easy!

do you take care of the lexicographic order?

Posted: Thu Mar 13, 2003 3:04 pm
by szymcio2001
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.

Posted: Thu Mar 13, 2003 3:07 pm
by szymcio2001
Sorry, the output is of course:

Code: Select all

2 1 5 4
4

Posted: Sun Mar 16, 2003 7:26 am
by 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

Posted: Sun Mar 16, 2003 6:27 pm
by 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

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

Posted: Sat Apr 05, 2003 7:12 am
by 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]

Posted: Sun Apr 06, 2003 2:08 pm
by 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

TSP trouble

Posted: Thu Apr 17, 2003 12:52 am
by 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?

Posted: Thu Apr 17, 2003 7:52 am
by 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

Posted: Thu May 01, 2003 9:17 am
by yatsen
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]

Posted: Thu May 01, 2003 4:26 pm
by 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.

Posted: Sat May 31, 2003 10:05 am
by angga888
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 :)

pb 116 Unidirectional TSP -- what lexicographic order?

Posted: Mon Jun 09, 2003 12:38 pm
by 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)