### prabowo's blog

By prabowo, history, 15 months ago,

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:

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.

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:

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

• +133

 » 15 months ago, # |   +52 Last year's problems were interesting to say the least! I cant wait to join the mirror this year!!!
•  » » 15 months ago, # ^ |   +8 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. :)
 » 15 months ago, # |   +42 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....)
 » 15 months ago, # |   +24 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.
 » 15 months ago, # |   +16 Good luck everyone, especially for the official participants !
•  » » 15 months ago, # ^ |   +13 As you are an official participant yourself, good luck to you as well ;)
•  » » » 15 months ago, # ^ |   +3 Thanks, lets give it our best !
 » 15 months ago, # |   0 need day 0 editorial
 » 15 months ago, # |   +8 Will we be able to upsolve afterwards ?
•  » » 15 months ago, # ^ |   +6 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!
•  » » » 15 months ago, # ^ |   +3 Thanks for information.
 » 15 months ago, # | ← Rev. 4 →   +14 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: SolutionDefine 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: If we keep $A[i]$, we can 'clone' all the arrays in which $A[i]$ is an element, and append $A[idx]$ to them. There are $P(i)$ such arrays. If we remove $A[i]$, we set $i \leftarrow i-1$ to consider the previous element. 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 $P(x) = \sum_{i = n}^{x-1}P(i),$and from the second point, we have $Q(x) = P(n) + Q(n) - (n==0),$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
•  » » 15 months ago, # ^ |   +9 orz orz orz orz orz
•  » » 15 months ago, # ^ |   +4 orz congrats for first place!!!
•  » » 15 months ago, # ^ |   +3 Wow!! You're the only official participant who solved that problem, and using unintended solution, and u won the first place. Congraattsss!!!
 » 15 months ago, # |   0 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.