Hi everyone,
A few months ago, I participated in a contest and encountered a geometry problem that has been stuck in my head ever since. I have tried searching for the official editorial or any existing solutions, but I couldn't find any.
Could you please provide some hints, a full solution, or even approaches for the subtasks? Since my English is not very good, I'm afraid that re-explaining the problem myself might lead to misunderstandings or incorrect terminology. Therefore, I have included the original problem link here for accuracy: problem here
Thank you very much for your help!
Damn, bro got second prize in VOI
Oh, thanks :3
I think this problem is asking you to find the Steiner tree of those points, which appears to fit in the constraint, since it would need at most K-2 extra Steiner points.
This problem is NP-hard in general but it appears there are some algorithms which work in small enough cases. (link)