Hello Codeforces community,
We are excited to invite you to TOKI Indonesian NOI Open Contest 2023 — 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, 2022), 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: 28 August 2023 11:00 — 29 August 2023 06:00 UTC (trial session)
- Day 1: 29 August 2023 07:00 — 30 August 2023 06:00 UTC
- Day 2: 30 August 2023 07:00 — 1 September 2023 06:00 UTC (2 days)
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.
We are aware that the contest days overlap with IOI 2023; unfortunately, we cannot change the dates.
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!
The result of the open contest can be found on our website.
You can upsolve the problems here. The official editorials are available in the upsolve link
We thank everyone who is involved:
- Scientific Committee: hocky, Mushtofa, yz_, Pyqe, rama_pang
- Technical Committee: aguss787, AVM.Martin, fushar, siplusplus, vioalbert
- Organising Committee: Drew_, kalEl2001
- Authors: ayaze, yz_, prabowo, Pyqe, rama_pang
- Tester: ArvinCiu, faustaadp, jt3698
We hope we can conduct the open OI again, and see you next year!
You can now start your 5-hour window for the mirror of day 1. Good luck and have fun!
Will be there upsolving?
Yes! Further information regarding upsolving will be informed once everything is over. Stay tuned!
You can already start the 5-hour window for day 2, good luck everyone! Note that the time interval for day 2 is two days.
Will there be a scoreboard after the contest?
I see it now :) I got a gold, woo! It's here if anyone's wondering.
How does the medal spread work here?
Follows the medal score cutoffs for the actual competition
Congrats on solving day2 B and C. What were your ideas for there problems?
For problem B, I solved it in the case of $$$P_i = i-1$$$ and then made the solution more general. For problem C, I used divide-and-conquer. I don't want to give it away, but I can give a hint for C if you'd like.
For problem C..
Let f(T) be the maximum range of numbers which can be solved within n days. Can you come up with base case(s) / a recursive definition for function f?
If you can't figure it out, then try hard-code subtask 2. That's how I figured it out.
Suppose we guess at some position $$$a$$$ for the first shoe and $$$b$$$ for the second shoe, and let $$$a < b$$$. Let the interval we are currently working in be $$$[l, r]$$$. Then after the second shoe is sent, we receive feedback for the first shoe:
$$$f(T-2) \hspace{1em} | \hspace{1em} f(T-2) \hspace{1em} | \hspace{1em} f(T-3)$$$
Therefore, $$$f(n) = f(T-2) + 1 + f(T-2) + 1 + f(T-3)$$$. In fact, if we tabulate $$$f$$$, we see that it closes aligns with the constraints for each subtask.
Now, divide and conquer!
There is a very beautiful solution: Assume that we know that the answer is in $$$[1, n]$$$ and our last query was $$$x$$$. If $$$x$$$ is not in $$$[1, n]$$$, then its exact value and result on that query don't matter. Let $$$f(n)$$$ be the largest Fibonacci number not greater than $$$n$$$. Then you can guarantee that $$$x$$$ is either outside $$$[1, n]$$$, or $$$x = f(n)$$$ by always asking $$$f(n)$$$ as the first query inside $$$[1, n]$$$. Such algorithm gives the exact total number of queries from the problem statement.
Edit: Forgot to mention that this is for 2B (although it should be pretty obvious...)
I assume you already know how to solve the problem when the tree is just a line since you already have 49 points.
The numbering of the nodes in the tree does not actually affect the answer. The answer for one shape of a tree is valid for that shape no matter how the nodes are numbered, so you can ignore the whole "youngest bunny, child with fewest slices first" part.
The solution that works only for lines can be extended to the full tree simply by considering "chains" of parent-child paths in the trees as lines and solving them independently (make sure the numbers aren't duplicated!). We can maximize the value of $$$K$$$ that this approach works for by greedily making the longest chain possible every time we try to create a new chain in the tree.
Submission
Not the person you asked (and my description is kind of abstract), but I hope this helps anyway.
Thank you, your response is a lot better than the one from the person whom he asked xD
Nahh lol, I didn't get 2C and that was half the question, so...
I answered the other half ;)
When will you guys publish the editorial and allow people to upsolve?
The official editorials will be released. For now, you can upsolve the problems here!
Will the test data be published?
They don't usually publish the test cases themselves, but they do (eventually) publish the test case generators for each year here (should be in a repository titled
osn-{year}). These will usually be in tcframe format.