Hello Codeforces community,
We are excited to invite you to TOKI KSN Open Contest 2021 — an online mirror contest for the Indonesia 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) 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: 7 November 2021 09:00 — 8 November 2021 01:30 UTC (trial session)
- Day 1: 8 November 2021 06:30 — 9 November 2021 01:30 UTC
- Day 2: 9 November 2021 06:30 — 10 November 2021 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 any time within the time range, by clicking the "start" button. The scoreboard will be hidden until the contest has ended.
All three contests are now available on TLX.
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!
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 KSN Open, you may submit a response in this form.
We thank everyone who are involved:
- Scientific Committee: prabowo, Yoshiyuki, AMnu, steven.novaryo, vioalbert
- Technical Committee: fushar, faishol27, Samuel
- Authors: fushar, prabowo, AMnu, steven.novaryo, Pyqe
- Testers: rama_pang, hocky, jfcjaya
We hope we can conduct the open OI again, and see you next year!
Last year's problems were interesting to say the least! I cant wait to join the mirror this year!!!
Also, I wish a good luck to all official contestants and mirror participants. Although it's a competition, don't forget to enjoy the problems too. :)
As an official participant in the actual olympiad, I'd like to wish good luck to both the official and mirror participants!
(Let's see how the problems will be this year....)
Good luck to all mirror participants and to all official participants as well.
As an official participant, I am very excited. After 10 months of doing CP, the day is finally here.
Good luck everyone, especially for the official participants !
As you are an official participant yourself, good luck to you as well ;)
Thanks, lets give it our best !
need day 0 editorial
Will we be able to upsolve afterwards ?
Yes, you will be able to upsolve after the announcement of the official result. Editorial will also be available afterwards.
This blog will be updated when those are available, so stay tuned!
Thanks for information.
As the only participant who solved problem 2A during the contest, I found out that my solution to the problem is quite different from the official editorial.
Here is my solution:
Define a final array as an array that can be made by applying $$$0$$$ or more operations described in the problem. For ease of discussion, we will consider the empty array $$$[]$$$ as a valid final array, but we will subtract $$$1$$$ later from our answer when needed.
Notice these observations in general for an index $$$idx$$$ and an array $$$A$$$. Define also two recurrence relations $$$P$$$ and $$$Q$$$.
$$$P(idx)$$$ stores the number of valid final arrays in which $$$A[idx]$$$ is an element. To find the value of $$$P(idx)$$$, let us work backwards from the index $$$idx-1$$$. Set the value of $$$i$$$ initially equal to $$$idx-1$$$. If there are no values between index $$$i$$$ and $$$idx$$$ inclusive that are less than $$$i$$$ and $$$idx$$$, we have two choices:
We stop when there is an element between $$$i$$$ and $$$idx$$$, inclusive, that is less than $$$i$$$ and $$$idx$$$. Why? If there is such an element, we can't remove all elements between $$$i$$$ and $$$idx$$$, so we would only be overcounting previous results.
To efficiently execute this, we only need to stop at the element just before the first element that is smaller than $$$A[idx]$$$. The proof is left to the reader as an exercise.
Meanwhile, $$$Q(idx)$$$ stores the number of valid final arrays in which $$$A[idx]$$$ is not an element. For the first element less than $$$A[idx]$$$, say $$$m$$$, we can remove all elements to the right of it, that is, we can remove the subarray $$$A[m+1..idx]$$$ altogether. That means we can 'clone' all final arrays that are valid when considering the subarray $$$A[1..m]$$$, without appending anything to it. There are $$$P(m) + Q(m)$$$ such arrays if $$$m \neq 0$$$, and $$$P(m) + Q(m) - 1$$$ such arrays if $$$m = 0$$$ (because we consider the empty array as a valid final array, but the problem doesn't, we have to subtract $$$1$$$).
Thus, we have now formulated two formulas.
From the first point, we have
and from the second point, we have
where $$$n$$$ is the last index between $$$1$$$ and $$$x-1$$$ inclusive such that $$$A[n] < A[x]$$$.
The base case would be $$$P(0) = 1$$$ and $$$Q(0) = 0$$$. Our answer will be $$$P(N) + Q(N)$$$.
We can implement this approach with two one-dimensional bottom-up DP arrays, prefix sum, and a method for finding RMQ, such as a segment tree. The final time complexity is $$$O(N \log N)$$$.
Edit: Thanks for all the kind words from everyone who replied to this comment :D
orz orz orz orz orz
orz congrats for first place!!!
Wow!! You're the only official participant who solved that problem, and using unintended solution, and u won the first place. Congraattsss!!!
If you need more challenges for problem 1C, try these two additional subtasks:
$$$Q=2000$$$, $$$N=1200$$$, there are at most $$$3$$$ different materials;
$$$Q=2000$$$, $$$N=800$$$, there are at most $$$5$$$ different materials.