hello!

Why can't I register for the competition?

Good luck have fun everybody! I always have fun with the problems from JOI Spring Camp.

Excited!

Is it like Div2 or does JOI has same difficulty as Div1 ?

When will the analysis mode be opened?

I believe I have a solution for day 1 P2 using $$$1363 \approx k \log (q+1) + (q-1) \log (k)$$$ queries after contest ended.

The organizers probably purposely set the limits close to $$$k \log (2q)$$$ to purposely troll people to believe that it is close to optimal (and I got trolled during contest to do disgusting optimizations, I mind solved up to 96 points, but ran out of time and only got 94 :V).

How to solve d1p3 ?

A critical error has occurred :-(

how did Japanese design these communication task perfectly to let me get unbelievably low score and simply can not notice the key to a great solution in 2+ hours?

How to solve d2p3? I passed it in n*log(1e9)*log(n) with some careful implementations and dirty optimizations, so I think someone will have a better solution.

Day 3 Problem 1 and 3 were really amazing. Spent a long time getting the 71-point subtask right and made stupid mistakes when rushing out problem 3 in the last minutes XD. Though I think the 71-point subtask of problem 1 is probably harder to think and implement than the full solution of problem 3, so I guess it deserves more points.

Are these problems available in Codeforces gym After the end of contest?

How can I achieve 50 points in Problem 2 Day 2? I've only managed to score 15 points so far and couldn't think of anything helpful to proceed further in the task.

Contest Day4 is Over

The contest Day4 (final day) is finished. The overall ranking is as follows. Thank you for your participation, and let's discuss the problem.

The overall ranking is as follows.

Will the problems be available for upsolving ?

if so then on which website ?

I've decided to share my solutions to the problems I've managed to fully solve. If you can add solutions to the rest of the problems/provide a better solution/ask a question, please, feel free to do so.

$$$\mathbf{Day\ 1.\ Problem\ A}$$$

I'll begin with a little transformation of the statement — instead of adding $$$1$$$ or $$$D$$$, I will subtract from the numbers and aim to achieve subarrays of zeroes. My first observation was that one's goal should be to use operation $$$A$$$ to sort the numbers in the queried range and then continue with operation $$$B$$$, as you can achieve any sorted sequence with it. We will answer the queries offline. If we are willing to answer the queries ending on some position $$$r$$$, we should seek to find the optimal usage of operations to sort the sequence for $$$1$$$ to $$$pos$$$, as then if $$$b_i$$$ is the number of usages of operation $$$A$$$ on $$$c_i$$$, the answer for the query from $$$l$$$ to $$$r$$$ will be $$$\sum_{i=l}^r b_i$$$. This is true because adding a number to the left of an interval will only result in a potential addition of operation $$$A$$$-s to it. Imagine we've found $$$b_i$$$ for some $$$r-1$$$ and now we want to see how $$$b_i$$$-s change with the appendment of $$$c_r$$$. Let's denote the changed heights with $$$h_1, h_2, h_3, ..., h_{r-1}$$$. You can see, that after sorting, the sequence is split into blocks of "dominoes" — subarrays $$$[l,r]$$$, for which if you decrease $$$h_r$$$ by $$$D$$$, then $$$h_l, h_{l+1}, ..., h_{r-1}$$$ will also decrease by $$$D$$$, as if you push the last one domino, every other will fall as well. The blocks of dominoes are separated by "barriers" between the end $$$r_{prev}$$$ and the beginning $$$l_{next}$$$ of such blocks, which if broken will result in the merge of the two ranges. Each of these barriers takes some number of $$$D$$$-s before breaking. So, now imagine the following two scenarios — $$$c_r \geq h_{r-1}$$$ and $$$c_r < h_{r-1}$$$. If $$$c_r \geq h_{r-1}$$$, then it's easy — $$$h_r = c_r$$$ and only possibly add a barrier between $$$r-1$$$ and $$$r$$$. The other case is much more interesting, as you then must decrease the height of $$$c_r$$$. Let $$$x$$$ be the required number of times you need to perform operation $$$A$$$ on $$$c_r$$$. Then, every element in the domino-range of $$$r-1$$$ will each decrease by $$$x \times D$$$. Then, when you meet the barrier between the current and previous range, you should check whether you should remove the barrier and decrease $$$x$$$, or stop the procedure. Let's say that you need to decrease $$$h_{l_{next}}$$$ by $$$y \times D$$$ in order to merge the ranges. If $$$x \geq y$$$, then every element in the previous range should be decreased by $$$(x-y) \times D$$$ units. Then you repeat the procedure until you run out of "decreases" or of barriers. If implemented with the correct data structure for range updates, this algorithm will be fast, as with every addition of an element, you add at most $$$1$$$ barrier, remove some number of barriers, then stop at $$$1$$$ barrier. This will result in $$$O(N)$$$ amortized traversal of barriers. In order to implement the range updates, you can keep a segment tree with lazy propagation. The answer will be, as mentioned, the sum of $$$b_i$$$-s and the check whether an interval is valid is to see if $$$h_l \geq 0$$$. The final complexity is $$$O((N+Q)\ log_{\,2}\ N)$$$.

$$$\mathbf{Day\ 3.\ Problem\ B}$$$

As it gets messy very quickly, I will only mention the key ideas of my solution. Its main idea is to use a centroid decomposition of the tree and keep online updates. By keeping a centroid decomposition, our goal is to calculate the number of triplets in each centroid's subtree, whose path passes trough the current centroid. Let's denote $$$u$$$-s centroid subtree, where $$$u$$$ is root, by $$$T_u$$$. The "subtrees" in $$$T_u$$$ are the subtrees of the children of $$$u$$$ in $$$T_u$$$. The paths are split into the following categories:

$$$(1)$$$ Triplets, including the centroid

• If $$$f_{centroid} = 0$$$, their number is the count of paths of the type $$$1-2$$$ in each subtree.

• If $$$f_{centroid} = 1$$$, their number is the ways of choosing $$$0$$$ and $$$2$$$ from separate subtrees in $$$T_u$$$.

• If $$$f_{centroid} = 2$$$, their number is the count of paths of the type $$$1-0$$$ in each subtree.

$$$(2)$$$ Paths, not including the centroid

• $$$0-1-centroid-2$$$, equal to the number of ways of selecting paths of the type $$$1-0$$$ and $$$2$$$ from different subtrees.

• $$$0-centroid-1-2$$$, equal to the number of ways of selecting paths of the type $$$0$$$ and $$$1-2$$$ from different subtrees.

The whole solution is based on keeping the mentioned pairwise products in a sane way. You should be able to track down how an update is changing the count of $$$1-0$$$ and $$$1-2$$$ paths for every subtree. For every node, you keep in which subtree is situated for every of its parent centroids, and keep three Fenwicks on the dfs order for each $$$T_u$$$, one for $$$0$$$, $$$1$$$, and $$$2$$$ updates, which helps calculating the change in the count of triplets. Instead of keeping $$$3 \times N$$$ separate fenwicks, I glued them together for better memory and time management. With very careful implementation of $$$356$$$ lines, I managed to provide an $$$O(N\ log_{\,2}^{\,2} N)$$$ solution with a big constant, and it passed for $$$2.3$$$ seconds out of the provided $$$3 seconds$$$.

$$$\mathbf{Day\ 3.\ Problem\ C}$$$

The first thing I did was to solve the third subtask. It only requires to be able to determine whether you can reach a certain position or not. It could be solved by finding $$$[0,+\infty] \setminus [L_1, R_1] \setminus [L_2, R_2] \setminus [L_3, R_3]\ \setminus \ ... \setminus \ [L_N, R_N]$$$. Then, you sort the remaining intervals and keep a vector with the reachable positions. Imagine you have determined the reachable positions of the first $$$x-1$$$ intervals and now you seek to find the available positions of the $$$x$$$-th interval, which is $$$[l,r]$$$. If you can reach the $$$pos$$$-th position $$$(l \leq pos \leq r)$$$, then you can reach every position in the range $$$[pos + 1, r]$$$. Now, we need to find that position $$$pos$$$. As the intervals are uninteresecting, then we can't reach the interval $$$[l,r]$$$ by doing a simple step, so we need to find the farthest reachable position down, from which we can jump to the current interval. This can be done with a binary search, because what you really search for is the first interval, which intersects with $$$[l-D, r-D]$$$. To answer the queries you can do a binary search on the intervals of available positions. Now, after solving the third subtask, we can notice that the optimal path of all paths to a certain $$$X_j$$$ is one using the least or the most $$$D$$$-jumps possible. Finding the least amount of $$$D$$$-jumps to a certain position is easy, the count is equal to the minimum $$$D$$$-jumps to reach the interval as a whole, so if the jumps for every interval $$$i$$$ is $$$minJumps_i$$$, and the interval, which firstly intersects with $$$[l-D,r-D]$$$ is with index $$$parent$$$, then $$$minJumps_i = minJumps_{parent} + 1$$$. Now, the more interesting part is to count the path with the most $$$D$$$ jumps. I tried the following greedy strategy — if you want to find the path with the most $$$D$$$ jumps, which ends at position $$$X$$$, check whether position $$$X-D$$$ is reachable, and if it is, then jump to it. If it isn't, go to $$$X-1$$$. It passed the tests for the first subtask, so I decided to optimize it, hoping for the $$$O(NQ)$$$ subtask, by doing the following:

1) Have a memoization, so I don't end up calculating the same answer twice.

