Please read the new rule regarding the restriction on the use of AI tools. ×

luogu_official's blog

【MX-X6/J7】Mengxiong Weekly (Open, Div.1+Div.3)
By luogu_official, history, 40 hours ago, In English

We will hold 【MX-X6/J7】Mengxiong Weekly (Open) on Luogu. This is a Div.1+Div.3 round provided by our collaborator. If you cannot understand Chinese, ChatGPT may be helpful.

We are looking forward to your participation! If you cannot understand Chinese, ChatGPT may be helpful. We are working on establishing an English platform, but it takes time. We plan to complete this task by the end of 2024 or early 2025.

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

»
40 hours ago, # |
  Vote: I like it -24 Vote: I do not like it

hope the adminers of luogu will not use their website to play genshine

→ Reply
  • »
    »
    39 hours ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    hope the adminers of luogu will not use their website to play florr.io

    → Reply
  • »
    »
    39 hours ago, # ^ |
    ← Rev. 3   Vote: I like it -17 Vote: I do not like it

    tang

    → Reply
»
39 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

Thanks to MengXiong and Luogu for the quality contest.

qpzc

→ Reply
»
38 hours ago, # |
  Vote: I like it +4 Vote: I do not like it

At first I thought the contest looked very early due to different time zones, but it seems that the contest is at 13:30 even in China? Is that a time when Chinese people are usually free? I'd assumed that they would either be at school or work.

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

    Is luogu good to practice on?

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

    It's our National Day and most of us are on holiday

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

    And this year, our National Day holiday is from Oct. 1st to Oct. 7th

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

      But some students in China can only have a three-day vacation.

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

        But some students in China can only have a less-than-half-day vacation. Guess who.

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

          Is Hunan Normal University so miserable?Senior 3rd students in my city can have a 4-day off.I'm in Nantong,Jiangsu.

          → Reply
  • »
    »
    25 hours ago, # ^ |
    ← Rev. 2   Vote: I like it -20 Vote: I do not like it

    Why you are in China,From Nanjing Foreign Language School?You should know it

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

    It's during the National Day holiday,isn't it?

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

How to E?

→ Reply
  • »
    »
    18 hours ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    If the operation 3 is global (subtask 3), we can maintain a binary trie (separate by the lowest bit first) with lazy propagation.

    In general, we cut out a subtree, add some value for it, and put it back into another position. We might need to merge it with an existing subtree, but we can just merge them recursively in amorized $$$O(1)$$$ time (potential: number of nodes. reference).

    → Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest. T2 is really interesting. I stucked in T3.

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

Can we submit after the contest is over ?

If yes, then how ?

→ Reply
  • »
    »
    15 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    It'll have to wait until the administrators add the problems to the main problem archive. After that, one may submit a problem when accessing it from the archive.

    upd. I've bumped the administrator, it should be available now :)

    → Reply
»
17 hours ago, # |
  Vote: I like it +19 Vote: I do not like it

I got accepted for Div1F with $$$O(\sqrt{q} (n+q) \log(n+q)^2)$$$ time (in < 1 sec).

When $$$n$$$ is large enough, I checked every vertex which has a monent to have degree $$$\ge n-2$$$. There are $$$O(\min\{ n, q/n \})$$$ such vertices. For each vertex, since I didn't have a suitable link cut tree or something, I calculated the cost with 2 logs using offline dynamic connectivity. I feel like it might be as fast as 1 log.

Is it indeed that fast or there are not many tests with about $$$\sqrt{q}$$$ key vertices?

→ Reply
  • »
    »
    15 hours ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Indeed, I did not anticipate this solution and therefore most tests (unfortunately) have $$$n\geq 10^4$$$. I think I had put in a few tests with something around $$$n=500, q=3\times 10^5$$$ (and I switched root every $$$3n$$$ operations or so) just in case, but it was not specially constructed against this solution, so the amount of key vertices may still be small.

    The reason for the TL to be 5s is that one of the testers wrote a self adjusting top tree which needs ~4s, and none of our testers (nor me) thought of anything between $$$O((n+q)\log^2n)$$$ and $$$O(nq)$$$.

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

Is there an editorial for these problems ?

If yes, where can I find it ?

→ Reply