10159 - Star

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Eric3k
New poster
Posts: 29
Joined: Mon Apr 29, 2002 5:22 pm
Contact:

10159 - Star

Post 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.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

10159 - Star > Need help.

Post 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.
_.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Your values are correct.

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Thanks Kuegel!

Post 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 :o
I'll try to read, then check the algo again.
A couple of I/O would help :wink:

Thanks, and keep posting!

Edited: :o 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.
_.

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

10159?

Post 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?

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post 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

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

Re: 10159 - Star

Post 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?

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

Re: 10159 - Star

Post by Bruno »

Finally got accepted! The idea above is correct :D, 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:

Code: Select all

9 7 3 8 8 5 0 1 4 9 7 1
The correct output is:

Code: Select all

44 131
Thank you!

maweaver
New poster
Posts: 3
Joined: Fri Jun 03, 2011 11:03 pm

Re: 10159 - Star

Post 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.

Bruno
New poster
Posts: 22
Joined: Thu Oct 01, 2009 9:03 pm

Re: 10159 - Star

Post 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? :(

Post Reply

Return to “Volume 101 (10100-10199)”