Page 1 of 1

11156 - Continuous Drawing

Posted: Mon Jan 22, 2007 1:16 pm
by rio
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.

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

Posted: Mon Jan 22, 2007 2:59 pm
by ardiankp
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
by rio
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
by Per
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
by ardiankp
Thx a lot! :)

Btw how do you get the 20 bound?

Posted: Mon Jan 22, 2007 8:49 pm
by Per
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
by ardiankp
Great! :)

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

Posted: Sat Feb 10, 2007 4:11 am
by FAQ
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
by emotional blind
What is the output for the input:

Code: Select all

1
2
A1 A1
B2 B2

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