Hello everyone!
JOI Open Contest 2022 will be held from Sunday, July 3, 04:00 UTC to Monday, July 4, 04:00 UTC. You can start any time and the duration is basically 5 hours. Note that the duration becomes shorter if you start after Sunday, July 3, 23:00 UTC, i.e. less than 5 hours before the contest ends.
There will be 3 tasks, and the maximum score for each task is 100 points. Since this is an IOI-style contest, there may be some subtasks. Each submitted source program must be written only in C++. Problem statements will be provided both in Japanese and in English. You can find more details in the contest page.
Past contests are also available in this page, and you can test your code in oj.uz website.
Good luck and have fun!
why is it trying to access my github
There was an issue that we need to authenticate with GitHub, but it is already solved.
We can correctly access the contest page and able to register now.
Reminder:
The contest will start in 10 minutes.
Now the registration page is open and we can participate in the contest.
I hope there will be wonderful problems like the previous joi spring camp contests !
Problem A is nice! How to solve C?
How to solve A?
Let $$$f(l,r)$$$ be the average number of interval $$$[l,r]$$$. For every interval length only two intervals are useful, which satisfy $$$f(l,r) \leq f(1,n) \leq f(l+1,r+1)$$$.
How do we compute the answer, using these useful intervals? And why are only these intervals useful?
upd: My solution is complicated because I missed a conclusion. The answer $$$[L,R]$$$ is valid iff for every interval length there exists $$$f(l,r) \in [L,R]$$$. But my conclution is still needed.. It may be easier to understand now. link(not mine,in chinese)
Could you please make it more specific?I still can not understand it.
C: For an edge $$$(x,y,w)$$$, if $$$dis(1,x)+w=dis(1,y)$$$ and $$$dis(x,n)=w+dis(y,n)$$$ call it useful. If we can pass any unuseful edge in our route, the answer is 1, and it's trivial to check.
If we only pass through useful edges, the answer is 1 iff we can pass an edge backwards. After drawing several cases, it is not hard to discover that we should just check if the useful edges form a Two-Terminal Series-Parallel Graph, where terminals are $$$1$$$ and $$$n$$$.
I almost solved the problem except for the last step of Two-Terminal Series-Parallel Graph. Is it ‘useless algorithm’ or can we solve it without the knowledge?
The name seems complexed, but the checking algorithm is actually very simple: if a vertex has exactly one incoming edge (from $$$x$$$) and exactly one outgoing edge (to $$$y$$$), remove the vertex and link an edge from $$$x$$$ to $$$y$$$. Keep simulating this process until only $$$1$$$ and $$$n$$$ are left.
I learned about the algorithm beforehand so I'm not sure, but it seems not impossible to come up with it independently (?)
I once thought about it but unfortunately feel it can't work, didn't realize multiple edges can be merged.. Thank you for reply.
For more details why it works (and how it seems reasonable to come up with it independently).
The reduction algorithm will leave you with a DAG with the following properties:
1: Unique source and sink nodes: 2: Each non source/sink node either has in-degree >= 2, or outdegree >= 2.
Then, if there are non source/sink nodes, then there exists a path from N to 1 that takes at least one edge backwards.
Proof by construction:
Consider a topological ordering f of the DAG (edge from x -> y implies f(x) > f(y))
By handshake lemma at least one node has in-degree >= 2
Let X be the node with in-degree >= 2 with f(X) maximised. Let A be the parent of X with the largest f(A), and B be the parent of X with the smallest f(B).
By definition of X, as f(B) > f(X) then B must have out-degree 2, and hence it has another child C != X. Hence clearly you can construct a path as follows:
Take any route from N -> A. Then take A -> X. Then take X -> B (our backwards edge. Then take B -> C, and then any path C -> 1.
The fact that B is the parent of X with the smallest f(B) is important to ensure that it is impossible for any path from C -> 1 to accidentally pass through X.
How to solve B. giraffes?
If the permutation $$$p$$$ if legal, one of $$$p_1$$$ and $$$p_n$$$ must be $$$1$$$ or $$$n$$$. Assume $$$p_n = n$$$, and the original permutation will be legal if and only if $$$p_1, p_2, \cdots, p_{n-1}$$$ is legal.
View the permutation $$$p$$$ as $$$n$$$ points $$$(i, p_i)$$$ on a plane. Then, we can easily write an $$$O(n^3)$$$ dp, each state representing the maximum number of unchanged points in a particular square on the plane.
Rewrite the dp as follow: Let $$$dp[i]$$$ represent the set of minimal squares in which there can be $$$i$$$ unchanged points. Then, for each $$$i$$$, we only care about those squares with one of its corner $$$= (j, p_j)$$$ for some $$$j$$$. As a result, we can use $$$dp[i][j][0(/1/2/3)]$$$ to represent the smallest size of a square such that 1) its top-left corner is $$$(j, p_j)$$$ 2) in it there are at least $$$i$$$ unchanged points.
If the transition is done through brute force, the complexity will be $$$O(tn^2)$$$ where $$$t$$$ is the maximum number of unchanged points overall (about $$$300$$$ when $$$n = 8000$$$). A bit of optimization, however, is enough to pass.
Here is my solution. Assume we're calculating $$$dp[i][j][0]$$$ for each $$$j$$$. For each line $$$x = k$$$ or $$$y = k$$$, we can preserve the squares of $$$dp[i-1]$$$ with an edge on this line. Note that $$$dp[i][j][0] > dp[i-1][j][0]$$$, so we can set $$$dp[i][j][0] = dp[i-1][j][0]$$$ and keep incrementing $$$dp[i][j][0]$$$ by one until the current square contains a square of $$$dp[i-1]$$$. Here, we only to check those squares with one edge on $$$x = j - dp[i][j][0]$$$ or $$$y = p_j - dp[i][j-1][0]$$$. The transition of $$$dp[i][j][1/2/3]$$$ can be done similarly, and the program runs in ~2.7s on my laptop.
There also exists an $$$O(tn \log n)$$$ solution which involves dividing the plane into 8 sections and handling 2D range queries with a sweepline & Fenwick tree.
In fact one can prove $$$t = \Theta(\sqrt{n})$$$, so the time complexity of your solution will be $$$O(n^{5/2})$$$ on average case. The solution which speeds up the DP with sweepline algorithm will run in $$$O(n^{3/2} \log n)$$$ time. I will share the reason of $$$t = \Theta(\sqrt{n})$$$ here (because you didn't mentioned about it).
Lemma 1. $$$t \leq$$$ (the length of LIS of $$$p_1, p_2, \dots, p_n$$$) + (the length of LDS of $$$p_1, p_2, \dots, p_n$$$).
Here, LIS means the longest increasing subsequence and the LDS means the longest decreasing subsequence. The reason is because, the "unchanged points" can always be decomposed into an increasing subsequence and a decreasing subsequence.
Lemma 2. The expected length of LIS for random permutation is $$$2\sqrt{n} + O(n^{1/6})$$$.
This is the result of Odlyzko & Rains (1998), which also states that the standard deviation is also $$$O(n^{1/6})$$$. However, even if you don't know the fact, we can prove the fact near to Lemma 2.
Lower Bound: Think about constructing the increasing subsequence in this way: for each $$$k$$$, if there are a value in range $$$[k\sqrt{n}, (k+1)\sqrt{n})$$$ in $$$p_{k\sqrt{n}}, \dots, p_{(k+1)\sqrt{n}-1}$$$, we pick one of them in the result sequence. The size of sequence will be:
Therefore, asymptotically, (the expected length of LIS) $$$\geq 0.632 \sqrt{n}$$$.
Upper Bound: Think about the increasing subsequence of length $$$k$$$. There are $$$\binom{n}{k}$$$ such subsequences, and the probability for them to be increased is $$$\frac{1}{k!}$$$ each. Therefore, the expected number of length-$$$k$$$ increasing subsequences will be:
This value will be equal to $1$ when $$$k = (e+o(1))\sqrt{n}$$$, and converges to $$$0$$$ if $$$k = c\sqrt{n}$$$ for $$$c > e$$$. Therefore, asymptotically, (the expected length of LIS) $$$\leq e\sqrt{n} < 2.719\sqrt{n}$$$.
Thus, the expected length of LIS will be asymptotically $$$c\sqrt{n}$$$ for $$$0.632 < c < 2.719$$$.
Combining these two theorems, one can say $$$t \leqq (4+o(1))\sqrt{n}$$$. Experimentally, the asymptotics of $$$t$$$ seems to be little lower than that, like $$$t \approx 3\sqrt{n}$$$.
Thanks for the proof :) In fact, I did find during contest that the upper bound of $$$t$$$ is LIS + LDS and therefore $$$O(\sqrt{n})$$$, but didn't realize this bound is tight. Later I was told that considering the points in $$$[1, \frac{n}{2}] \times [1, \frac{n}{2}]$$$ only (and setting their LIS "unchanged") is enough to prove the answer $$$\Omega(\sqrt{n})$$$ :)
I don't think my solution (involving 2-pointers) is $$$\Theta(n^{5/2})$$$ when the data is randomly generated, though (or I wouldn't try this solution during contest). The reason I used a 2-pointer approach to speed up the transition is that I estimated the expected number of squares with an edge on line $$$x = x_0$$$ to be likely $$$O(1)$$$. And if it is $$$O(1)$$$, the whole solution will be $$$O(n^2)$$$. It's quite hard to prove this, though, as the distribution of the maximal squares is hard to describe (or can it be contradicted?).
I also heard that some accepted solutions involve keeping only the $$$1000$$$ largest/smallest squares during DP or stuff like that. Is this an intended solution?
First of all, thank you for participating in JOI Open Contest 2022!
There were 4 participants (qazswedx, djq_cpp, djqtxdy, 127) who got full 300 points. Congratulations! The overall ranking is available here.
You can upsolve problems in the contest website until July 11th. The editorials and sample source codes will be published soon. Also, feel free to answer the questionnaire JOI Open Contest 2022 Survey.
Does someone know when will JOI Open Contest 2023 be held?