We will hold Marubeni Programming Contest 2024 (AtCoder Regular Contest 183).
- Contest URL: https://atcoder.jp/contests/arc183
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240825T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: maroonrk
- Tester: maspy, sigma425
- Rated range: — 2799
The point values will be 400-600-600-800-900-1100.
We are looking forward to your participation!
Solved B at 119 min 46 sec! Thrilling!
What does run-length encoding mean for the editorial in question B thanks!
I think they don't actually mean run-length encoding, but rather:
compress identical adjacent elements to one element
Is it possible to provide only the gist part of the solution [by the exclusion of all the templates and typedef stuffs] in the Editorial? I need to scroll a lot of templates of the author and got lost in the middle of the Editorial of problem A.
Can problem D be solved this way? Since a tree is a bipartite graph, the pair of leaves we choose must not belong to the same partite set, ensuring a perfect matching. So we can color each vertex either red or blue based on it's partite set. Next, we need to find an edge that divides the graph into two equal parts. If a perfect matching exists, there should be an equal number of red and blue vertices on either side of this edge(uncertain if this claim is true). However, I'm uncertain whether such an edge always exists. The goal is simply to pair any two vertices from these components. we can pair them in any way, it shall satisfy that they were leaves at the moment they were being paired.
Problem B is novel and interesting, solution to Problem D is beautiful!
I wonder why that my solution to D takes such long time (1864 ms) to execute?
My solution shares the same beginning with the official solution, the last part is based on heavy-light decomposition. I think its time complexity is $$$\mathcal O(N \log N)$$$ with space $$$\mathcal O(N)$$$. It's weird for it to take 1864 ms on one testcase.
The problems are really good, though both D and E are a bit implementation heavy (especially E, considering the fact that there are lots of details in implementing), which makes it really hard to solve both in 2 hours.
Just curious if the sample of B was made weak intentionally or not. It was really frustrating when I forgot a corner case and had no idea why it got WA :(
problem B was really interesting, thanks you!
Thanks for the contest!
Can problem C be solved if the requirement was on the value itself, not the index? $$$X_i$$$ instead of $$$P_{X_i}$$$.
https://atcoder.jp/contests/arc183/submissions/57132775
https://atcoder.jp/contests/arc183/submissions/57133336
the 2 codes are almost same. maroonrk can you check it?