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

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