## 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

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

### 11156 - Continuous Drawing

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
``````
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
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.
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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
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
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
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
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
I passed all above tests but still got a lot of WAs please help me some more tests

Thanks
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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