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

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

sorry, was far-fetched stuff...

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

I got AC, and it appears that the correct sequence is:
2 1 2 1 1 1 1 1 1

Sorry, the WA got me wandering, while I just failed to handle 1-row matrices correctly.

But having the alphabetically smallest sequence was a nice exercice
:wink:

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

[Resolved]: faster "lexicographical" order for 116

Post by bugzpodder » Sat Jul 05, 2003 2:04 am

I got a solution for 116 but it passes the OJ test after running for 5 seconds. I used a DP solution O(3*m*n) so i dont think that is lagging me. But however since the problem requires lexicographical order, i keep an array of prev[10][100] that contains all the previous orders, in C++ string format (fortunately all the rows are in single digits 0-9). i suspect my algorithm is lagging because of numerous string comparisions and adding in the end. and obviously, it breaks down when the rows gets to 11 (which doesnt happen in the problem).

so my question is, how do you do the lexicographical order of the path in another way? i attempted to just keeping the smallest previous row but that doesnt guarentee the lex order required.
Last edited by bugzpodder on Mon Aug 23, 2004 8:24 pm, edited 1 time in total.

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf » Wed Jul 16, 2003 11:40 am

U don't have to keep all the previous order.
U can solve this problem by using DP only.
Try to search the part from the end to beginning (reverse).

Then u just have to search the path for minimum path from the begining, by choosing the min row.

Hope it help.

Sorry for my bad english

amstex
New poster
Posts: 5
Joined: Tue Jul 29, 2003 9:49 am

116 WA help

Post by amstex » Tue Jul 29, 2003 10:37 am

I have read through 13 pages about pb 116 and tried many test cases but I still can not figure out what's wrong with my code. Would anyone give me some test cases so that I can find what's wrong. Here is my source code. Thank you very much.

Code: Select all

#include <stdio.h>

int arr[11][101], cost[11][101], path[11][101], visit[11][101], store[101][2];

void printResult(int, int);
int find(int, int, int);

main() {
        int m, n, x, y, val, prePos, preVal, midVal, downPos, downVal, min, corX, min1;
        scanf("%d %d",&m,&n);

        while (!feof(stdin)&&m!=0&&n!=0) {
                for (x = 0; x<m; x++) {
                        for (y = 0; y<n; y++) {
                                scanf("%d",&arr[x][y]);
                                visit[x][y] = 0;
                        }
                        cost[x][0] = arr[x][0];
                        visit[x][0] = 1;
                }
                for (x = 0; x<n; x++) {
                        for (y = 0; y<m; y++) {
                                val = cost[y][x];
                                prePos = (y-1+m)%m;
                                preVal = arr[prePos][x+1];
                                midVal = arr[y][x+1];
                                downPos = (y+1)%m;
                                downVal = arr[downPos][x+1];
                                if (visit[prePos][x+1]==0) {
                                        cost[prePos][x+1] = val+preVal;
                                        visit[prePos][x+1] = 1;
                                        path[prePos][x+1] = y;
                                }
                                else {
                                        if (cost[prePos][x+1]==val+preVal) {
                                                min = find(path[prePos][x+1],y,x);
                                                path[prePos][x+1] = min;
                                        }
                                        if (cost[prePos][x+1]>val+preVal) {
                                                cost[prePos][x+1] = val+preVal;
                                                path[prePos][x+1] = y;
                                        }
                                }


                                if (visit[downPos][x+1]==0) {
                                        cost[downPos][x+1] = val+downVal;
                                        visit[downPos][x+1] = 1;
                                        path[downPos][x+1] = y;
                                }
                                else {
                                        if (cost[downPos][x+1]==val+downVal) {
                                                min = find(path[downPos][x+1],y,x);
                                                path[downPos][x+1] = min;
                                        }
                                        if (cost[downPos][x+1]>val+downVal) {
                                                cost[downPos][x+1] = val+downVal;
                                                path[downPos][x+1] = y;
                                        }
                                }


                                if (visit[y][x+1]==0) {
                                        cost[y][x+1] = val+midVal;
                                        visit[y][x+1] = 1;
                                        path[y][x+1] = y;
                                }
                                else {
                                        if (cost[y][x+1]==val+midVal) {
                                                min = find(path[y][x+1],y,x);
                                                path[y][x+1] = min;
                                        }
                                        if (cost[y][x+1]>val+midVal) {
                                                cost[y][x+1] = val+midVal;
                                                path[y][x+1] = y;
                                        }
                                }
                        }
                }
                min = cost[0][n-1];
                for (x = 0; x<m; x++) {
                        if (cost[x][n-1]<min) {
                                min = cost[x][n-1];
                                corX = x;
                        }
                }
                for (x = 0; x<m; x++) {
                        if (cost[x][n-1]==min&&x!=corX) {
                                min1 = find(x,corX,n-1);
                                corX = min1;
                        }
                }
                printResult(corX, n-1);
                printf("\n%d\n",min);
                scanf("%d %d",&m,&n);
        }
}

