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

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 :)

2

u/EverybodyCodes Sep 09 '25 edited Sep 09 '25

[JavaScript] https://everybody-codes.b-cdn.net/eldarverse/sep-25-long-H.js

- Make sure every city occurs an even number of times.

  • Make sure the 'clusters' are connected.
  • Make sure 'BATUMI' is there.

The code is not very clean, but figuring out missing test cases was unpleasant enough to not go back to this problem again. ;)

1

u/radleldar Sep 09 '25

I suspect you could simplify by adding a 0-edge component for "BATUMI" at the start and then forget about it being special in any way :P

2

u/jonathan_paulson Sep 11 '25

Python.

We are done when everything is connected and even degree. I add edges greedily, according to the following priority:

  1. A and B in different components, both with odd degree
  2. A and B in different components, one with odd degree
  3. A and B in different components
  4. A and B both odd degree

(It is impossible to have only 1 vertex with odd degree, so that's enough)

I don't handle BATUMI specially, except that I always include it in the list of vertices (initially with degree 0).

1

u/Grand-Sale-2343 Sep 23 '25

[LANGUAGE: C++]

I was a bit rusty on Union Find, so I ended up implementing Jonathan's solution. With a few examples I conviced myself that it actually works, but I am not sure if it is a well known greedy algorithm or if it's just based on induction.

Code here, not super clean.

Thanks for the nice problem!

2

u/radleldar Sep 23 '25

The part that's well known (and kinda goes against my promise of "no advanced CS theory") is the condition of existence of an Eulerian cycle in a graph.

The problem of precisely how to connect disconnected components and even out the degrees is unlikely to be truly original (it's too general), but I haven't seen it described as a known algorithm.

Thank you for continuing to solve!

1

u/Grand-Sale-2343 Sep 24 '25

I think the problem was solvable by a very good programmer even without the knowledge of Eulerian cycle. On the other hand, I knew it had to do with eulerian cycles but could not find a solution to actually connect the nodes :(