Hello, everyone!

Japanese Olympiad in Informatics (JOI) Spring Training 2024 will be held from March 21 to March 24. There are **4 days** in the contest.

- Day 1: March 21, 02:00 GMT — March 21, 24:00 GMT
- Day 2: March 22, 02:00 GMT — March 22, 24:00 GMT
- Day 3: March 23, 02:00 GMT — March 23, 24:00 GMT
- Day 4: March 24, 02:00 GMT — March 24, 24:00 GMT

The duration of the contest is **5 hours**, but you can start any time in 22-hour window. Note that if you start competing after 19:00 GMT, the contest ends at 24:00 GMT and you cannot compete 5 full hours. For example, if you start competing at 21:00 GMT, the contest will be shortened to 3 hours.

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

- Number of problems for each contest:
**3-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 task (e.g. output-only task, communication task) like IOI

Note that from this year, you can submit with C++20.

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

We welcome all participants. Good luck and have fun!

**UPD1:** The contest will start in 10 hours.

**UPD2:** Contest Day1 is started.

**UPD3:** Contest Day1 is finished. Now you can discuss Day1 problems.

**UPD4:** Due to technical issue, the contest Day2 will be delayed by about 1 hour.

**UPD5:** Contest Day2 is started.

**UPD6:** Contest Day2 is finished. Now you can discuss Day2 problems.

**UPD7:** Contest Day3 is started.

**UPD8:** Contest Day3 is finished. Now you can discuss Day3 problems.

**UPD9:** Contest Day4 is started.

**UPD10:** Contest Day4 is finished and now the entire series of contests is ended. Thank you for your participation.

hello!

Why can't I register for the competition?

Read the blog please.

thanks

there you can register 10 minutes before the start of the contest

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 ?

As far as I know it's not comparable with a Codeforces round, it's more like a contest with 3-4 3000ish problems

I believe that not all problems in the contest are 3000ish. Last year there were several problems that might be easy enough for solving (Currencies, Council, Tourism, Bitaro's travel) (you can also throw in Passport and Conveyor Belt). But yeah, focus on solving the subtasks might be a better strategy.

When will the analysis mode be opened?

After the 4-day contest ends.

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 Q=1Aoi only needs to tell Bitaro which hidden roads are used in any shortest path using $$$k$$$ bits. Bitaro needs to figure out how these hidden roads are arranged in a line. At each step, try to extend the path using the shortest distance to any unused road.

1363 solutionFor each hidden road, we label it with $$$0$$$ to $$$q$$$ depending on the first query that the hidden road is used. Because given some subset of the shortest path tree, we only need to "grow" another branch for the new query, so we only need to tell Bitaro which edges to attempt grow.

We will also need to tell Bitaro which hidden path from the existing shortest path tree he should grow this branch from, so this takes additional $$$log(k)$$$ bits per query.

As for encoding $$$17$$$-bit numbers well, note that $$$17^{11} < 2^{45}$$$.

In total, you use $$$(27 \cdot 45 + 13) + 15 \cdot 9 = 1363$$$ queries.

96 point solution (for reference)Send over a tree of $$$32$$$ vertices with $$$16$$$ leaves. This is the virtual tree version of the shortest path tree with each leaf describing the path needed for some query. For each hidden path, you will label it from $$$0$$$ to $$$31$$$, with $$$0$$$ to $$$30$$$ describing which edge of the virtual tree its being used in and $$$31$$$ reserved for unused edges.

Sending over the tree takes $$$60$$$ bits by sending the pre and post order traversal of the tree. Specific, append $$$\mathtt{0}$$$ when entering a vertex and $$$\mathtt{1}$$$ when leaving a vertex. You save $$$4$$$ bits since the first $$$2$$$ characters are $$$\mathtt{0}$$$ and the last $$$2$$$ characters are $$$\mathtt{1}$$$.

Then we need to send a permutation of length $$$16$$$ to match the leaves to queries. Actually, you can make the leftmost leaf be the first query, so that you send a permutation of length $$$15$$$. This requires sending $$$log(15!) \leq 41$$$ bits.

In total, you send $$$300 \cdot 5 + 60 + 41 = 1601$$$ bits. Your score will be $$$96.06$$$. If you used one more bit, your score will round down to $$$95$$$.

Note that you can squeeze $$$1$$$ more bit from sending the tree due to parity. Can we squeeze more bits there? It seems likely

Nice approach! I believe it is possible to optimize the 1500+? solution to 100 points though by sending the compressed tree more efficiently

How to solve d1p3 ?

A critical error has occurred :-(

I have the same problem :-(

Does someone know why this might be happening? It seems to work when I use a VPN

It is probably because of an IP ban. It seems to work with mobile data/hotspot

Probably my result on Day 1 was too suspicious :D

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?

Agreed, I couldn't think of anything helpful at these communication tasks :(

Being good isnt an excuse to not follow the rules. Kindly do not discuss about the problems. You spoiled atleast 2 things about the contest in this comment.

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.

After the binary search, each element in $$$a$$$ makes it impossible to choose a position within an interval as a starting point. The process of labelling these intervals that cannot be chosen can easily be done in $$$O(n)$$$ time, and the process of finding these intervals can be done in $$$O(n)$$$ time using many monotonically moving pointers.

Can you explain in more detail? I don’t understand what "each element in a makes it impossible to choose a position within an interval as a starting point" means.

First, when we want to match two arrays $$$A$$$ and $$$B$$$, the best strategy is to match the $$$i$$$-th largest element in $$$A$$$ with the $$$i$$$-th largest element in $$$B$$$.

Wlog assume that $$$b$$$ forms an interval when matching $$$a$$$, and let's focus only on the starting point $$$l$$$ of this interval $$$[l,l+n)$$$.

Consider an element $$$a_i\ (n+1\le i\le 2n)$$$, when this element is included in the interval (that means $$$l+n>i$$$), we've known that $$$a_{n+1}>a_{n+2}>\dots>a_{i-1}>a_i$$$, and we will have $$$\min(c,n-l+1)$$$ elements in $$$a_l,a_{l+1},\dots,a_n$$$ to be greater than $$$a_i$$$, where $$$c$$$ is the total number of elements in $$$a_1,a_2,\dots,a_n$$$ which is greater than $$$a_i$$$. $$$c$$$ can be found in linear time.

We can know that we want to have $$$[L,R]$$$ elements in the interval to be greater than $$$a_i$$$, which $$$L,R$$$ can be found in linear time. So when $$$l+n>i$$$, $$$l$$$ should satisfy $$$i-n-1+\min(c,n-l+1)\in [L,R]$$$, and this restriction means that when $$$l$$$ is in some ($$$O(1)$$$) intervals, we cannot choose that $$$l$$$.

The rest part of $$$a$$$ can be treated in similar ways, resulting to 4 similar processes.

Nice 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.

How to get 71-point subtask of Day 3 Problem 1?

The idea is to think of the ones $$$>x$$$ as $$$1$$$ and the ones $$$<x$$$ as $$$-1$$$ when the given query is $$$x$$$. Then solve the problem for three values. Here some careful classifications are required. I have written an explanation of the whole solution in Chinese right here, but it's too much work translating it in English.

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

No, but they will certainly be available in oj.uz

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 OverThe 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.

300300300300300300300300300300300300300map300300Is Japanese IOI team selected?

Will the problems be available for upsolving ?

if so then on which website ?

We can upsolve problems in the Contest Site, which is supposed to be on Analysis Mode now. It will end 7 days after the contest (if not started yet, it will start soon).

Also, we can upsolve past JOI problems in AtCoder. This year's one is not prepared yet, but I think that the judge will be prepared within some weeks.

Is official solution code available?

I think it will be prepared soon (in a few days or a week).

Like all solutions and test data in JOI Spring Camp 2023 can be obtained in the link https://www2.ioi-jp.org/camp/2023/2023-sp-tasks/index.html, a new page with the link just replacing 2023 to 2024 will soon be created.

Any updates on this?

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 :).

Really depends on what "Have a memoization" means, but if I am not mistaken, it seems what you are effectively doing is precalculating the maximum jumps for each right end, and seeing to which of those the current query rounds down to? Or on second thought, I feel that a testcase where the availible segments are something akin to $$$[i * (D + 1), i * (D + 1) + D - 1]$$$ might fail your code (because memoization might fail on such cases where you succesively apply step 3)-- could you link your code somewhere and maybe I can figure out some counter-testcase :))?