void printResult(int corX, int corY) {
        if (corY!=0) printResult(path[corX][corY],corY-1);
        printf("%d ",corX+1);
}

int find(int row1, int row2, int column) {
        int temp1, temp2, x;
        x = 0; temp1 = row1; temp2 = row2;
        store[x][0] = row1;
        store[x][1] = row2;
        ++x;
        while (column>0) {
                row1 = path[row1][column];
                row2 = path[row2][column];
                store[x][0] = row1;
                store[x][1] = row2;
                --column; ++x;
        }
        --x;
        while (x>=0&&store[x][0]==store[x][1]) --x;
        if (store[x][0]>store[x][1]) return temp2;
        else return temp1;
}

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Thu Jul 31, 2003 9:20 pm

amstex,

did you consider arranging the path Lexicographically?

this will help you.

take care.
__nOi.m....

amstex
New poster
Posts: 5
Joined: Tue Jul 29, 2003 9:49 am

Post by amstex » Fri Aug 01, 2003 8:28 am

I believe I have considered this because when there are more than one way to go to a point(have the same weight), I always choose the one with minimum Lexicographical order by tracking back. May be this procedure is wrong but I still can not find where.
Thank you for your reply.

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master » Fri Aug 08, 2003 6:59 am

I have used DP
I found a great help on this board about this problem.

aid
New poster
Posts: 1
Joined: Mon Aug 11, 2003 7:16 pm

Try this

Post by aid » Mon Aug 11, 2003 7:22 pm

input:

10 16
0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0
0 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1
1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1
1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1
0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0
1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1
1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1
1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1
1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1

output:
2 3 3 3 3 2 1 10 9 8 8 8 8 7 6 5
0

amstex
New poster
Posts: 5
Joined: Tue Jul 29, 2003 9:49 am

Post by amstex » Thu Aug 14, 2003 6:53 am

Hi, my code give the same output as yours.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Tue Aug 19, 2003 8:26 pm

IN:

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

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
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
Hope this helps!

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Tue Aug 19, 2003 8:35 pm

I posted this somewhere else but in case you missed it:

Code: Select all

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

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

116 Undirected TSP WEIRD PROBLEM

Post by xbeanx » Wed Aug 20, 2003 11:15 pm

I'm hoping one of you guys can make a suggestion about my program.

I wrote this program, and for all input I can find it creates correct output. However I always get WA.

So I tried a little trick using a try block. What I did was catch an exception and go into a spinlock. By doing this, I pinpointed exactly where the exception was occuring.

My code is below, and the offending exception (NumberFormatException) is marked with comments...

[java]// @JUDGE_ID: ******** 116 Java

import java.io.IOException;
import java.util.StringTokenizer;

class Main {
static int m, n;
static int[][] matrix;

public static void main(String[] args) throws IOException {
Tokenizer tok = new Tokenizer();
try {
while(true) {
m = Integer.parseInt(tok.nextToken());
n = Integer.parseInt(tok.nextToken());
matrix = new int[m][n];

////////////////////////
// OFFENDING EXCEPTION
////////////////////////
try {

for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
matrix[j] = Integer.parseInt(tok.nextToken());

} catch(NumberFormatException e) {while(true);}

findPath();
}
} catch(NoMoreTokensException e) {}
}

static void findPath() {
int[][] costs = new int[m][n];
for(int i = 0; i < m; i++) costs[n-1] = matrix[n-1];
for(int j = n-2; j >= 0; j--)
for(int i = 0; i < m; i++) {
int min = costs[(i-1+m)%m][j+1];
if(costs[j+1] < min) min = costs[j+1];
if(costs[(i+1)%m][j+1] < min) min = costs[(i+1)%m][j+1];
costs[j] = matrix[j] + min;
}

int minCost = costs[0][0], minPos = 0;
for(int i = 1; i < m; i++)
if(costs[0] < minCost) {
minCost = costs[0];
minPos = i;
}

System.out.print((minPos+1));
for(int j = 1; j < n; j++) {
int min = costs[(minPos-1+m)%m][j];
int tmp = (minPos-1+m)%m;
if(costs[minPos][j] < min) {
min = costs[minPos][j];
tmp = minPos;
} else if(costs[minPos][j] == min && minPos < tmp) {
min = costs[minPos][j];
tmp = minPos;
}
if(costs[(minPos+1)%m][j] < min) {
min = costs[(minPos+1)%m][j];
tmp = (minPos+1)%m;
} else if(costs[(minPos+1)%m][j] == min && minPos < tmp) {
min = costs[(minPos+1)%m][j];
tmp = (minPos+1)%m;
}
minPos = tmp;

System.out.print(" " + (tmp+1));
}

System.out.println();
System.out.println(minCost);
}

}

