11156 - Continuous Drawing

[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.

[rio]

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

[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.

[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.

[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.

[ardiankp]

Thx a lot!

Btw how do you get the 20 bound?

[Per]

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]

Great!

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

[FAQ]

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

Thanks

[emotional blind]

What is the output for the input:

Code: Select all

1
2
A1 A1
B2 B2

[Jan]

Your case is not valid I think.