116 - Unidirectional TSP

ivec · 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

bugzpodder · 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.

b3yours3lf · 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 · 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 · Post by **Noim** » Thu Jul 31, 2003 9:20 pm

amstex,

did you consider arranging the path Lexicographically?

this will help you.

take care.

amstex · 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 · 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 · 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 · Post by **amstex** » Thu Aug 14, 2003 6:53 am

Hi, my code give the same output as yours.

xbeanx · 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 · 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 · 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 · 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?

Julien Cornebise · 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

), but when I send it to the judge -> WA

I don't know on wich test I do fail, but I fail...

xbeanx · 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 ), 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?

OJ Board

116 - Unidirectional TSP

sorry, was far-fetched stuff...

[Resolved]: faster "lexicographical" order for 116

116 WA help

Try this

116 Undirected TSP WEIRD PROBLEM