maroonrk's blog

Marubeni Programming Contest 2024 (AtCoder Regular Contest 183) Announcement
By maroonrk, history, 3 weeks ago, In English

We will hold Marubeni Programming Contest 2024 (AtCoder Regular Contest 183).

The point values will be 400-600-600-800-900-1100.

We are looking forward to your participation!

  • Vote: I like it
  • +102
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Solved B at 119 min 46 sec! Thrilling!

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What does run-length encoding mean for the editorial in question B thanks!

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think they don't actually mean run-length encoding, but rather:

    compress identical adjacent elements to one element

    → Reply
»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

problem B was really interesting, thanks you!

→ Reply
»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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}$$$.

→ Reply
»
3 weeks ago, # |
  Vote: I like it +64 Vote: I do not like it

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?

→ Reply