Page 1 of 1

### 11156 - Continuous Drawing

Posted: 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
``````

Posted: Mon Jan 22, 2007 1:26 pm
I found my bug and got AC.
Anyway ubove output seems right.

Posted: 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.

Posted: 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.

Posted: 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.

Posted: Mon Jan 22, 2007 6:50 pm
Thx a lot!

Btw how do you get the 20 bound?

Posted: 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.)

Posted: Tue Jan 23, 2007 4:42 am
Great!

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

Posted: 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

Posted: Sun Nov 18, 2007 7:52 am
What is the output for the input:

Code: Select all

``````1
2
A1 A1
B2 B2``````

Posted: Sun Nov 18, 2007 7:33 pm
Your case is not valid I think.