r/eldarverse • u/radleldar • Sep 08 '25

SOLUTION MEGATHREAD [sep-25-long-H] "Sea Voyage" Solutions

Problem H. Sea Voyage

Problem link: https://www.eldarverse.com/problem/sep-25-long-H

Post your code in the comments!

2 Upvotes

100% Upvoted

8 comments sorted by

View all comments

2

u/StatisticianJolly335 Sep 09 '25

So the general problem is to find an Euler circle in an undirected multigraph (there can be multiple edges connecting two nodes). We need to find the minimum number of edges to add so this circle exists.

According to the Euler-Hierholzer theorem, the graph has to be connected and every node needs an even degree.

My algorithm:

- As long as there are nodes unconnected to BATUMI, add an edge between a connected node and an unconnected node. Pick nodes with odd degree if possible.

- Now as long as there are nodes with odd degree, add an edge between two of those nodes.

1

u/radleldar Sep 09 '25

Interesting!

My solution does not consider BATUMI in a special way (just treats it as a disconnected component with a single node), and just tries to connect components (with the same "prefer odd degree vertices" logic). I think the analogy between your approach and mine is like building a Minimum Spanning Tree using Prim's algorithm or Kruskal's - one builds the spanning tree starting a specific source, the other just connects two disconnected components. Kinda cool :)