Hello! Happy New Year! I'm happy to announce XXI Open Cup: Grand Prix of Nanjing, which will be held on Jan 10th, 2021.
This contest is mainly prepared by SUA Programming Contest Problem Setter Team, which has already been served as the 2020 ICPC Asia Nanjing Regional Contest.
Authors: chenjb, zimpha, shb123, TsReaper, oipotato, jiangshibiao, MudCoal
Testers: 300iq, Um_nik, Merkurev, KAN, jqdai0815, Suika_predator, lwn_16, lxlxl, Sugar_fan, liguanglin, lyk248289469. Thank you!
Contest link: http://official.contest.yandex.ru/opencupXXI/contest/24046/enter (Only visible for users with OpenCup login)
I will publish this contest to gym and please feel free to discuss afterwards.
UPD: An editorial written in Chinese Zhihu and I will make an english version later (hopefully).
UPD2: Now it is in the gym.
Your URL is wrong; it should have "opencupXXI" instead of "opencupXX"
Thanks, I will update it immediately.
Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).
Div 2 link doesn't work
No div2 contest today?chenjb
Sorry I don't know about div2 contest, maybe should poke snarknews
Link to Div.2 still doesn't work. OpenCup with it's usual...
How to solve A and D?
In A got AC by building very long path (diagonal zigzag)
Funnily I've have had another solution which locally had better (33%) success rate but it couldn't get AC which is very weird
Could you share that 33% one with me? I thought there should be some problems with that.
I run 10 stress tests under different seeds, the result is below:
Thanks, must be some kind of error in local checker
Turns out the basic rand() that local C++ compiler has gives 33% but after switching to proper random it dropped to just 20%. One more proof that C++ rand() is garbage.
In the regional, some teams asked me to justify whether the checker is correct because of this issue. Then we found that using rand() under windows will somehow give a much higher hack ratio.
Wow, I have heard a few times that C++ rand is not great from the cryptographic perspective, but I never imagined it can actually be distinguished from better randomness in "real life scenarios" o0
I also did diagonal zigzag but first got WA. Then I only changed
cout << grid.at(i).at(j);
tocout << grid.at(19-i).at(j);
and go AC...This is possible. A diagonal zigzag without any adjustment may got failed in some tests if unlucky. 125/500 is a little bit tricky. While if you make few adjustments to make full use of grids and build some traps, you construct will be more stable...You see I was going to set 5*125/500 tests but soon I realize this is too mean...
Strategy in D: call vertex bad if its degree is more than $$$n/2$$$. While there is an edge between bad vertices, delete such edges. It will not break graph connectivity. After that while there is an edge with one bad end which is not a bridge, delete it. After that if there is still a bad vertex, answer is "No", otherwise find any spanning tree.
How do you incrementally figure out whether an edge is a bridge or not? You can delete an edge and then some edge that didn't use to be a bridge now becomes one and figuring that online seems quite difficult
Find any spanning tree and delete only edges outside of it. After that there will be at most one bad vertex. If you delete it and find connected components of the remaining graph, then you need one edge going to each component, so you can delete all the other edges.
How to solve C?
EZ win xDDDDD
We: 1353min
Past Glory: 1354min
my brain exploded after trying to hack A 69 times))))))) you have no idea what tests I tried...
plz someone write a map from A. i really tired very much because of this shit(
People really need to stop being so afraid of geometry xd
I didn't even know there was geometry. Reading all the statements is too hard.
Just go through statements and search for "x_i y_i" in input section =] (and make sure statement doesn't mention rectangles so that it is not some stinking sweeping instead of real geometry). I do that in first 5 minutes of every contest :D
Both Yuhao and I are very curious about this issue too. In the regional, only 1 team solved I while 14 teams solved J. And testers solved I in the early period of 5 hours.
Scoreboard effect?
At first read, we thought you'd have to do the plane-sweep interval expanding/merging thing, before we realized that there are easier solutions because of small bounds. Perhaps other teams had this mistake too?
And in my code I've just got $$$10^9$$$ xD
Will be the editorial published?
We had already made a Chinese version and I may make an english version and publish the contest onto gym as soon as I got out of hospital~
How to solve problem B?
How to solve C and J?
J: if the bitwise xor of all pile sizes is $$$X$$$, you want to compute number of values $$$v$$$ in range satisfying $$$v\oplus X < v$$$. This happens precisely when $$$v$$$ has a $$$1$$$ at the most significant bit position of $$$X$$$. So maintain bitwise xor and count of values with a $$$1$$$ for each bit position, handle the update with segment tree beats (you need to additionally maintain minimum, count of minimum, and second minimum).
I managed to squueze $$$O((n+q)\sqrt{n} \log {A})$$$ in 2.052s in upsolving.
C:
Let's assume you first move in the following order exhausting moves of each type: Right, Left, Up, Down.
Suppose you move initially $$$x_r$$$ units to the right. Let $$$y^r_{hi}$$$, $$$y^r_{lo}$$$ be the maximum/minimum $$$y$$$ coordinate of the points to the right of $$$x_r$$$. Then go to left up to $$$x_l$$$, and let $$$y^l_{hi}$$$, $$$y^l_{lo}$$$ be the highest/lowest $$$y$$$ coordinate of the points to the left of $$$x_l$$$.
The answer to the problem is: $$$2 \cdot x_r + |x_l| + 2 \cdot \max(y^r_{hi}, y^l_{hi}) + \max(|y^r_{lo}|, |y^l_{lo}|)$$$ [1]
To compute this efficiently, we should store for all coordinates $$$x_l \le 0$$$ the four values: $$$x_l + a \cdot 2 \cdot y^l_{hi} + b \cdot y^l_{lo}$$$ where $$$(a, b) \in (0, 1)^2$$$ in a data structure such as a segment tree to query for minimums.
Fix each $$$x_r$$$ and, and depending on the values of $$$y^r_{hi}$$$, $$$y^r_{lo}$$$ you can determine using binary search some intervals to the left where you know in the equation [1] which terms of the $$$max(\cdot, \cdot)$$$ will dominate, and query for minimum in that intervals on relevant segment tree.
Finally, since the order of the moves (LRDU) affects the answer, you should try the four of them, flipping $$$x$$$ and $$$y$$$ axis, and solving the problem multiple times.
Code
Did other people get B accepted with some sensible solutions? We just got shameless $$$O(n^2)$$$ because who gives 10 seconds TL (which was 14 seconds in statements >:[) with $$$n \le 50000$$$
The intended solution goes with O(nlog^2n) or even O(nlogn) from zimpha. I got no idea with the TL on Yandex and all work are done by snark since I stayed in hospital for about a week :(
Why was the time limit so high then? It looked like the intended was O(n sqrt(n) log(n)) or something. My O(n log^2(n)) takes only 231ms to run. The time totally could've been way tighter if that was intended.
Strange. I check both mashup and polygon, the TL is supposed to be 5000ms... The runtime of std takes 2600ms...I don’t know what happened when it is moved to Yandex.
The reason could be that the std runs extremely slowly on Yandex (which happened before) and the. Snark have to set it to 10s.
Std runs 3.6s.... So I got no idea why TL is 10 or 14s...Sorry for this issue, should be tighter though.
Is std model solution? What does it stand for? If it runs 3.6s on Yandex then 5s would be really cruel... And we needed just 5.9s xd
I think std stands for "standard", as in "gold standard"/model solution? Not too sure.
If std took 3.6s, then 10s time limit is reasonable. Why does std take more than 1 second for $$$O(n log^2(n))$$$ when $$$n \le 50000$$$ though? That constant seems really bad.
Yes, it behaves badly on Yandex, but it is O(nlog^2n) after all. If 3.6s on Yandex, a better idea is to ask the author provide one with smaller constraints, or this seems a little bit ridiculous. I think sqrt solutions (sqrt*log or sth else) can be allowed to pass, but personally I don’t want n^2 to get passed. But never mind LOL
My solution was a pretty standard "merge smaller into bigger on suffix tree" idea.
The hard part of this problem is counting the number of $$$i$$$ so that $$$s[k \ldots n]<s[i \ldots n]$$$ but $$$r-k+1 > lcp(s[k\ldots n], s[i \ldots n]) \ge r-i+1 \ge 1$$$ (note in particular that this condition implies $$$k < i \le r$$$). (The other cases are simple rectangle queries on the set of points $$$(i,rank(s[i\ldots n]))$$$ from the suffix array of the whole string, though you could do smaller into bigger too if you wanted.)
To solve this case, we run merge-smaller-into-bigger on the suffix tree. For each node, we store a set of queries with $$$k$$$ in this subtree satisfying $$$r-k+1 > height$$$ sorted by $$$r$$$, and a sorted set of indices $$$i$$$ in this subtree. You can maintain these with smaller into bigger.
Then, we just need to handle all valid query/index pairs from 2 siblings being merged (queries from the left sibling and indices from the right). Once again, we use smaller into bigger. If there are fewer queries than indices, loop over the queries $$$r$$$ and count the number of indices with $$$r\ge i > r-height$$$ (so we should store the indices in an order statistic tree, I used PBDS). If there are fewer indices than queries, then for each index $$$i$$$, add one to all queries $$$i \le r < i+height$$$ (so we should store the queries in a BBST or compressed seg tree with lazy propagation, I used treap).
All of this is trivial to analyze as merge-smaller-into-bigger with O(log(n))-time data structures, so it naturally achieves O(n log^2(n)). In fact, splay trees and treaps and some other BBSTs can perform union of sets of size $$$m<n$$$ in $$$O(m \log(n/m))$$$, so if we use those for everything, we can get $$$O(n\log(n))$$$ runtime.
That's exactly what we hoped for — that you guys will go for a fair solution instead of gaming the system like us haha. Maybe that's what we need to win anything xD Radewoosh was hiding from the rest of us what he is trying to do because me and Marek would try to convince him to solve it in a typical way, but he turned out to be right :p
In fairness, this solution only took ~40 or ~50 minutes to implement, and I got it without any dirt, so I'm not sure squeezing would've worked out better. We were considering it, but decided not to try.
Just to confirm, "The other cases are simple rectangle queries" what are these cases? Or in other words, are you missing "k < i" condition from what you wanted to count in second paragraph?
Yes, here are the other 2 cases:
Note that the LCP/string conditions just correspond to a range of the suffix array, so these are rectangle queries.
In the second paragraph, $$$k < i \le r$$$ is implicit because $$$r-k+1 > r-i+1 \ge 1$$$ (sorry about that confusion).
How to solve F?
Solution of E: Contestants may solve it with a bunch of case analysis. But the intended solution is that there must be a permutation that doing all U,D,L,R together. So enumerate all 4! and check whether it is legal.
F (fixed point approach): As we want the minimum making optimal decisions, we can build a recursion:
note. $E_i$ is the expected time to rest with i unused fireworks.
Our main problem is that we need $$$E_0$$$ to solve the problem. If we take a closer look at the recursion, we can realize that:
We can notice that if the $E_0$ on the right is fixed, the function with respect to $$$i$$$ in the positive reals is convex. now we can solve the problem by noting that the resulting value minus the set value gives us the direction of our optimal value in the binary search (if I set a lower value, the minimum takes a higher value and closer to our solution, if I give it a higher value, the minimum takes a lower value.).
To solve each subproblem in good time, note that the minimum value takes it in:
note. where $x$ is the fixed value and $$$\beta = (1 - \frac{p}{10000})$$$
Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).
I have a faster solution for I.
Using a binary search for the answer, it's possible to reduce the problem to checking if there is a path satisfying a certain horizontal speed limit.
Let a point be reachable if it is the end of a correct path. It's possible to bypass all obstacles iff there is a reachable point above all of them.
Let's use scanline to find reachable points. Initially, the scanline is located below the obstacles and reachable points form a segment $$$[-m, m]$$$. I claim that at any height reachable points lie in a union of segments. Consider a range $$$[y_1, y_2]$$$ of heights where no obstacles start or finish. To recalculate a segment of reachable points while moving the scanline through this range, one can do the following steps:
Expand the segment by $$$\frac{v_x}{v_y} \cdot (y_2 - y_1)$$$ from both sides
Find obstacles that are the nearest to the right and the left.
Intersect it with the segment formed by the upper points of the obstacles.
The only case when the number of segments increases is when a segment is split by a starting point of a new obstacle. Therefore, the number of segments is $$$O(n)$$$ and the overall complexity of this solution is $$$O\left(n^2 \log \left( \frac{C}{\varepsilon} \right)\right)$$$.
This is the idea we initially had as well. I think you should be able to do this in $$$\tilde{O}(n \log(n))$$$ by maintaining events and whatnot, but I haven't worked out the details.
Regardless, this solution is faster by asymptotic runtime, but not by time to AC!
Isn't tilde over $$$O$$$ supposed to ignore logarithmic factors?
Yeah, I was going to ignore them, but $$$\tilde{O}(n)$$$ just looks too small, you know? I am ignoring factors of $$$\log(1/\varepsilon)$$$ though.
I used Google Translate to translate the editorial of problem B from Chinese. And I struggle with understanding it.
"For this tree, the points with only one son can be removed, so that $$$O(n)$$$ points are obtained."
Why $$$O(n)$$$ points are obtained?
"Then, for those who have $$$k$$$ sons, a binary tree of size $$$2k-1$$$ can be constructed."
Which binary tree?
It would be really helpful if there is an english editorial, the chinese one with google translate is sometimes a bit difficult to understand. Please look into this if possible, and thanks for great problems.