Page 1 of 1
10159 - Star
Posted: Wed Jul 21, 2004 5:51 am
by Eric3k
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.
10159 - Star > Need help.
Posted: Wed Jul 28, 2004 5:01 am
by _.B._
Greetings!
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
Output
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
Thanks in advance!
P.S.: if you know any critical I/O, will really appreciate it too.
Posted: Wed Jul 28, 2004 12:14 pm
by Adrian Kuegel
Your values are correct.
Thanks Kuegel!
Posted: Fri Jul 30, 2004 4:34 am
by _.B._
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 char-by-char 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?
Posted: Thu Feb 15, 2007 2:26 am
by Vexorian
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?
Posted: Thu Feb 15, 2007 5:46 am
by Vexorian
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:
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
Posted: Wed Jun 01, 2011 11:53 pm
by Bruno
I cant get an AC, here are some input and my output:
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
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 (0-9) 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?
Re: 10159 - Star
Posted: Thu Jun 02, 2011 1:40 am
by Bruno
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!
Re: 10159 - Star
Posted: Fri Jun 03, 2011 11:22 pm
by maweaver
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.
Re: 10159 - Star
Posted: Sat Jun 04, 2011 1:17 am
by Bruno
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?
