11156 - Continuous Drawing

All about problems in Volume 111. 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
User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

11156 - Continuous Drawing

Post by rio » Mon Jan 22, 2007 1:16 pm

Getting many WA..

Could someone verify my io test ?

With input

Code: Select all

5
0
2
A1 A2
A1 A5
6
A1 C2
B3 C3
C4 C2
C2 D2
A4 E4
A1 A5
7
A1 D3
B3 C3
C4 C1
C2 D2
A4 E5
A1 A5
B1 B5
10
A1 A5
B1 B5
C1 C5
D1 D5
E1 E5
A1 E1
A2 E2
A3 E3
A4 E4
A5 E5
I got

Code: Select all

Case 1: 0.00
Case 2: 4.00
Case 3: 17.24
Case 4: ~x(
Case 5: 46.00
Thanks in advance.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Jan 22, 2007 1:26 pm

I found my bug and got AC.
Anyway ubove output seems right.

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Post by ardiankp » Mon Jan 22, 2007 2:59 pm

Can you share your idea?

I am thinking about using euler theorem, and try to create edges such that all vertices (except at most 2) have even degree, which can be done by dijkstra.

However, the number of vertices will be 2^n and the number of edges can be more than that, which I think is not feasible since n can be as large as 25..

Thanks.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Jan 22, 2007 4:22 pm

However, the number of vertices will be 2^n and the number of edges can be more than that, which I think is not feasible since n can be as large as 25..
Why 2^n? In my way, the number of vertics is only 5x5 = 25, which is feasible.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jan 22, 2007 4:41 pm

It's a Chinese Postman problem.

There's a fairly easy O(x^2*2^x) solution where x is the number of odd nodes in the graph, which will be at most 20.

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Post by ardiankp » Mon Jan 22, 2007 6:50 pm

Thx a lot! :)

Btw how do you get the 20 bound?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jan 22, 2007 8:49 pm

ardiankp wrote:Btw how do you get the 20 bound?
The only vertices which can have odd degree are the endpoints of the line segments, and there at most 2*N of those.

(And now I see that the bound is N < 10 rather than N <= 10, so you will have at most 18 odd vertices.)

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm

Post by ardiankp » Tue Jan 23, 2007 4:42 am

Great! :)

Thx a lot. Hehe.. I still need to learn a lot to have such insight :)

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

Post by FAQ » Sat Feb 10, 2007 4:11 am

I passed all above tests but still got a lot of WAs :( please help me some more tests

Thanks

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sun Nov 18, 2007 7:52 am

What is the output for the input:

Code: Select all

1
2
A1 A1
B2 B2

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Nov 18, 2007 7:33 pm

Your case is not valid I think.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 111 (11100-11199)”