### chenjb's blog

By chenjb, history, 11 days ago,

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, Retired_MiFaFaOvO, Suika_predator, lwn_16, lxlxl, Heltion, liguanglin, lyk248289469. Thank you!

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).

• +82

 » 11 days ago, # |   +16 Your URL is wrong; it should have "opencupXXI" instead of "opencupXX"
•  » » 11 days ago, # ^ |   0 Thanks, I will update it immediately.
 » 11 days ago, # |   0 Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).
 » 11 days ago, # |   +9 Div 2 link doesn't work
•  » » 11 days ago, # ^ |   +5 No div2 contest today?chenjb
•  » » » 11 days ago, # ^ |   0 Sorry I don't know about div2 contest, maybe should poke snarknews
•  » » » 11 days ago, # ^ |   0 Link to Div.2 still doesn't work. OpenCup with it's usual...
 » 10 days ago, # |   +8 How to solve A and D?
•  » » 10 days ago, # ^ |   0 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
•  » » » 10 days ago, # ^ |   0 Could you share that 33% one with me? I thought there should be some problems with that.
•  » » » » 10 days ago, # ^ |   0 20 20 01111011111001111101 11001010001011000101 10011010111010111101 10110110100110100011 10101101101101101110 10111011011011011000 11000110110110110111 01011101100101101101 11010011010111011011 10110110111010110101 10101101101101101111 10111011010111011000 11000110111000110111 01011101101011101101 11010011011010011001 10110110110110010111 10101101100101110100 11101011010111000111 00011010111000111001 11110111101111101111 
•  » » » » » 10 days ago, # ^ |   0 I run 10 stress tests under different seeds, the result is below: 95 times hack 103 times hack 104 times hack 97 times hack 102 times hack 116 times hack 130 times hack 98 times hack 116 times hack 112 times hack 
•  » » » » » » 10 days ago, # ^ |   0 Thanks, must be some kind of error in local checker
•  » » » » » » 10 days ago, # ^ |   +20 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.
•  » » » » » » » 10 days ago, # ^ |   +35 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.
•  » » » » » » » 10 days ago, # ^ |   +18 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
•  » » » 10 days ago, # ^ |   0 I also did diagonal zigzag but first got WA. Then I only changed cout << grid.at(i).at(j); to cout << grid.at(19-i).at(j); and go AC...
•  » » » » 10 days ago, # ^ |   0 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...
•  » » 10 days ago, # ^ |   +18 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.
•  » » » 10 days ago, # ^ |   +10 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
•  » » » » 10 days ago, # ^ |   0 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.
 » 10 days ago, # |   0 How to solve C?
 » 10 days ago, # |   +34 EZ win xDDDDDWe: 1353minPast Glory: 1354min
 » 10 days ago, # |   0 my brain exploded after trying to hack A 69 times))))))) you have no idea what tests I tried...
•  » » 10 days ago, # ^ |   0 plz someone write a map from A. i really tired very much because of this shit(
•  » » » 10 days ago, # ^ |   0 Spoiler20 20 11111110111110111111 10101001101001101001 11011011011011011010 10110110110110110111 01101101101101101101 11011011011011011011 10110110110110110110 11101101101101101101 10011011011011011001 10110110110110110111 01101101101101101101 11011011011011011011 10110110110110110110 11101101101101101101 10011011011011011001 10110110110110110111 01101101101101101101 11011011011011011011 10110010110010110101 11101111101111101111 
 » 10 days ago, # |   +6 complicated enriched segment tree beats: 28 ACtrivial geo where you just need to check whether two segments intersect: 17 AC People really need to stop being so afraid of geometry xd
•  » » 10 days ago, # ^ |   0 I didn't even know there was geometry. Reading all the statements is too hard.
•  » » » 10 days ago, # ^ | ← Rev. 2 →   +29 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
•  » » 10 days ago, # ^ |   +8 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.
•  » » » 10 days ago, # ^ |   0 Scoreboard effect?
•  » » 10 days ago, # ^ |   0 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?
 » 10 days ago, # | ← Rev. 2 →   +26 Problem I
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 And in my code I've just got $10^9$ xD
 » 10 days ago, # |   +10 Will be the editorial published?
•  » » 10 days ago, # ^ | ← Rev. 2 →   +13 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~
 » 10 days ago, # |   +9 How to solve problem B?
 » 10 days ago, # | ← Rev. 2 →   +18 How to solve C and J?
•  » » 10 days ago, # ^ | ← Rev. 3 →   +26 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).
•  » » » 7 days ago, # ^ |   +10 I managed to squueze $O((n+q)\sqrt{n} \log {A})$ in 2.052s in upsolving.
•  » » 10 days ago, # ^ |   +9 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
 » 10 days ago, # |   +10 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$
•  » » 10 days ago, # ^ |   +18 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 :(
•  » » » 10 days ago, # ^ |   0 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.
•  » » » » 10 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 10 days ago, # ^ |   0 The reason could be that the std runs extremely slowly on Yandex (which happened before) and the. Snark have to set it to 10s.
•  » » » » » » 10 days ago, # ^ |   0 Std runs 3.6s.... So I got no idea why TL is 10 or 14s...Sorry for this issue, should be tighter though.
•  » » » » » » » 10 days ago, # ^ |   0 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
•  » » » » » » » » 10 days ago, # ^ |   0 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.
•  » » » » » » » » 10 days ago, # ^ | ← Rev. 2 →   0 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
•  » » 10 days ago, # ^ | ← Rev. 3 →   +20 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] 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 •  » » » 10 days ago, # ^ | ← Rev. 2 → +28 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 •  » » » » 10 days ago, # ^ | +10 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. •  » » » 6 days ago, # ^ | 0 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? •  » » » » 6 days ago, # ^ | 0 Yes, here are the other 2 cases: Case 1:$k < i \le r$and$lcp(s[k \ldots n], s[i \ldots n]) \ge r-k+1$. Case 2:$l \le i \le r$,$s[i \ldots n] < s[k \ldots n]$, and$lcp(s[k \ldots n], s[i \ldots n]) < r-k+1$. 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).  » 10 days ago, # | 0 How to solve F? •  » » 10 days ago, # ^ | ← Rev. 2 → +8 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. •  » » » 10 days ago, # ^ | 0 it's E. but i have already translated the solution from chinese. thanks •  » » 10 days ago, # ^ | ← Rev. 2 → 0 F (fixed point approach): As we want the minimum making optimal decisions, we can build a recursion:$E_i = \min (m + (1 - \frac{p}{10000})^i E_0, n + E_{i+1})$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:$E_0 = \min\limits_{i \ge 0}(m + n i + (1 - \frac{p}{10000})^i E_0)$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.). double lo = 0, hi = 1e12; for (int i = 0; i <= 65; ++i) { double mid = (lo + hi) / 2; if (f(mid) - mid >= 0) lo = mid; else hi = mid; } To solve each subproblem in good time, note that the minimum value takes it in:$i = \max(0, \log_{\beta}(\frac{-n}{x \ \log \beta})))$note. where x is the fixed value and$\beta = (1 - \frac{p}{10000})$ » 10 days ago, # | 0 Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).  » 10 days ago, # | +10 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)$. •  » » 10 days ago, # ^ | +20 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! •  » » » 10 days ago, # ^ | +25 Isn't tilde over$O$supposed to ignore logarithmic factors? •  » » » » 10 days ago, # ^ | ← Rev. 2 → +20 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.