E869120's blog

By E869120, 3 years ago, In English

Hello, everyone!

Japanese Olympiad in Informatics (JOI) Spring Camp 2022 will be held from March 20 to March 23. There are 4 days in this contest.

The duration of the contest is 5 hours. You can choose start time from specified range freely. Please note that if you start competing after 19:00 GMT, the contest ends at 24:00 GMT (and it means the duration is less than 5 hours). For example, if you start competing at 21:00 GMT, the duration is 3 hours.

The contest information is as follows. Details are available in contest page.

  • Number of problems in each day: 3 or 4 problems
  • Max score for each task: 100 points
  • Style: IOI-Style (There may be some partial scores)
  • Problem statement: Japanese & English
  • There may be some unusual tasks (e.g. output-only task, communication task, reactive task) like IOI

The registration page and live scoreboard will be announced 10 minutes before the contest.

We welcome all participants. Good luck and have fun!

Tags joi, ioi
  • Vote: I like it
  • +347
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +77 Vote: I do not like it

Commented so this would remain in recent actions

»
3 years ago, # |
  Vote: I like it +64 Vote: I do not like it

Now, the contest Day1 starts!

You can choose start time from March 20, 02:00 GMT — 24:00 GMT freely. Let's participate!

»
3 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Commented so this would remain in recent actions

»
3 years ago, # |
  Vote: I like it +55 Vote: I do not like it

Seems the Day 1 contest has been finished.

Let's discuss the tasks here. How to solve Task 2 (Kyoto)?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The edges in the answer must be on the convex hull

  • »
    »
    3 years ago, # ^ |
    Rev. 6   Vote: I like it +113 Vote: I do not like it

    There is a solution which does not use convex hull, so I will introduce that.

    Subtask 1:
    Dynamic programming. Time complexity is $$$O(HW)$$$.

    Subtask 2:
    The horizontal road which satisfies both $$$A_i \geq \min(A_1, A_2, \dots, A_{i-1})$$$ and $$$A_i \geq \min(A_{i+1}, A_{i+2}, \dots, A_N)$$$ will not be used for the optimal route. Same for vertical roads. For $$$A_i, B_j \leq 1000$$$, almost of the road will be eliminated, so this problem can be solved by DP of $$$2000 \times 2000$$$ grid.

    Full Score:
    Suppose the case of which the $$$i$$$-th northernmost road is $$$x = x_i$$$ and the speed is $$$A_i$$$, and the $$$j$$$-th westernmost road is $$$y = y_j$$$ and the speed is $$$B_j$$$. (In this problem, $$$x_i = i$$$ and $$$y_j = j$$$ for each $$$i, j$$$). First, consider the $$$H = 2$$$ and $$$W = 2$$$ case.

    • If we pass the route $$$(1, 1) \to (1, 2) \to (2, 2)$$$, the cost is $$$A_1 (y_2 - y_1) + B_2 (x_2 - x_1)$$$.
    • If we pass the route $$$(1, 1) \to (2, 1) \to (2, 2)$$$, the cost is $$$B_1 (x_2 - x_1) + A_2 (y_2 - y_1)$$$.

    If you transform this formula, you will know that the condition of which route is better will be equivalent to which of $$$\frac{A_2 - A_1}{x_2 - x_1}$$$ and $$$\frac{B_2 - B_1}{y_2 - y_1}$$$ is larger. If the former route is better, it is not wrong to say that it is "impossible" turn left at $$$(2, 1)$$$, and if the latter route is better, it is not wrong to say that it is "impossible" to turn right at $$$(1, 2)$$$.

    Consider the general case. We will first calculate $$$\frac{A_{i+1} - A_i}{x_{i+1} - x_i}$$$ and $$$\frac{B_{j+1} - B_j}{y_{j+1} - y_j}$$$ for all $$$i, j$$$. There are $$$H+W-2$$$ values, but suppose that the largest among them is $$$\frac{A_{k+1} - A_k}{x_{k+1} - x_k}$$$. In this case, if we apply the condition stated above for all $$$W+1$$$ squares sandwiched by roads $$$x = x_k$$$ and $$$x = x_{k+1}$$$, it can be said that we cannot turn left at $$$(k+1, 1), \dots, (k+1, W-1)$$$, which means that road $$$x = x_{k+1}$$$ will not be used. This will eliminate one road. (Note that some part of the road will remain if $$$k = H-1$$$.)

    If we eliminate all roads by repeating this procedure, only one path from $$$(1, 1)$$$ and $$$(H, W)$$$ will be there — which is, the optimal route. We can simulate this procedure by using std::set or something else, and we can find the optimal route in $$$O((H+W) \log (H+W))$$$.