2) Instead of always checking whether $$$X-D$$$ is reachable, find the interval you're in and do all the jumps possible at once, so you stay in the interval.

3) If $$$X-D$$$ is outside the current interval, check if it's in another. If it is, directly jump to it.

4) Otherwise find the first interval, before $$$X-D$$$. Directly jump to its right border.

By doing the described optimizations, the solution passed for $$$100$$$ points. I haven't proved it yet, so if you could provide proof/antitest to it it wouldn't be left unappreciated. Still, I believe that the tests are strong enough to not allow such a solution to pass, if it has bad complexity.

$$$\mathbf{Day\ 4.\ Problem\ A}$$$

We can follow this given greedy strategy: for every query, catch the flight which arrives at the next destination the earliest. Then you can choose which flight you'll be taking first and then stick to the greedy. By doing this, you will score $$$14$$$ points.

Then, instead of doing this procedure over and over again, you can precalculate for every flight $$$i$$$ the transferring one $$$par_i$$$ from the next position, where $$$i$$$ and $$$par_i$$$ follow some kind of numeration. After doing this, you can build a tree, where the edges are between $$$par_i$$$ and $$$i$$$. Every edge has $$$2$$$ fixated costs — one when transferring and one when ending your jouyney with the current flight. Every path between $$$(l,r)$$$ can be broken down to $$$r-l-1$$$ flights of the first type and one of the second type. Now, every query is depicted as follows: for a set of nodes (the flights, coming from $$$l$$$), find the path with edge count $$$r-l$$$, which is with the lowest length. For the subtasks with $$$M_i \leq 5$$$, this can be implemented directly with binary lifting for a complexity of $$$O(N\ log_{\,2}\ N + Q\ M_i\ log_{\,2} \ N)$$$, but there is a better approach. Instead of using binary lifting, you can notice, that the set of the mentioned $$$l$$$-flights is all the nodes of a certain depth $$$x$$$ in the tree, and all the destination nodes ($$$r-1$$$-flights) are at another depth $$$y$$$. You answer the aforementioned queries offline by doing a dfs traversal of the tree, writing down the parents at all depths, and when reaching a node with the dfs, you can access all the parents you want with $$$O(1)$$$ complexity. This will remove the $$$log$$$ from the complexity, giving you $$$O(N\ log_{\,2}\ N + QM_i)$$$, still giving you $$$54$$$ points.

