Hello everyone!

JOI Open Contest 2024 will be held from Sunday, June 16, 04:00 UTC to Monday, June 17, 04:00 UTC.

The duration of the contest is **5 hours**, but you can start any time in the 24-hour window. Note that if you start competing after 23:00 UTC, the contest automatically ends at 04:00 UTC and you cannot compete 5 full hours. For example, if you start competing at 03:45 UTC, the contest will be shortened to 15 minutes.

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

- Number of Tasks:
**3 Tasks** - Max Score for Each task:
**100pts** - 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 will be announced 30 minutes before the contest starting time. 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.

Saturday is June 15th, right? The link says so, indicating the start day is actually Sunday.

Revised.

HYPE!

i think will be hard contest because its 3 tasks on 5 hours

3 tasks on 5 hours it's standard for IOI like contests

Wait, didn't it say the contest was on Saturday?

Thanks for a great contest!

How to solve the third problem ?

You can find the solutions to all the problems at the contest page

It seems they have a deterministic solution. I, however, have a non-deterministic solution which I still find interesting and would like to share:

RandomThe query answers the number of cycles of the given p composed with the inverse of the answer.

Generate random permutations until you get one that has like $$$2$$$ cycles. Futher swap random values until you obtain a single cycle. We now strive to break the cycle in unitary pieces, which actually means we found the permutation. For that, we can take another random pair and swap them, meaning we are breaking the current cycle into two pieces. We now have to identify those pieces, so a scan among the elements of the cycle is necessary.

This is very similar (if not identical) to the quicksort procedure. Given the (I assume) not adaptive manner of the grader, this has around $$$O(n*logn)$$$ queries. Problem is, given $$$log$$$, for a random pair, has its base equal more towards $$$3/2$$$ rather that $$$2$$$. This will not pass.

The trick is as follows: take $$$~6$$$ elements. Perform swaps among them until they are all in separate cycles. We now have the liberty to rearrange cycles in a manner that is beneficial to us, i.e., if we chain these cycles back together, taking the representative of the $$$1$$$-st cycle and the $$$4$$$-th cycle, we now have a random pair that divides the cycle more closely to two halves. This fixes the constant enough to pass (Locally, my code takes around $$$4800$$$ queries on average to solve).

why

I forgot the intended solution.

bound of 5000 queries kindly suggests some O(N log N) queries solutions. Let's think of one such

First thought is binary search, but it's not clear how to apply it here, so we'll return to it later.

Recall what is the smallest number of swapt to "sort" the permutation? It is equal to

`N - number of components in graph (i -> p[i])`

. We don't have to sort the permutation, but we can actually create a permutation of indices and sort it, so the problem stays same.Described above is called decomposing permutation in cycles, and it has the next property: if we swap two elements that belong to same component, number of components increases by 1; otherwise it decreases by 1. Respectively after any swap we can track whether those two elements belonged to same component (and respectively this "swap" should be kept) or not.

O(n^2) queries solution would be: for each j from 2 to N, try to swap it with each 1<=i<j and see whether it improves the cost or not. If it does, swap it and proceed with next j.

Obvious way to optimize it is binary search. Let's see how to apply it: if we could check with 1 query whether one of first X indices belongs to same component as index J, we'd be able to find the index we have to swap j with in log(n) queries.

Take a look at swap process — it not only changes the number of components, but splits one component in two or merges two in one. So actually we can recreate described above: "merge" first X indices into one component and check whether swapping J with any increases number of components. If it does, the index we search for lies there. Merging them would simply be cyclically shifting them to left or right. After finding the required index, swap it with j in your code and proceed to j+1. Note that it works since at any step, all of first (j-1) indices belong to different components (thanks to that swap).

Bonus: it actually solves problem in under 4000 queries =)

Its funny to see you guys are still "upset" regarding the venue choices :P. Story of P2, I mean

This is my code for 2nd subtask in problem A:

SpoilerI don't think it should have passed. I think a test case with no | operations and a bunch of () can make it tle. Can you hack it?

It fails on [2]^[2]^....[2] (repeated 250000 times)

pretty sus how library appeared on POI 3 months ago with the exact same constraints...

I mean, the setting of the problem itself is not really that distinctive, so repeats of it might just be coincidental

oj.uz when will the tasks be uploaded to oj.uz?

next monday