class Tokenizer {
private StringTokenizer st;

public Tokenizer() {st = new StringTokenizer("");}

public String nextToken() throws NoMoreTokensException {
while(!st.hasMoreTokens()) {
String input;

try {input = readLine(128);}
catch(IOException e) {input = null;}

if(input == null) throw new NoMoreTokensException();
st = new StringTokenizer(input);
}
return st.nextToken();
}

static String readLine(int maxLg) throws IOException {
byte[] lin = new byte[maxLg];
int lg = 0, car = -1;
while(lg < maxLg) {
car = System.in.read();
if(car<0 || car=='\n') break;
lin[lg++] += car;
}
if(car<0 && lg==0) return null;
return new String(lin, 0, lg).trim();
}
}

class NoMoreTokensException extends Throwable {}[/java]

Now, my problem is I don't know how to get around this. Is there a problem with my logic, or perhaps my readLine() method????

Like I said, I have tried it with all sorts of input, and it seems to work just fine. I do not have any idea why a NumberFormatException is getting thrown.

All the input are int's, I am using StringTokenizer which should correctly remove any whitespace or newline/carriage return.

Please if anyone has a suggestion I'd love to hear it!!!! :) :)

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Thu Aug 21, 2003 1:25 pm

I honed my exception handler and found that my problem occurs on input set #15. For whatever reason, when I get to that input my program dies. :(

:-?

::EDIT::
Okay, so I honed my progam a little more and found out that my program dies when one of the inputs is simply "-".

So, obviously one of the integers gets broken at the '-'. I'm going to try to increase the input buffer, that may be my problem.

::EDIT 2::
Hmm.. That did not fix my problem. I also tried taking the "-" and appending another token to the end, but that doesn't work.....

Can anyone tell me why my program isn't working?
Last edited by xbeanx on Thu Aug 21, 2003 2:57 pm, edited 1 time in total.

Julien Cornebise
Experienced poster
Posts: 145
Joined: Sat Feb 23, 2002 2:00 am
Location: Paris, France
Contact:

Post by Julien Cornebise » Thu Aug 21, 2003 2:49 pm

Hi xbeanx
I alas can't help you on this one, only tell you that I face the same problem in C : my program outputs the right answer for all the input I figured out (and this include the one you make avalaible on your website :wink: ), but when I send it to the judge -> WA :( :-?
I don't know on wich test I do fail, but I fail...

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Thu Aug 21, 2003 3:03 pm

Julien Cornebise wrote:Hi xbeanx
I alas can't help you on this one, only tell you that I face the same problem in C : my program outputs the right answer for all the input I figured out (and this include the one you make avalaible on your website :wink: ), but when I send it to the judge -> WA :( :-?
I don't know on wich test I do fail, but I fail...
Hey, it's good to see someone is reading this thread other than me. :)

Why don't you try putting a check in your program. If the input token (which should be an integer) is equal to the string "-" enter an infinite loop.

I just did this:
[java]String in = tok.nextToken();
while(in.equals("-"));[/java]

When I submit my program with this little clause it gives me a TLE. So I know that the reason it is giving me WA is because one of the input integers is broken.

I have even narrowed it down and I know that it is happening in the 15th data set. I'm wondering if an admin can check the test input to see if there's an error. I believe this works in C++ because when you do

int n;
cin >> n;

if the input is just "-" it sets n to 0. Does anyone know if this is correct?

Post Reply

Return to “Volume 1 (100-199)”