»
3 years ago, # |
Rev. 2   Vote: I like it +114 Vote: I do not like it

[Day 1] My solution for misspelling — AC (100 pts):

Solution
Code

Also, this is my first attempt at writing an editorial (at least publicly), so any feedback is very much welcome!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks, your solution is easier to understand than the official one :))

»
3 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Contest Day1 is Over

The contest Day1 is finished. Thank you for your participation.
Day2 will start 2 hours later (March 21, 02:00 GMT — 24:00 GMT), so good luck and have fun!

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Is there any way to see the day 1 problems? Doesn't seem to be on the contest page for me (only shows countdown for day 2).

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I believe you can only see the problems if you participate in the contest and download the pdfs.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Here are the statements for all four contests.

»
3 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Contest Day2 is Over

The contest Day2 is finished. Thank you for your participation, and now you can discuss the problem.
Day3 will start 2 hours later (March 22, 02:00 GMT — 24:00 GMT), so good luck and have fun!

»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it

How to make SetID() in day2 task2 useful?

»
3 years ago, # |
Rev. 13   Vote: I like it +72 Vote: I do not like it

Here is my 100 points solution for Copy and Paste 3 from Day 2:

Spoiler
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Where can we upsolve the problems from previous days?

»
3 years ago, # |
  Vote: I like it +77 Vote: I do not like it

How to solve day2 p2?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +61 Vote: I do not like it
    96 points

    How to get 100 points?

»
3 years ago, # |
Rev. 2   Vote: I like it +84 Vote: I do not like it

Is the judging server broken? The submission I sent 25 minutes ago is still compiling...

UPD: seems the CMS server is down :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think so too

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    There had been a server problem during Contest Day 3, which prevented submissions from being judged. The problem is likely happened since 3 AM in Japan. Sorry for the inconvenience!

    The server problem is now solved, so I think that the Contest Day 4 will start on time.

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I somehow didn't participate in first two days, but came excited to participate in the third day. 90% of my enthusiasm and motivation has gone away once I read the tree problem. Remaining 10% has gone away after I read the ants problem. Then I read the device problem and it looked nice, but the blow from the tree one was too severe

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why is that?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -49 Vote: I do not like it

      This is not 2014, centroid decomposition is not cool for the sake of itself. This is literally a tutorial problem for quite a complicated technique and JOI is not supposed to be a an educational round. Once on final stage of POI we had a problem whose whole statement was literally "write NTT" and this is similar approach

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it +22 Vote: I do not like it

        I believe there is a solution for the tree problem (sprinkler) without using centroid decomposition.

        Source: I solved it in contest without using centroid decomposition

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        In fact, it turns out that the editorial solution for "sprinkler" is not centroid decomposition, but an $$$O(ND)$$$ solution with simple implementation!

        The centroid decomposition would pass subtask 5, but it's likely to get TLE for full score. The main reason is because the "inverse" is not defined for composite mod. Although it is possible to factorize $$$M$$$ and solve for each prime factor, it is still time-consuming.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
          Rev. 2   Vote: I like it -56 Vote: I do not like it

          Oh, so distances were <=40 >_>...? Great. Such crucial and very unusual constraint stated among the sea of obvious constraints only on the 3rd page (especially if the problem is solvable in the general setting). Such crucial constraint should definitely be stated in a much more visible way. I don't blame myself that much for not reading carefully the remaining 5 pages after I read the first one :p

          Device made me similarly annoyed as it stated that we can use 2000 operations only to change its mind on the freaking fifth page that this is just a very technical constraint and in fact you can use at most 140 for the full score.

          Also, it is true that the fact that multiplying mod sth non-prime has no inverse operation and that is a serious problem for the standard way of doing cent-decomp. However it can be done in the same complexity, so that you do not need inverse operation if you use the "1/3-2/3" approach that finds a centroid and divides its subtrees into two groups such that each of them has >=n/3 vertices. But I did not have that one in my library xd

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +25 Vote: I do not like it

            1) I don't remember JOI being particularly known for hiding unusual constraints without telling you in the statement, so this might just be an error that made it past quality assurance.

            2) From my exprience, writing the limit for getting any points at all in the statement, then having detailed limits breakdown in the Scoring section is common practice for interactive/communication problems in OI contests.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

              So "hiding" unusual constraints without telling you in the statement is low-quality? I disagree with that.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                Rev. 3   Vote: I like it 0 Vote: I do not like it

                Oof. I shouldn't have been so hasty when writing my opinion out.

                I don't think that putting unusual constraints in the Constraints section and not in the statment upfront is wrong. It's where constraints should go, after all.

                But I have experienced cases where problemsetters intentionally hid unusual constraints in that section, to lower the chance of contestants noticing it and artificially increasing the difficulty of the problem ( cough ICPC Vietnam National 2017 cough), and so I have built a personal distaste for problems like that.

                Sorry for bothering you by saying that such kind of problemsetting is outright low-quality without thinking it through.

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Contest Day3 is Over