Maybe a more «sure» solution which looks to be the same?If it is of any value, I would like to add that another solution for which the answer may look more better defined prior to any query is to do the exact procedure which you've mentioned, but in reverse (starting from zero and succesively adding D, then rounding to the next left end; as much as there can always be formed succesive buckets of lenght for which all the positions have the same values, and these would normally be every $$$[i * D, i * D - 1]$$$, if it werent for some "further away" reachable segments, case in which you have to move all the succesive "answer segments" to the right to align with the left end of said "further" segment).

Well, yeah, if it works, it would be because the solution mostly relies on the precalced answers for the right ends. However, I think a test in the form of blocks of $$$D$$$ free spaces and $$$1$$$ occupied after them should get me a TL because I will be randomly traversing through the tower. Still, here is my code: https://pastebin.com/mnmePxZc

And yeah, I think your idea should be correct, probably by doing amortized stuff with data structures, which could even be with a set.

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:

Day 1fish3 (★★★): This was a standard problem. One can reduce it to range prefix maximum summation—I did that a lot before, and it's not like you should know it beforehand to solve this.

spy3 (★★★★): It was pretty nice to come up with the solution with 5K + f(Q) queries, which was enough to get a relatively high score (8x ish). On the other hand — optimizing f(Q) wasn't so nice because the implementation goes a long way even though the idea is rather trivial. JOI recently had a lot of "constant optimize to the end" types of problems, and it feels like a mixed bag to me. Most of them require very, very heavy implementation, but they are not just mechanical; they are also pretty hard to come up with. This time, I thought it was more like "just mechanical" type, but I also can see how the author wanted to require it because you can, and also, it isn't too monstrous to code. Apparently, some people above cooked up pretty interesting shenanigans, too. So, it's truly a mixed bag, but the overall idea is cute, and I would say I enjoyed this problem.

ski2 (★★★★): This problem was pretty tricky for me. The overall idea isn't too hard at the end, but it took me a lot of time to come up with it. Although the implementation was short, I thought my idea was hard to implement. It was a nice challenge in the end.

Day 2Day 3Day 4My 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.

Ok, here's my implementation for everything besides tricolor and collection: Link

Btw, seems like Mr. JOI has a sneaky plot for invading the KOI plateau...

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.

Let's wait for https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/index.html

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

Why I couldn't upload day4 tennis (now uploaded)I don't have a good idea to write a checker for Day4 tennis better than $$$O(N^3/64)$$$ time, and it is too slow. I believe there should be a better checker since it is a tournament, but I don't have time to actually solve this problem

Writing the checker for this problem is really easy assuming you've solved it, but in case you don't want to be spoiled I'll hide it below:

small tennis spoilerLet the outdegree of vertex $$$i$$$ be $$$d_i$$$. Then the number of trilemmas is $$$\binom{n}{3} - \sum_i \binom{d_i}{2}$$$.

Thanks, done

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

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