Way to solve Codeforces Round#416 problem E in O(input) steps

Revision en2, by fast_photon, 2024-06-28 14:59:54

I'm sorry about my poor English.

First, make every cross a node. Give each node a position $$$(x, y)$$$. There is an edge between two nodes if and only if:
- $$$|x_1-x_2|+|y_1-y_2|=1$$$ - The edge splits two different characters.

For example, for the example situation in the problem.

We will get the graph:

Tags 811e, low complexity solution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en16 English fast_photon 2024-06-30 07:03:15 4
en15 English fast_photon 2024-06-30 07:02:06 48
en14 English fast_photon 2024-06-30 07:00:22 20 #462 -> #416
en13 English fast_photon 2024-06-30 06:58:21 4 There's a mistake in spoiler (published)
en12 English fast_photon 2024-06-30 06:57:26 0 Tiny change: '811E or #462 E in $\ma' -> '811E or #416 E in $\ma' (saved to drafts)
en11 English fast_photon 2024-06-30 06:56:20 0 (published)
en10 English fast_photon 2024-06-30 06:50:04 5954
en9 English fast_photon 2024-06-30 06:44:28 45
en8 English fast_photon 2024-06-30 06:37:26 8
en7 English fast_photon 2024-06-30 06:35:40 15
en6 English fast_photon 2024-06-30 06:35:15 4
en5 English fast_photon 2024-06-30 06:34:44 4 Tiny change: '_1-y_2|=1$\n- The ed' -> '_1-y_2|=1$ \n- The ed'
en4 English fast_photon 2024-06-30 06:34:04 14130
en3 English fast_photon 2024-06-28 15:53:29 406
en2 English fast_photon 2024-06-28 14:59:54 92
en1 English fast_photon 2024-06-28 14:49:37 437 Initial revision (saved to drafts)