Hello Codeforces community,
We are excited to invite you to TOKI Indonesian NOI Open Contest 2022 — an online mirror contest for the Indonesian National Olympiad in Informatics. This national olympiad is one of the stages required for our students to qualify to represent Indonesia in the International Olympiad in Informatics (IOI). You may have seen our past open olympiads (2015, 2016, 2017, 2018, 2019, 2020, 2021), and you can check our past problems here.
The contest is similar to IOI: 2 competition days (+ 1 trial session), each consisting of 3 IOI-style (partial, subtasks) problems to be solved in 5 hours. The schedule is as follows:
- Day 0: 3 October 2022 03:30 — 4 October 2022 01:30 UTC (trial session)
- Day 1: 4 October 2022 06:30 — 5 October 2022 01:30 UTC
- Day 2: 5 October 2022 06:30 — 6 October 2022 01:30 UTC
Each contestant can select any 5-hour window within the time range to do the contest for each competition day. Each contestant may start the contest at any time within the time range by clicking the "start" button. There will be no additional time given if a contestant starts the contest less than 5 hours before the contest ends. The scoreboard will be hidden until the contest has ended.
All three contests are now available on TLX. Please register in those contests. You may need to register for a TLX account if you do not have one.
For more detailed information and rules, see our official website.
See you on the leaderboard!
UPD: The official contest has ended, thanks for your participation!
Congratulations to errorgorn for winning the contest! The result of the open contest can be found on our website.
You can upsolve the problems here. The editorials can be found in the contest link or upsolve link.
If you'd like to give feedback to the contest, you may submit a response in this form.
We thank everyone who is involved:
- Scientific Committee: AMnu, steven.novaryo, faustaadp, rama_pang, Pyqe, Mushthofa
- Technical Committee: fushar, faishol27, Samuel
- Authors: rama_pang, Pyqe, Mushthofa
- Tester: nirvana
We hope we can conduct the open OI again, and see you next year!
Have fun and best of luck to all participants! The problems will be great no doubt! For others, please do join the open contest as well — it will be fun (they said). See you on the leaderboard! 💗
P.S. I can't believe it has been a year since I last participated, I'm feeling a bit nostalgic...
As a former participant two years ago, I can vouch that the questions would be interesting and intriguing :D
The trial session will begin in about 20 minutes.
A friendly reminder that the first competition day will begin in 20 minutes. You can choose any 5-hour window within the time range to do the contest. Good luck!
P.S. Please do not discuss the problems until the Day 1 contest ends.
The second day of the contest will be available in 20 minutes. Good luck and have fun!
will there be an editorial? How to solve Day 1 1C. Building Lighthouses?
Yes, the editorial will be released in a few days.
Consider the Cartesian tree of the array $$$A$$$. Try to come up with a DP, where the $$$(l,r)$$$ states only involve the vertices in the Cartesian tree.
Suppose we are in subarray $$$[l, r]$$$, and lighthouse $$$l-1$$$ is not valid. So, we need to increase a lighthouse $$$x \in [l, r]$$$ to height $$$A[l-1]$$$. Are there any special properties of $$$x$$$?
We can always make $$$x \leq \arg\max_{s \in [l, r]} A[s]$$$. For lighthouse $$$r+1$$$, we can always make $$$x \geq \arg\max_{s \in [l, r]} A[s]$$$ too.
Define $$$dp(l,r,x,b_l,b_r)$$$, where:
Suppose all values in $$$A$$$ are distinct. The number of occurrences of each value in the final configuration is always $$$\leq 3$$$.
We can always make the values in $$$A$$$ distinct by setting $$$A_i := A_i + i \times \epsilon$$$.
Instead of storing $$$x$$$ in our DP state, we can store $$$c \leq 2$$$ of the number of lighthouses we can make valid by increasing to some value $$$x$$$ outside the subarray. Now there are $$$O(N)$$$ states, and each transition is $$$O(1)$$$.
So it seems I got the only AK :sunglasses:
My screencast for day 2 is here (sub 1 hour AK).
The contest is over, thanks for participating! The scoreboard for the open contest is available here. We will publish the post-contest summary, including problems and editorials for upsolving, after the official closing ceremony in a few days.
The contest footage for official participants is also available here.