### rama_pang's blog

By rama_pang, history, 2 months ago,

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:

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.

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:

We hope we can conduct the open OI again, and see you next year!

• +126

 » 2 months ago, # |   +28 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...
 » 2 months ago, # |   +10 As a former participant two years ago, I can vouch that the questions would be interesting and intriguing :D
 » 2 months ago, # |   +18 The trial session will begin in about 20 minutes.
 » 2 months ago, # |   +32 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.
 » 2 months ago, # |   +32 The second day of the contest will be available in 20 minutes. Good luck and have fun!
 » 2 months ago, # |   +10 will there be an editorial? How to solve Day 1 1C. Building Lighthouses?
•  » » 2 months ago, # ^ |   +9 Yes, the editorial will be released in a few days. A few hints for 1C. Building LighthousesHint 1Consider 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. Hint 2Suppose 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$? Hint 3We 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. Hint 4Define $dp(l,r,x,b_l,b_r)$, where: it is the minimum cost to make subarray $[l,r]$ valid, if we can also increase a lighthouse to height $x$ directly to make it valid (i.e., we have a visible lighthouse of height $x$ outside the subarray). If the boolean $b_l = 1$, then in subarray $[l,r]$, we must increase at least one index to height $A[l-1]$, as currently lighthouse $l-1$ is not valid. If the boolean $b_r = 1$, then in subarray $[l,r]$, we must increase at least one index to height $A[r+1]$, as currently lighthouse $r+1$ is not valid. Hint 5Suppose all values in $A$ are distinct. The number of occurrences of each value in the final configuration is always $\leq 3$. Hint 6We can always make the values in $A$ distinct by setting $A_i := A_i + i \times \epsilon$. Hint 7Instead 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)$.
 » 2 months ago, # |   +45 So it seems I got the only AK :sunglasses:My screencast for day 2 is here (sub 1 hour AK). I wanted to upload day 1 too but...
 » 2 months ago, # |   +17 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.
•  » » 2 months ago, # ^ |   0 The contest footage for official participants is also available here.