Hello, everyone!
The 24th Japanese Olympiad in Informatics (JOI 2024/2025) Final Round will be held from Sunday, February 02th, 10:00 UTC to Monday, February 03th, 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 03th, 10:00 UTC, if you start the contest after Monday, February 03th, 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 12 hours.
UPD2: The contest is started.
UPD3: The contest is ended. Thank you for your participation.
bump
How to solve the
$$$1, 1, \dots , n - 1$$$
case in P5?
My solution for the 12 points was some simulation. In each moment of time, I move the package at the post office which is furthest from its destination. My intuition for this was that it would maximize the number of simultaneous movements that happen, but I can't prove it formally lol
The proof of your claim is also pretty intuitive. Notice that when two packages meet, they will follow the same path until one of them reaches its destination. If we decide to let the one that has a shorter path go first, then the other one will still have at least 2 edges to pass through after the first one arrives at its destination.
From that greedy solution, we can make another claim: for an edge, the last time some package passes through it is only dependent on the distances of packages passing through this edge.
The intuition here is that all the edges before will "sort" those packages the same way as the current edge will. Packages that end before that edge will have a lower priority than all the other ones, so they won't change the order in which packages come to this edge.
To calculate the answer on each edge, we can store the distances on a segment tree. If you handle distance offsets well, the cycle becomes a simple sweepline. Tree parts of the graph work similarly but require small-to-large merging of those segment trees.
Where can I find the editorials?
How to solve P4
You can get 46pts using bitmask dp.
Can you elaborate? Maybe implementation?
Note that it can always be done with 21 ties, even if we don't ignore any of the audience numbers: assign each tie to one of 1, 2, ..., 21, and for each audience number, only make moves to the tie we assign to that number.
Then, for each index $$$i$$$ in the numbers $$$A_i$$$ called out by the audience, we can figure out the possible sets of all lengths of ties after that number is called. The answer, then, is after $$$A_n$$$ is called out, the set with the least number of 1 bits. This will take $$$2^{\max A_i}$$$ for each index, for a complexity of $$$O(2^{\max A_i} \cdot n)$$$.
dp[i][mask] = Is it possible that I haven't ignored the i-th performance and after it, my models have the ties in the mask?
dp[0][mask] = true // When I have 0 performance, anything is possible
dp[1][mask | (1 << a[1])] = true // Since I had the performance 1, I should have length a[1] in my mask.
dp[i][mask] = if the mask doesn't contain a[i], then this is never possible, to do this performance and the audience is angry with us.
Now let's consider the case when the mask does contain a[i]-th bit on.
It could have come from a length <= a[i]. So I should try all possible states and at least one of them should be true. Also for each mask either we take dp[i-1][mask] or dp[i-2][mask] since I can choose to ignore i-1 performance.
if dp[n][mask] or dp[n-1][mask] is true, then answer min= the number of on bits in the mask.
To optimize this, note the for each mask, only the largest $$$n$$$ that $$$dp(n,mask)=1$$$ is important, so record $$$f(mask)$$$ as the largest $$$n$$$, and you can do the transition in $$$O(na+2^aa^2)$$$.
$$$f(mask)=max f(new mask)$$$
Now let's say $$$n = f(mask)$$$
if $$$a[n + 2]$$$ is in $$$mask$$$, $$$f(mask) += 2$$$
if $$$a[n + 1]$$$ is in $$$mask$$$, $$$f(mask) += 1$$$
And we repeat until one of them holds.
How this is it most $$$O(na)?$$$
record $$$next_1(p,x)=$$$ minimum $$$p' \gt p$$$ that $$$a_{p'}=x$$$, and $$$next_2(p,x)=$$$ minimum $$$p'\geq p$$$ that $$$a_{p'}=a_p$$$ and $$$a_{p'+1}=x$$$.
Now it makes complete sense to me. Thanks.
I couldn't get the idea. Can you explain, please, more detailed? (Also, I look ko_osaga's solution.)
Where can I upsolve?
My code (joi25*.cpp)
Are test data and standard programs available?
Could you explain your solutions for problems even for 1-st problem?
For problem D, I wrote a brute force bitmask dp ($$$O(n2^a)$$$), and deleted all states that will not contribute to the answer. That is to say, if there are two states $$$S_1,S_2$$$ with the same number of $$$1$$$, and for every $$$k$$$, the $$$k-$$$th highest $$$1$$$ of $$$S_1$$$ is always not smaller than $$$S_2$$$, then we can delete $$$S_2$$$. The check was simply brute force, so the complexity is $$$O(nk^2a)$$$ where $$$k$$$ is the maximum number of states at a single position. However, it passed all the tests with a maximum time of only 1 second. Can anyone prove that the number of states is small or give a hack to this solution?
Will there be analysis mode?
It's linked from https://contests.ioi-jp.org/joi-ho-2025/index-en.html now:
https://atcoder.jp/contests/joi2025ho/tasks
Why does JOI every time have such mean grading criteria? What was the point of having such a slow ascent from ~60 bits to ~20 bits in fortune telling?
I should delete this account...
you commented on the wrong blog, but nevertheless
my first (and only) solution was 30 bits, and it got 50 points. I think that was fair considering I only have little idea about 70+ score (and the details seems unclear to me), and evidently 100 is practically impossible.
If the harder part takes so much effort, why should it not be worth points?
I think <20 deserves more points than it actually does (with regards to optimized 30 bits which leads to like 55).
Hello! can someone explain why this solution for problem D doesn't get TLE?
I mean, isn't its complexity $$$O(N*2 ^ {21}))$$$