116 - Unidirectional TSP

[ivec]

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]

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]

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]

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]

amstex,

did you consider arranging the path Lexicographically?

this will help you.

take care.

[amstex]

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]

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

[aid]

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]

Hi, my code give the same output as yours.

[xbeanx]

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]

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]

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]

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]

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]

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?