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:
Posted: Sun Nov 18, 2007 7:33 pm
by Jan
Your case is not valid I think.