The contest Day3 is finished. Thank you for your participation, and now you can discuss the problem.
Day4 will start 2 hours later (March 23, 02:00 GMT — 24:00 GMT), so good luck and have fun!

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Totally defeated by the Day3 problems:(

By the way, is there an easy way to get a high score in problem device2?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    The 80 points solution imo:

    String A: "0101010101010101" (90 times "01") String B: for each bit of N (from 0 to 59), if that bit is 0 then you add three zeros to B, else you add three ones.

    The processing part is quite long, and since you are LGM, I will safely assume that you can make it out for yourself.

    (P/s: I don't know if this solution is easy or not)

  • »
    »
    3 years ago, # ^ |
    Rev. 8   Vote: I like it +59 Vote: I do not like it

    [Day 3] My solution for device2 — 80 pts:

    Solution
    Anna
    Bruno

    Would be interested in hearing the full solution!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Hints for 100 pts
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like it

        I'm sorry, but this hint only needs 0 bit to communicate

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Brilliant!Thanks to both of you!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Any other different solution? Very interested

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +58 Vote: I do not like it

    My 96-point solution for device2 , which got the highest points among all the solutions submitted in JOISC contest 3.

    In my opinion, this is just a extension of the 80-point solution which have been mentioned for many times.

    But I don't think there's an easy way to get a full solution by improving this algorithm.

    Solution
    Anna.cpp
    Bruno.cpp

    Sorry for my poor English.

    Look forward to a full solution.

»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to prevent the $$$\log$$$ factor in day 3 problem 2? I had a $$$O(Q*40* \log N)$$$ solution and failed to optimize it for three hours. :(

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    You can specify that the length of the path is exactly 40 or 39 by continuing moving up at the lca.

    solution
  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    I don't know what your solution is like, here is my solution.

    Consider maintaining $$$mul_{i,j}$$$, which means all the childs of node $$$i$$$ with depth $$$j$$$ should be multiplied by $$$mul_{i,j}$$$. It's easy to see the answer to node $$$i$$$ is $$$h_i\times \sum\limits_{j=0}^{maxd=40} mul_{fa_{i,j},j}$$$.($$$fa_{i,j}$$$ is the $$$j$$$-th ancestor of node $$$i$$$.)

    As for modifies(i,d,w), jump to $$$fa_{i,d}$$$ and then process from up to down.

    In more detail, we multiply $$$mul_{fa_{i,d},0}$$$ by $$$w$$$ at first. Then, for $$$mul_{fa_{i,j},k}$$$, if $$$k>d-j$$$, then the children can't be reached. If $$$k<d-j-1$$$, then $$$fa_{i,j+1}$$$ has multipled it in $$$mul_{fa_{i,j+1},k-1}$$$, so it shouldn't be multiplied twice. Therefore, we can simply do $$$mul_{fa_{i,j},d-j}\leftarrow mul_{fa_{i,j},d-j}\times w,mul_{fa_{i,j},d-j-1}\leftarrow mul_{fa_{i,j},d-j-1}\times w$$$.

    Sample for modify(i,3,w) (picture not so clear)

    We can multiply $$$w$$$ to at most 2 mul tags for each node, so time complexity is $$$O(d)$$$ per modify.

    Special case: $$$fa_{i,d}$$$ may be not exist, then just multiply the other tags to the root of the tree.

    Sample Code

    btw sorry for my poor English.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thank you, I understand now.

      I binary searched on the range of nodes that will be updated for each depth, and updated the range using a segment tree. Guess I've unnecessarily overcomplicated it, sad :(

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you explain in more detail how you handle updates?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Updated my comment so it is now clearer.

»
3 years ago, # |
  Vote: I like it +131 Vote: I do not like it

I spent most of my time doing sugar, so I automatically liked it :v

Solution for sugar
  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    how can we prove that matching with size $$$|A|-max_{X\subseteq A}(|X|-|N(X)|)$$$ is always achieveble ?

»
3 years ago, # |
Rev. 2   Vote: I like it +92 Vote: I do not like it

Contest Day4 is Over

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

Place Username Day1 Day2 Day3 Day4 Total
1st djq_cpp 300 281 280 300 1161
2nd hehezhou 300 275 280 300 1155
3rd LJC00118 300 268 280 300 1148
4th wasa855 300 276 212 300 1088
5th 4182_543_731 300 276 210 300 1086
6th xyr2005 240 272 280 277 1069
7th qazswedx 300 200 263 300 1063
8th Gracey 240 200 283 300 1020
9th xtqqwq 300 287 210 208 1005
10th 127 200 277 205 300 982
»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

test data when

»
3 years ago, # |
  Vote: I like it +50 Vote: I do not like it

Uploaded codes to the problem which I have full solution here

»
3 years ago, # |
Rev. 4   Vote: I like it +23 Vote: I do not like it

It was so bizarre when I got 100 % on dango3 with a random algorithm ...

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In fact, as long as the data is randomly ordered before processing, then it is random for all cases.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I also use the random algorithm and passed... but still don't know how it works...

      Then what's the expectation of number of queries?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used random as well and I think it is impossible to counter that approach. At least the way I did it. If checker is not adaptive then my solution clearly works, but even if it is then I think it maybe is provable it is impossible to counter it.

    I drew random 2000 dangos and kept fingers crossed I get nonzero answer. Then I take them out one by one if removing a particular dango doesn't decrease query answer to 0 and at the end I remain with a proper stick.

    Was intended solution different? It was weird cause at no point I had an idea that would pass for 22 points. That random approach jumps directly from 7 to 1000

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      The problem can be solved in $$$n*m*\lceil log_2(m) \rceil$$$ queries as follows:

      Solution
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Cool one, thanks. I wonder what's the expected number of queries that my approach has. There is some chance it could be better, but it's rather hard to optimize and analyze properly, since that 2000 was fairly arbitrary and would need improvements for general case

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I got 22 points at first because I just shuffled the index array at first but not after each Answer()...

»
3 years ago, # |
  Vote: I like it +47 Vote: I do not like it

When can we upsolve the problems in the CMS platform?

By the way,Thanks for the excellent problems.

»
3 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Analysis

The contest site is in analysis mode from March 24, 15:00 GMT to March 31, 15:00 GMT. You can upsolve all the problems!

»
3 years ago, # |
  Vote: I like it +54 Vote: I do not like it

I would be interested to hear the solution to fish eating problem

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +26 Vote: I do not like it

    Here's my solution: (it's a bit bizarre, but I've managed to inplement it during the contest and it passed anyhow :)

    Let's set $$$a_0 = a_{n+1} = \infty$$$. Consider those segments $$$[l, r]$$$ s.t. $$$ \sum_{i=l}^{r} a_i < \min (a_{l-1}, a_{r+1})$$$. One can prove that:

    • There exist only $$$O(n)$$$ such segments;

    • For any pair of segments, they either don't intersect or one is included in the other;

    • For any $$$i\in [1, n]$$$, there exist at most $$$O(\log A)$$$ segments including $$$i$$$.

    Let's try to maintain the set $$$S$$$ of valid segments during modifications. Consider a modification on $$$a_i$$$. Only segments that either include $$$i$$$ or use $$$i-1$$$/$$$i+1$$$ as its right/left endpoint will be affected. Let's store those segments on its endpoints (using std::set or std::vector), and by doing binary search on segment trees to quickly find valid segments, we can simply delete and rebuild those affected segments in a quite straightforward manner, yielding a time complexity of $$$O(\log A \log n)$$$ per modification.

    Consider a query $$$[l, r]$$$. Let's find the rightmost $$$i\in [l, r]$$$ s.t. $$$a_i > \sum_{k=l}^{i-1} a_k$$$, and the leftmost $$$j \in [l, r]$$$ s.t. $$$a_j > \sum_{k=j+1}^r a_k$$$. Fish $$$x$$$ can survive iff

    • $$$x \in [i, j]$$$;
    • There exists no segment (the aforementioned "segment") $$$[l', r']$$$ s.t. $$$[l', r'] \not= [i, j], [l', r']\in [i, j]$$$ and $$$x\in [l',r']$$$.

    It's not hard to find that, if for each $$$i$$$ we maintain an extra counter $$$cnt[i]$$$ which counts the number of segments including $$$i$$$, then all $$$x \in [i, j]$$$ whose $$$cnt[]$$$ reaches the minimum of $$$cnt[i...j]$$$ satisfy the conditions described above. Let's use a segment tree to range +1/-1 when a segment is inserted/erased from $$$S$$$ while maintaining the minimum and its number of existence. Therefore, after finding $$$i$$$ and $$$j$$$ using also binary search on segment trees, we can easily get the answer, thus solve the whole problem!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for solution. I had the first idea at the beginning, but could not improve. Didn't see that number of segments does not exceed O(N), and that they don't intersect. Very cool solution.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    It's just a little too complicated though. There exists a rather simple and straightforward solution. Basically, we just maintain $$$O(\log A)$$$ prefixes/suffixes on segment trees, and then try to speed up the process of node merging. Feel free to ask wasa855 for more details if anyone's intrested :)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +40 Vote: I do not like it

    First build a simple segment tree on the array, for each node in the segtree $$$[L,R]$$$, maintain each fish between $$$[L,R]$$$, the leftmost and the rightmost fish $$$(l,r)$$$ it can eat.

    Consider a valid candidate pair $$$(l,r)$$$ for a segtree node $$$[L,R]$$$. Firstly either $$$l=L$$$ or $$$r=R$$$ should hold. If $$$l=L$$$, then $$$\sum_{i=l}^r a_i<a_{r+1}$$$ or $$$r=R$$$, since prefix sum of $$$\sum_{i=l}^r a_i$$$ will multiply by 2 after added a new fish, there will only be $$$O(\log V)$$$ candidate pair. Then for each candidate pair, count how many begin fish will get it.

    To merge two segtree node, just use simple two-pointers.

    check my code here for details.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also check out my (long and shitty) code :)

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve the problem Jail in Day1?

I have tried some greedy methods,but it doesn't work.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it
    Jail
    • »
      »
      »
      3 years ago, # ^ |
      Rev. 8   Vote: I like it +38 Vote: I do not like it

      We can prove the lemma "if the solution exists, we can move prisoners directly one by one". The idea is "if there's a prisoner appearing in two different sections of moves, we can contract them".

      Proof of the Lemma
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thank you for the great contest. I really liked flights, team, sugar, fish2, reconstruction.

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

The competition summary of JOI 2022 Spring Camp is published! Now we can see (1) problem statement, (2) actual test data, (3) sample source codes, (4) Japanese editorials, (5) score distribution of onsite contest, in JOI website.
https://www.ioi-jp.org/camp/2022/2022-sp-tasks/index.html

The page is in Japanese, so feel free to read with translators if you want.

»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

You can submit all problems here: https://oj.uz/problems/source/595

For problem device2, currently, the riffle shuffle is only done pseudo-randomly, though the contest announcement said otherwise (i.e. it is not guaranteed that it's random). This is because the test data doesn't contain any information about how the shuffle should be done. The problem might be rejudged if we manage to find the correct shuffling method for each test.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In fact,problem reconstruction can be solved in $$$O(m\log m+Q)$$$ using the same solution of spanning tree with minimum variance.