Update 2019/11/07. The contest is now in Gym. Thanks to MikeMirzayanov for uploading it. Have fun!
Hello! I'm happy to announce XX Open Cup. Grand Prix of Korea.
- Contest link: http://official.contest.yandex.ru/opencupXX/contest/14556/enter (Only visible for users with OpenCup login)
- Contest time: 2019/10/13 Sunday, 17:00 Korea Standard Time (UTC+9).
- Problemsetters: ainta, Cauchy_Function, jh05013, ko_osaga, kriii, .o.. Thank you!
- Testers: All problemsetters, kdh9949, Konijntje, jqdai0815, tzuyu_chou, xiaowuc1, chenjb. Thank you!
List of relevant previous contests:
- XVIII Open Cup. GP of Korea
- KAIST RUN Spring Contest 2018
- XIX Open Cup. GP of Korea
- XIX Open Cup. GP of Daejeon
Enjoy!
I can't wait to solve them
How dare you say that on comment
Best sentence of the problem-set:
If you know about “cardinals,” please assume that “infinite” refers only to “countably infinite.” If you don’t know about it, then you don’t have to worry.How to solve I?
Link
We almost removed I due to that issue (apparently it's well known in China), but I just decided not to. Hope you enjoyed our contest anyway.
Yes, other problems were pretty nice.
That's a beautiful problem but I've seen it so many times already... It's well known in Poland as well and I guess everywhere else too
I initially made an easier problem, but .o. lately discovered that it was solvable for a general graph, hence the current form.
I don't think it was known in Korea (at least no testers knew), so it was nice to use for local contests. For OpenCups, I agree that it's not enough to please top-level contestants since the topic is pretty general.
Also it was in Jagiellonian U Contest, at winter ptz camp 2013 (Problem H. Hunt).
I thought it was something like we can find all pair shortest distance between all the vertices. Let, the maximum distance d be between u and v. These will be our two ends of the diameter. After that, we find a path between u and v, of distance d. We then add the rest of the vertices in a greedy manner so that our diameter remains unchanged. Can we approach the solution like this?
So, is it possible to solve J faster than O(nlogn) with Treap? Our solution is still getting TL 13.
You can maintain $$$dp_i - dp_{i-1}$$$ in heap.
Can you explain please? I don't think we can change Treap in our solution without getting O(nlog^2n).
You can use
std::priority_queueinstead of treap. I claim that the complexity would still be $$$O(n \log n)$$$. Indeed, unlike the more common situation, when we merge things that have size $$$O(\text{subtree size})$$$, here we merge things that have size $$$O(\text{subtree depth})$$$. It is quite well-known that we will do only linear number of operations in that case (and each of them takes $$$O(\log n)$$$ time).The solution is not particularly quick even with heap (the implementation below took ~0.5s on Yandex.Contest), so it is unsurprising (though unfortunate) that using treap may give TL.
Code
Oh,
std::priority_queueis probably much faster than the nonsense I was doing withstd::multiset.Our solution ran in 1.161s during the contest, but strangely runs twice as fast when I resubmit the same code now at ~0.5s.
How to solve I and J? We wrote the solution of J using heavy-light ,, but I think it has a simple solution :( Can anyone explain ?
How to solve J using heavy-light?
I proved for my opinion , if for $$$k$$$ we take some set of vertices , for $$$k + 1$$$ we need only add some vertices to that set. Now we can solve problem only for $$$k = 1$$$. After we find set of vertices for $$$k = 1$$$ , we can delete vertices of that set and do it again for the new tree.
For vertex $$$v$$$ we take difference $$$dif[v] = (val[v] - \sum_{to}{dp[to]})$$$ where $$$to$$$ is the child of $$$v$$$ , $$$dp[to]$$$ is the answer for subtree of $$$to$$$ for $$$k = 1$$$ and $$$val[v]$$$ is the value which is given in the statement.
Now for $$$k = 1$$$ , how we find vertices that we need? The vertex $$$v$$$ is in the set if and only if $$$dp[v] = val[v]$$$ therefore we need that $$$dif[v] >= 0$$$ (We can find this with simple segment tree). After we take this vertex we delete that vertex (give the value of $$$dif[v]$$$ $$$-infinite$$$ in the segment tree) and doing update $$$dif[x]$$$ $$$+$$$$$$=$$$ $$$dif[v]$$$ , for any vertex $$$x$$$ from $$$root$$$ to $$$parent[v]$$$ (update this with heavy-light decomposition).
P.S. We got WA7 during the contest.
Congratulations to Polish Mafia (mnbvmar, Radewoosh, Marcin_smu) for the first place by a huge margin, and also being very close to all solve!
Here is the solution.
I hope you enjoyed the contest!
I think time limit for problem F was very tight, we did the segment-tree variant and it was impossible for us to squeeze it in time.
I have got TL 46, but it wasn't related to the segment tree speed. Try checking maxtest with $$$O(n)$$$ add queries with $$$k = 0$$$ and $$$O(n)$$$ third type queries with $$$x = 0$$$.
I really enjoyed the problemset, thanks for it!
What is your solution in K? I'm curious because of your submission time.
Centroid decomposition on the first tree and subtree compression and two closest ones on the second tree.
Same for us, for some reason it took 30 minutes only to code it :O
Practice klavogonki more please
In K I also built centroid decomposition for one tree and reduced problem to $$$\min_{u \neq v}(a_v + d(v, u) + a_u)$$$ on the compressed second tree. But for some reason I thought that the fastest way to solve it is also centroid decomposition, so I wrote 2-dimensional centroid decomposition. It's $$$O(n\log(n)^2)$$$ with huge constant, but passed in 9.5 seconds.
We wrote nlog^2 solution with centroids, but waste a lot of time to fit it in TL. Could anybody, who hasn't such issues post their code?
koosaga kriii. They run slightly less than 0.5x TL. Sorry for bit tight limits.
An alternative solution for D:
Consider only positions of 2. If you move all 2s into the correct position, then 1s are in the correct position automatically.
Let's assume the assignment of 2 are fixed (matching of starting positions and ending positions). Let d_i : |start position of i-th 2 — end position of i-th 2|. Then, the lower bound of the cost is (the sum of ( (d_i/2) * (C+1+1+2) + (d_i%2) * (C+1+2) ) ) + (number of inversions in assignment).
And, surprisingly, it is always possible to do (you can find at least one optimal move in each situation)
So, we can use dp[][] for each parity. The time complexity is O(N^2) and you can find the actual order of operations by topological sort.
Contest was good, big thanks to authors
Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).
Auto comment: topic has been updated by ko_osaga (previous revision, new revision, compare).