Now, the only thing what remains is what with do with big $$$M_i$$$-s. Let's split the $$$l$$$-s into two types — big and small. The small $$$l$$$-s will be with $$$M_i \leq \sqrt{\sum M_i}$$$ and the big ones will be with $$$M_i > \sqrt{\sum M_i}$$$. We can answer the queries with the small $$$M_i$$$-s for a complexity of $$$O(N\ log_{\,2}\ N + Q \sqrt{\sum M_i})$$$, which is fast enough. The only thing what remains is to find a way to answer all the queries for the big $$$M_i$$$-s. One can notice, that there will be at most $$$O(\sqrt{\sum M_i})$$$ big $$$M_i$$$-s, and if we answer the queries for a big $$$M_i$$$ with a complexity of $$$O(N+Q)$$$, our solution would be finished. For doing this, we can do a dfs, similar to the one mentioned before, as we keep the best children at the depth of $$$l$$$-s flights for every node and chkmin the answer for it's $$$r$$$. We now have a solution with complexity $$$O(N\ log_{\,2}\ N + Q \sqrt{\sum M_i})$$$, which passes for $$$100$$$ points.

$$$\mathbf{Closing\ remarks}$$$

This analysis of mine isn't meant to be professional and I'm sure I've made mistakes in it. I hope it still is useful for solving the tasks. I very much hope to receive as comments for the rest of the tasks. Also, If you have any questions, again, feel free to ask :). And also, sorry if my English isn't the best, but I think it's understandable enough :).

JOI Spring Camp is certainly a great contest series in terms of its OI-style format, problem quality, difficulty, and the total length of 20 hours. I always solved most camp problems at some point in the year (usually during our national IOI camp training), but I could never participate in all seriousness. This year (right after participating in Potyczki Algorytmiczne 2024, another great contest spanning six days), I reserved my 10 pm to 3 am time to focus solely on virtual participation. It was a rough ride (I still suffer from headaches from 5 am sleep), but I had a lot of fun; thank you as always!

Here are my very honest impressions of each problem:

My ranking for the past 13 years of JOISC: 2017 > 2023 > 2020 > 2014 > 2012 > 2022 > 2019 > 2016 > 2015 > 2021 > 2024 > 2013 > 2018. I think this year was slightly less than a "great" contest, but still an interesting problemset anyway.

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.

When will you upload test data?

When will test data be published? Usually it is published within a week and problems are also then added to atcoder/oj.uz for upsolving.

You can solve all problems here: https://oj.uz/problems/source/647

Contest Data

We updated the contest page of JOI Spring Camp. Test Data, Problem Statement & Sample Solutions are added.

• https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/index.html

We are very sorry for late upload. All of the responsibility are belong to us.