Hello Everyone!
The 20th Japanese Olympiad in Informatics Final Round Online Contest will be held on February 14. (08:00-12:00 GMT).
The contest duration is 4 hours. There are five problems, which are the same as the 20th JOI Final Round. Problem statements will be provided both in Japanese and English.
The registration page will be announced 30 minutes before the contest start.
You can see details in the contest information page.
Auto comment: topic has been updated by yutaka1999 (previous revision, new revision, compare).
This is the best valentines gift someone could gave me.
Ahora soy mejor :)
Ahora todo cambió:)
Has anyone logged in the contest page?
Sorry for disturbing,something strange happended to my chrome.Now it has recovered.
Has anyone else had problem with getting tle on about five cases of p4 robot, while the rest were well within limit? If so, what did you fix?
Did you do Dijkstra's on edges instead of the nodes? I got TLE from doing that because I think that's not $$$\mathcal O((V + E) \log V)$$$ in the worst case. Anyway, here's my 100-points code if you want to compare: https://github.com/dolphingarlic/CompetitiveProgramming/blob/master/JOI/JOI%2021-robot.cpp
Oh I see, my dp state held previous edge instead of color and I transitioned to every other edge, so it was like creating edge graph which is O(m^2) ig. Clever wot u did with ur code, thx for sharing!
Great problems, thank you!
Especially the last problem seems interesting. How to solve it? I tried some cartesian-tree like approach but didn't get to the full solution.
I didn't think it through too deeply, but can you explain which part of your solution you wasn't able to implement? I'm talking about storing euler tour in cartesian tree, then increase $$$u$$$ and updating euler tour accordingly, since there will be $$$O(n)$$$ link/cut operations. For fixed path from $$$s$$$ to $$$t$$$ then answer can be calculated as sum of answers on some subsegments, and for each subsegment the answer is either $$$(p_i - p_{i-1}) \cdot c_{i-1}$$$ when $$$c_i \leq c_{i-1}$$$ or $$$u \cdot c_1 + (p_2 - p_1) \cdot c_2 + \ldots + (p_{k-2} - p_{k-3}) \cdot c_{k-2} + (p_k - p_{k-2} - u) \cdot c_{k-1}$$$ when $$$c_i < c_{i+1}$$$ for $$$i < k - 1$$$ and $$$c_{k-1} \geq c_{k}$$$, which is a linear function of $$$u$$$ (which I hope is possible to maintain in cartesian tree via 2-3 types of lazy propagation).
Here's a solution using only standard data structures.
First assume that $$$T=N+1$$$. Let $$$X_i$$$ be the coordinate of the floor $$$i$$$, i.e. $$$X_i := A_1+\cdots A_{i-1}$$$. The answer is the minimum cost to cover $$$[X_S,X_{N+1}]$$$ by subsegments of $$$[X_i,X_i+U]$$$ with cost $$$B_i$$$ per unit. Let $$$L_i$$$ (resp. $$$R_i$$$) be the maximum (resp. minimum) index such that $$$L_i<i$$$ and $$$B_{L_i} \leq B_i$$$ (resp. $$$R_i>i$$$ and $$$B_{R_i} < B_i$$$.) In the optimal covering, the $$$i$$$-th segment is used from $$$\max(X_i, X_{L_i}+U)$$$ to $$$\min(X_i+U, X_{R_i})$$$ (or isn't used when the subsegment degenerates.) Thus, if we fix $$$S$$$, the length of the $$$i$$$-th subsegment is a piecewise linear function with respect to $$$U$$$. We can easily update these functions and their sum, thus can answer each query in the descending order of $$$S$$$.
But, how can we handle the general case? Actually, we can reduce it to the previous case. Let $$$T'$$$ be the index whose value of $$$B$$$ is minimum among the floors in $$$[X_T-U, X_T]$$$. Then, the answer is (the answer for $$$(S,N+1,U)$$$)$$$-$$$(the answer for $$$(T',N+1,U)$$$)$$$+(X_T-X_{T'})\times B_{T'}$$$, and the reduction is done.
(Haven't read the whole solution above yet, but I think this is different.)
(oops is the spoiler below broken)
Consider the case where all $$$B_i$$$ are either $$$0$$$ or $$$1$$$ and the answer to each query is not $$$-1$$$.
For a query $$$(S,T,U)$$$, the bottleneck of my solution is summing the contributions of all intervals $$$[x,y]$$$ such that $$$S\le x\le y\le T$$$, $$$B_x=B_y=0, B_{x+1\ldots y-1}=1$$$ to the answer. This contribution is simply $$$\max(len_{x,y}-U,0)$$$, where $$$len(x,y)=A_x+A_{x+1}+\cdots+A_{y-1}$$$.
So we need to sum $$$len(x,y)-U$$$ over all intervals such that $$$S\le x, T\ge y, U\le len(x,y)$$$. This reduces to the following classical problem:
This can be done in $$$\mathcal{O}((N+M)\log^2(N+M))$$$ with Divide & Conquer + BIT.
It remains to reduce general $$$B_i$$$ to the $$$B_i=0,1$$$ case (left as an exercise).
Code (needs C++17 ...)
When will the test data for the problems be released?
You can solve all problems here: https://oj.uz/problems/source/546
Could anyone explain their solution to Problem 4? Thanks!