https://atcoder.jp/contests/arc021/tasks/arc021_4
- Thoughts.
- The strange problem of making a tree with almost the smallest whole area.
- O(ElogE) when the minimum area tree is obtained by the [Kruskal method)
- There are 5000 points, so there are about 10^7 edges.
- It’s a little tough. It takes 200 to calculate the distance.
- Is the key that the input is guaranteed to be random?
- First, divide the point approximately in half
- Just focus on one axis and divide by positive and negative.
- The cost of the Kruskal method is halved because the sides are 1/4 of the cost of the Kruskal method.
- The cost of connecting the two parts is high if you are trying to find the best edge, but this is fine if you connect them properly, only 2 at most worse than in the best case.
- In fact, Curse of the dimension almost all the points have a distance near 1
- I’m not sure if I’ll be able to make it in half the time.
- If they don’t make it in time, they need to be broken into smaller pieces.
- Judging from the minimum score of the sample, you can divide it into 16 pieces and connect them appropriately.
- The strange problem of making a tree with almost the smallest whole area.
- Official Explanation
- It’s 200 dimensions, so I’m splitting it into 200 pieces.
- You don’t do that and prove that it fits within 1.01 times the optimal solution…
This page is auto-translated from /nishio/arc021_4 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.