10859 - Placing Lampposts

All about problems in Volume 108. 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
crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

10859 - Placing Lampposts

Post by crip121 » Wed Sep 30, 2009 12:05 am

after very little effort i came up with a dp solution which has been rejected (WA). but my problem is that, i think judge contains isolated vertex ( junction ). can anybody help me, what will be our choice if there is an isolated vertex? should we place i lamp there :D or will skip it as there is no road to lightning up :D

anyway, any ac code's output is wellcome

Code: Select all

11
4 3
0 1
1 2
2 3
6 5
0 1
0 2
0 3
0 4
4 5

9 8
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 7
0 1
1 2
2 3
3 4
4 5
5 6
6 7
6 5
0 1
1 2
1 3
2 4
3 5
7 6
0 1
1 2
1 3
2 4
3 5
4 6
8 7
0 1
1 2
1 3
2 4
3 5
4 6
5 7
7 6
0 1
1 2
2 3
2 4
3 5
4 6
8 7
0 1
1 2
2 3
2 4
3 5
4 6
5 7
9 8
0 1
1 2
2 3
2 4
3 5
4 6
5 7
6 8
5 1
4 3
and my wa output

Code: Select all

2 1 2
2 1 4
4 0 8
4 1 6
3 2 3
3 1 5
3 0 7
3 0 6
4 2 5
4 1 7
1 0 1
though i think my output is right except the last one. really confused about it :roll:

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 10859 Placing Lampposts

Post by sohel » Wed Sep 30, 2009 6:01 pm

Yes, you have to make sure all the roads receive lights. So, there is no need to place lampposts on isolated nodes!

crip121
New poster
Posts: 29
Joined: Tue Jul 08, 2008 9:04 pm

Re: 10859 Placing Lampposts

Post by crip121 » Wed Sep 30, 2009 6:45 pm

thx vaia, got ac already, in ranklist 5-th :D
nice problem :wink:

output from my previous post is correct.

Post Reply

Return to “Volume 108 (10800-10899)”