E869120's blog

JOI 2022/2023 Final Round Online Contest
By E869120, 14 months ago, In English

Hello, everyone!

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023) Final Round will be held from Sunday, February 12th, 10:00 UTC to Monday, February 13th, 10:00 UTC. The contest information is as follows:

  • Contest duration: 4 hours (You can choose start time freely in 24-hour window)
  • Number of tasks: 5 tasks
  • Max score for each task: 100 points
  • Style: IOI-Style (There may be some partial scores)
  • Problem Statement: Japanese & English

Note that since the contest ends at Monday, February 13th, 10:00 UTC, if you start the contest after Monday, February 13th, 06:00 UTC, the duration will be shorter than 4 hours.

The registration page will be announced 30 minutes before the contest starts. Details are available in the contest information page.

We welcome all participants. Good luck and have fun!

Tags joi, ioi
  • Vote: I like it
  • +237
  • Vote: I do not like it

Comments Comments (13)
| Write comment?
»
14 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Bump

→ Reply
»
14 months ago, # |
  Vote: I like it +34 Vote: I do not like it

Now the contest had ended. Thank you for your participation. Let's discuss the problem!

→ Reply
»
14 months ago, # |
  Vote: I like it +54 Vote: I do not like it

Thanks for the contest!

How to solve P5. Modern Machine?

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +84 Vote: I do not like it

    Observation: at any time, the state can be described by $$$0\le L\le R\le N$$$, where the first $$$L$$$ letters are R, the last $$$N-R$$$ letters are B, while the other letters are the same as initial state.

    First consider subtask 5: $$$L=R=t$$$, note that pressing button $$$A$$$ would change $$$t$$$ into $$$(t+[t<A]+A)\bmod (N+1)$$$, one can solve this subtask by processing queries offline and maintaining such changes using BST. Complexity $$$O(N+(M+Q)\log Q)$$$. (There exists other solutions.)

    Now we are interested in simulating a bunch of presses to make $$$L=R$$$. Note that the influence of several presses in the prefix or suffix can be simply summed (sum of their distances to borders), and a press in the middle part doubles the length of either prefix or suffix, so there's only $$$O(\log N)$$$ such presses. You can find them quickly in $$$O(\log M)$$$ time each, giving $$$O(\log N \log M)$$$ complexity per query.

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

What is the intended complexity of P3 Maze for 100 points?

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

    I found a O(RClogN) solution and a O(RC) solution.

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

      My solution with RClog got only 84.Did you manage to get 100 with the RClog solution?

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

        My RClog got 94 and I tried to optimize some constants, but failed, so I coded RC solution.

        → Reply
      • »
        »
        »
        »
        14 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        My RClogN solution got AC.

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

        I used bitset instead of set and got AC. I'm surprised O(RC log R) doesn't pass, the log part is just one lower bound on a set. I guess the bottleneck is the erasing part, which can be done faster with bitset

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

When will the upsolving stage be opened?

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

    The analysis mode is now started. You can upsolve the problems in Contest Site until February 19th, 2023.

    → Reply
»
14 months ago, # |
  Vote: I like it +91 Vote: I do not like it

This is how to solve C.

→ Reply