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!
Bump
Now the contest had ended. Thank you for your participation. Let's discuss the problem!
Thanks for the contest!
How to solve P5. Modern Machine?
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 areB, 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.
What is the intended complexity of P3 Maze for 100 points?
I found a O(RClogN) solution and a O(RC) solution.
My solution with RClog got only 84.Did you manage to get 100 with the RClog solution?
My RClog got 94 and I tried to optimize some constants, but failed, so I coded RC solution.
My RClogN solution got AC.
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
When will the upsolving stage be opened?
The analysis mode is now started. You can upsolve the problems in Contest Site until February 19th, 2023.
This is how to solve C.