10159  Star
Moderator: Board moderators
10159  Star
Hey guys,
I'm wondering if there's an easier way to solve this problem. What I'm thinking of is create a grid with the triangles, where each cell contains 2 triangles. Then use recursion to get the solution. However, it would be long and inefficient.
Any other ideas?
Thanks.
I'm wondering if there's an easier way to solve this problem. What I'm thinking of is create a grid with the triangles, where each cell contains 2 triangles. Then use recursion to get the solution. However, it would be long and inefficient.
Any other ideas?
Thanks.
10159  Star > Need help.
Greetings!
I'm trying to solve this problem, but I'm getting nothing but WAs so far.
Please, evaluate this I/O:
Input
Output
Thanks in advance!
P.S.: if you know any critical I/O, will really appreciate it too.
I'm trying to solve this problem, but I'm getting nothing but WAs so far.
Please, evaluate this I/O:
Input
Code: Select all
5 7 8 9 6 1 9 0 9 8 4 6
5 7 8 9 6 1 9 0 9 8 4 6
0 0 0 0 0 0 0 0 0 0 0 0
9 9 9 9 9 9 9 9 9 9 9 9
9 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 9 9 9 9
9 0 0 0 0 0 0 9 0 0 0 0
9 0 0 0 0 0 9 0 0 0 0 0
6 4 8 9 0 9 1 6 9 8 7 5
6 4 8 9 0 9 1 6 9 8 7 5
Code: Select all
40 172
40 172
0 0
36 432
NO SOLUTION
NO SOLUTION
NO SOLUTION
9 18
9 9
40 172
40 172
P.S.: if you know any critical I/O, will really appreciate it too.
_.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Thanks Kuegel!
Greetings!
Thanks for the prompt answer!
Now I believe the problem is lying either in my reading of the input ("Every line in the input contains 12 digits, each two of them separated by a space."), or my algorithm is just wrong
I'll try to read, then check the algo again.
A couple of I/O would help
Thanks, and keep posting!
Edited: just made a charbychar reading of the input, and still WA. Must be my algorithm. Will really appreciate critical I/O, or at least a couple of tests.
Thanks for the prompt answer!
Now I believe the problem is lying either in my reading of the input ("Every line in the input contains 12 digits, each two of them separated by a space."), or my algorithm is just wrong
I'll try to read, then check the algo again.
A couple of I/O would help
Thanks, and keep posting!
Edited: just made a charbychar reading of the input, and still WA. Must be my algorithm. Will really appreciate critical I/O, or at least a couple of tests.
_.
10159?
I am trying to solve 10159. The suggestion in the programming challenges is to find a way to get the result individually, I accomplished this to get the maximum very fast, however the minimum is different....
I am this close to try an heuristics solution. But the suggestion in the book and the fact that there are many solutions that are really fasts according to the stats make me doubt that it was the best way to get the minimum.
(What's)/(Is there) an easier way to get the minimum?
I am this close to try an heuristics solution. But the suggestion in the book and the fact that there are many solutions that are really fasts according to the stats make me doubt that it was the best way to get the minimum.
(What's)/(Is there) an easier way to get the minimum?
I eventually made the heuristic solution.
WA in 7 seconds! So I guess that there must be a better way...
Edit: I have reduced the time to 0.082 seconds, still WA...
Edit II: I got AC, it is a pretty slow solution (more than 1 second) but it works, I still wonder whether there was a more direct solution.
correct i/o for the people still having problems that may find this thread using the search option:
WA in 7 seconds! So I guess that there must be a better way...
Edit: I have reduced the time to 0.082 seconds, still WA...
Edit II: I got AC, it is a pretty slow solution (more than 1 second) but it works, I still wonder whether there was a more direct solution.
correct i/o for the people still having problems that may find this thread using the search option:
Code: Select all
5 7 8 9 6 1 9 0 9 8 4 6
5 7 8 9 6 1 9 0 9 8 4 6
0 0 0 0 0 0 0 0 0 0 0 0
9 9 9 9 9 9 9 9 9 9 9 9
9 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 9 9 9 9
9 0 0 0 0 0 0 9 0 0 0 0
9 0 0 0 0 0 9 0 0 0 0 0
6 4 8 9 0 9 1 6 9 8 7 5
6 4 8 9 0 9 1 6 9 8 7 5
7 6 6 6 6 6 7 6 6 6 6 6
2 2 2 2 5 2 2 2 2 2 2 5
Code: Select all
40 172
40 172
0 0
36 432
NO SOLUTION
NO SOLUTION
NO SOLUTION
9 18
9 9
40 172
40 172
31 289
13 102
Re: 10159  Star
I cant get an AC, here are some input and my output:
Checking for the maximum value is easy, I just put the max value possible for each spot, and sum all spots values. If a line (A, B, C..) does not dettermine at least a spot value then NO SOLUTION. I believe this part I am doing ok. The problem is the min value, I did it using DP and got WA, I changed it to a complete search and still WA. I do this way: For each possible value (09) if there is 0 lines for that value I wont add anything, if there is 1 value I will add the value, if there is more than 1 I do the complete search (here is where I was doing the DP) to try to combine the most as possible the lines, then the val I will multiply by the value and add to min answer.. Am I doing it right or missing something?
Code: Select all
5 7 8 9 6 1 9 0 9 8 4 6
5 7 8 9 6 1 9 0 9 8 9 6
1 2 3 4 1 1 1 4 1 1 4 1
1 1 1 4 1 1 1 4 1 1 4 1
1 1 1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 1 2
1 7 6 2 9 7 1 0 2 3 4 9
0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9 9 9 9
1 9 2 7 3 9 1 2 3 9 1 9
5 7 8 9 6 1 9 0 9 8 4 6
5 7 8 9 6 1 9 0 9 8 4 6
0 0 0 0 0 0 0 0 0 0 0 0
9 9 9 9 9 9 9 9 9 9 9 9
9 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 9 9 9 9
9 0 0 0 0 0 0 9 0 0 0 0
9 0 0 0 0 0 9 0 0 0 0 0
6 4 8 9 0 9 1 6 9 8 7 5
6 4 8 9 0 9 1 6 9 8 7 5
7 6 6 6 6 6 7 6 6 6 6 6
2 2 2 2 5 2 2 2 2 2 2 5
Code: Select all
40 172
45 187
12 57
7 54
4 37
NO SOLUTION
NO SOLUTION
0 0
4 48
8 96
12 144
16 192
20 240
24 288
28 336
32 384
36 432
32 110
40 172
40 172
0 0
36 432
NO SOLUTION
NO SOLUTION
NO SOLUTION
9 18
9 9
40 172
40 172
31 289
13 102
Re: 10159  Star
Finally got accepted! The idea above is correct , I was making a little mistake on the complete search, I forgot to check in the arrangements to check if the third line is OK too, this test case was giving me wrong output:
The correct output is:
Thank you!
Code: Select all
9 7 3 8 8 5 0 1 4 9 7 1
Code: Select all
44 131
Re: 10159  Star
Bruno,
It is possible to find min value without searching. First, assume entire board is 0 except maximums given. The only way to reduce the min value is for the maximum values for two or three lines to be from the same triangle. For example, in the given data D, G, and I lines all have a max value of 9. If this value occurs in the triangle where those intersect, 9 only has to be counted once instead of 3 times.
Because this only happens when values are exactly equal, it doesn't matter exactly which triangle you use if there is more than one option (as long as the number of maximums eliminated is the same). Just pick one greedily and move on.
It is possible to find min value without searching. First, assume entire board is 0 except maximums given. The only way to reduce the min value is for the maximum values for two or three lines to be from the same triangle. For example, in the given data D, G, and I lines all have a max value of 9. If this value occurs in the triangle where those intersect, 9 only has to be counted once instead of 3 times.
Because this only happens when values are exactly equal, it doesn't matter exactly which triangle you use if there is more than one option (as long as the number of maximums eliminated is the same). Just pick one greedily and move on.
Re: 10159  Star
Humm, so if there is some lines that collide forming 3 I choose that? I did not understand very well, what happens in this case:
A B C D E F G H I J K L
1 1 1 1 1 1 1 1 1 1 1 0
 combine A, E, J
 combine B, F, K
 now C can only combine to remove 2, which one to choose? I can choose C, F, I for example
 D can now only remove 2, meaning more 1 will need to be removed
That result is 5 but the answer is 4, so the order does matter. Am I wrong or misunderstand anything?
A B C D E F G H I J K L
1 1 1 1 1 1 1 1 1 1 1 0
 combine A, E, J
 combine B, F, K
 now C can only combine to remove 2, which one to choose? I can choose C, F, I for example
 D can now only remove 2, meaning more 1 will need to be removed
That result is 5 but the answer is 4, so the order does matter. Am I wrong or misunderstand anything?