Hello, everyone!
The 23nd Japanese Olympiad in Informatics (JOI 2023/2024) Final Round will be held from Sunday, February 04th, 10:00 UTC to Monday, February 05th, 10:00 UTC. The contest information is as follows:
- Contest duration: 4 hours (You can choose start time freely in 24-hour window)
- Number of tasks: 5 tasks
- Max score for each task: 100 points
- Style: IOI-Style (There may be some partial scores)
- Problem Statement: Japanese & English
Note that since the contest ends at Monday, February 05th, 10:00 UTC, if you start the contest after Monday, February 05th, 06:00 UTC, the duration will be shorter than 4 hours.
The registration page and live scoreboard will be announced 30 minutes before the contest starts. Details are available in the contest information page.
We welcome all participants. Good luck and have fun!
UPD1: The contest will start in 24 hours.
UPD2: Now the contest is started, so good luck and have fun. Note that you can start any time in 24-hour window.
UPD3: The contest is ended. Thank you for your participation.
anyone know how to solve problem 3 and 5 ?
For problem 3, first consider how to answer one question. Balls at the same position can be merged, then consider the entire process in reverse order, The last ball collected must be one of the balls on left or right side of the end point, and the last $$$k$$$ balls collected must form an interval. Enumerate the last ball collected(at most 2 different balls possible), the observation leads a DP that $$$f_{l,r}$$$ indicates if we collect the balls between $$$l$$$-th to the $$$r$$$-th position at the end of entire process, what is the minimal time to collect them. It answers a question in $$$O(n^2)$$$ time, where $$$n$$$ is the different places that have balls. If we calculate all $$$n$$$ beginning position, we can answer a question in $$$O(\log n)$$$ time.
Another observation is that if we have $$$n$$$ different positions that have balls, the minimal time is at least $$$n^2/2$$$, so we only need to solve the task for $$$n\le 1000$$$, previous $$$O(n^3)$$$ solution works.
How to prove that the last ball collected is the leftmost or rightmost ball ?
Assume you pick up anything in the middle right now, but you will pass this point atleast once more (when you go from leftmost to rightmost or vice versa), its just optimal to pick it up then.
Thanks, nice observation.
Problems were entertaining; btw when will the upsolving open?
Hello!
There is something about JOI rounds that makes me particularly sad, that being the absence of English editorials.
JOI problems are really helpful for people that try to reach high levels, and I am sure that the release of English editorials will make a really big change in something I like to call the "JOI Effect" (positive effect of solving past JOI problems).
I heard the fact that one of the main reasons why the Chinese people are so good is because there are tons of high quality editorials for problems, on websites like Luogu and other Chinese OJ's. As a person that wants the best for future generations, I feel like this thing should also happen with English editorials, as translating an editorial using online services can often times be inaccurate and mislead into a wrong understanding of a solution.
I hope for future English editorials!
Cristofor
it is a shame that your comment gets downvoted, growing up something i loved about contests and olympiads was that editorials and model solution were written with the actual desire to educate people, but unfortunately i see more and more people approving this mindset of not explaining the approach in a written format.
even having explanations in comments would be great, they don't have to be official or anything of sorts, i guess community written comments would be just as good too.
Gonna make one for the problems and subtasks I solved, Not the best but it can help anyway.
What algorithms are needed to fully get The second problem? I only got the $$$N <= 50$$$ $$$N <= 3000$$$ and using 2 dijkstras.
Then you can do binary search!
First you need to do 2 dijkstras from $$$T.$$$ and $$$S.$$$ node.
Then, suppose we went $$$u.$$$ node from $$$S.$$$ node with $$$x$$$ time, we need to go $$$v.$$$ node from $$$T.$$$ node with $$$K - (x + L)$$$.
(Because we can construct a road between $$$u$$$ and $$$v$$$.)
damn, thanks! I thought it had to do with some complex solution because of the subtasks lol.
I have some trouble implementing this solution, How can I avoid counting same pair of (u, v) twice?
For example, if both S and T can reach u and v, and you can build a bridge from (u, v) and (v, u), then pair (u, v) will be count twice.
You need to do some easy examples:
Suppose you built a road between $$$u$$$ and $$$v$$$ and your road is $$$S \rightarrow u \rightarrow v \rightarrow T$$$: You went $$$u$$$ from $$$S$$$ within $$$x$$$, went $$$v$$$ from $$$T$$$ within $$$y$$$. And if we went within $$$x + y + L$$$ and $$$x + y + L \le K$$$.
Suppose you built a road between $$$u$$$ and $$$v$$$ and your road is $$$S \rightarrow v \rightarrow u \rightarrow T$$$: You went $$$u$$$ from $$$T$$$ within $$$a$$$, went $$$v$$$ from $$$S$$$ within $$$b$$$. And if we went within $$$a + b + L$$$ and $$$a + b + L \le K$$$.
$$$IF$$$ $$$x + y + L \le K$$$
$$$&$$$ $$$a + b + L \le K$$$
$$$\rightarrow$$$ $$$x + a \le K$$$ (or $$$y + b \le K$$$)
And the answer is all edges — $$$n * (n - 1) / 2$$$.
Alright, thank you very much!
Is it true that you solved the problem using a dynamic lazy segment tree?
Anyone know how to get 100 pts on problem 4?
For a better understanding of my approach, let's represent each person $$$i$$$ as a segment $$$(B_i, A_i)$$$. So now for every query, we need to find out whether there is a permutation $$$p$$$ of left bounds such that all segments will stay valid $$$(B_{p[i]} < A_i)$$$ and all left bounds will change their position $$$(p[i]!= i)$$$.
The first thing that you have to notice is that you can't rearrange left bounds correctly if there is a segment that doesn't intersect with anyone else. In other words, all positions the segment covers are covered only by that segment. Otherwise, there is a strategy to arrange them. The straight-forward check of that condition takes $$$50$$$ points.
In order to get $$$100$$$ points, we need to precompute the following for every segment:
$$$lb_i$$$ is the closest segment that intersects with the $$$ith$$$ segment in the array from the left: $$$(lb_i < i)$$$.
$$$rb_i$$$ is the closest segment that intersects with the $$$ith$$$ segment in the array from the right $$$(rb_i > i)$$$.
Both things can be precomputed by a segment tree with an assignment on segment. To be specific, we iterate from left to right, and for every position $$$x$$$, we maintain $$$tr[x]$$$, the $$$max$$$ index of the segment that covers $$$x$$$ ($$$tr[x] < i)$$$. Than, to find $$$lb_i$$$, we just take $$$max$$$ on the interval $$$[B_i, A_i]$$$ in the seg-tree.
Finally, both arrays help us respond to the queries offline. Here we iterate from left to right, and on each iteration we respond to queries with the right bound equal to $$$i$$$. To respond to each query quickly, we have to maintain another array $$$f$$$, where $$$f_j$$$ initially points to $$$lb_j$$$, but when $$$rb_j <= i$$$, $$$f_j$$$ becomes $$$+\infty$$$. This structure helps us to respond to each query in $$$O(logn)$$$ as the task is reduced to $$$min$$$ on segment.
I hope I explained it in enough detail; feel free to ask.
Thank you and I appreciate your helpful explanation.
How to solve E?
I'm yet to implement it, but probably this will work.
Thanks!
I upsolved everything, including the solution to E, in the way I described above.
code
When we can upsolved it ?
They are on Atcoder
ojuz Any plans on adding them to your website?
Or is there another place where they are already added with English statements? I saw Atcoder has them but the translation is pretty bad IMO.
We'll try to upload it when Spring Camp materials are available (I just want to do it simultaneously for efficiency, sorry)
Anyway, you could use https://www.acmicpc.net/category/detail/4176 instead. You can use English UI by clicking "English (Beta)" at the bottom.
You can also download the statements from the website (they are available both in English and Japanese), and submit on AtCoder, if it's the translation that's bugging you.