10332 - The Absent Minded Professor

[Moni]

Thanks Adil (On behalf cothevacothe),
As I don't know Java well, I didn't help him at that time !

[..]

I find that my accepted program can't solve the case of incorrect balance with N = 50.....It will got TLE

But my program just run 0.2s on judge, that means the judge input isn't a good input set at all........
Can anyone solved this problem tell me how you check for the case of incorrect balance? I used recursion to solve this problem, so in this case my program will make a deep deep search.........

(Hope I can copy the test case correctly.........)
50
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 17 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 18 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 21 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 23 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 24 25 25 25 25 25 25 25 25 25 25 25 25 25 25 25 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 26 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 27 28 28 28 28 28 28 28 28 28 28 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 30 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 31 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 32 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 33 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 34 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 35 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 36 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 37 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 38 39 39 39 39 39 39 39 39 39 39 39 39 39 39 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 41 41 41 41 41 41 41 41 41 41 41 41 41 41 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 42 43 43 43 43 43 43 43 43 43 43 44 44 44 44 44 44 44 44 44 44 44 44 44 45 45 45 45 45 45 45 45 45 45 45 45 45 45 45 46 46 46 46 46 46 46 46 46 46 46 46 46 47 47 47 47 47 47 47 47 47 47 47 47 47 47 48 48 48 48 48 48 48 48 48 48 48 48 49 49 49 49 49 49 49 49 49 49 49 49 50 50 50 50 50 50 50 50 50 50 51 51 51 51 51 51 51 51 51 51 51 51 51 51 52 52 52 52 52 52 52 52 52 52 52 52 53 53 53 53 53 53 53 53 53 53 53 53 53 54 54 54 54 54 54 54 54 54 55 55 55 55 55 55 55 55 55 55 55 55 56 56 56 56 56 56 56 56 56 56 56 56 57 57 57 57 57 57 57 57 57 58 58 58 58 58 58 58 58 58 58 58 59 59 59 59 59 59 59 59 59 59 60 60 60 60 60 60 60 60 60 61 61 61 61 61 61 61 61 62 62 62 62 62 62 62 62 62 62 63 63 63 63 63 63 63 63 64 64 64 64 64 64 64 64 65 65 65 65 65 65 65 66 66 66 66 66 66 67 67 67 67 67 67 67 67 68 68 68 68 68 68 68 69 69 69 69 69 70 70 70 70 70 70 70 70 70 71 71 71 71 71 71 71 71 71 71 72 72 72 72 72 73 73 73 73 73 73 73 73 74 74 74 74 74 74 74 74 74 75 75 75 75 75 76 76 76 76 76 76 77 77 77 77 78 78 78 78 78 78 79 79 80 80 80 80 81 81 81 82 82 82 82 82 83 83 83 83 84 84 85 85 86 86 86 86 86 87 87 87 88 89 89 89 89 90 90 90 91 91 91 92 92 93 93 93 93 94 94 95 95 96 97 98

[Andrey Mokhov]

My program says "Incorrect Balance." very quckly. I also use recursion but it might be cut off a lot of wrong subrtrees of search.

Andrey.

[..]

Thanks for your reply.
After reviewing my code, I find that I already tried to cut the search tree.
But the cutting step is in a stupid way and spend a lot of processing time.
After improving it, I can check the above incorrect inbalance case in a second.

[kalinov]

What about this:

Code: Select all

input:
6
1 2 2 3 4 5 6 7 7 8 9 10 11 13 14
 
output 1:
0 4 6 11 13 14

output 2:
0 3 5 7 13 14

Note that output 2 is NOT an image of output 1, and they are both correct outputs.

I hope there is no such examples in the test data.

[Adrian Kuegel]

I guess there are no such inputs; anyway, my program would output the first possibility.

[tobby]

Hi,

I don't really know how to prune. Can anyone give me some idea? I am getting many TLE. Thank you very much.

EDIT: I get accepted, but I am still not satisfied with my pruning. Any idea is welcome.

[lighted]

For input

Code: Select all

6
1 2 2 3 4 5 6 7 7 8 9 10 11 13 14

My acc prog gives

Code: Select all

0 4 6 11 13 14