### chenjb's blog

By chenjb, history, 15 months ago,

Hello! I'm happy to announce XXII Open Cup: Grand Prix of EDG, which will be held on Nov 14th, 2021.

This contest is mainly prepared by Zhejiang University, which has already been used as the 2021 CCPC Guilin Contest.

On the same day of the 2021 CCPC Guilin Contest, Team Edward Gaming (EDG) from League of Legends Pro League (LPL, China) won the Champion of the 2021 League of Legends World Championship held in Reykjavík. They are also the only LPL team entering the semi-finals while the rest of three teams all coming from League of Legends Champions Korea (LCK, Korea), including the champion from last year. Almost nobody would bet on their winning, but they made it and reclaim the glory for LPL after 2 years.

Team EDG has been doubted for a long time because their performance in the World Championship is usually very struggled and disappointing. However, they never give up their dream. Their brave heart and the strong will push them go forward. Now they make the history. Their spirit moves everyone and their legend lasts forever.

As well as contestants, problem setters are also deeply touched by their victory. Their spirit inspires us. In competitive programming, it is the same spirit that drives us improve ourselves, challenging problems and enjoying every contest.

Therefore, we decide to call this contest as the GP of EDG.

Coordinators: oipotato, Claris

Testers: SSerxhs, Eden_CY, cxt, nothing100, UESTC_Nocturne, Orenji.Sora, Onozuka, Maniac_Wallnut, Randias, qiqi20021026, DeepinC, szb, LOLtxdy, Sdchr, chenyanbo, Tommyr7. Thank you!

I will publish this contest to gym and please feel free to discuss afterwards.

UPD2: The contest has been uploaded to Gym.

• +350

 » 15 months ago, # |   +47 Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).
 » 15 months ago, # |   +48 I Love ChenJB
 » 15 months ago, # |   +15 Good problems.
 » 15 months ago, # |   +22 Edward Gaming！
 » 15 months ago, # |   +16 EDG NB!
 » 15 months ago, # |   +17 chenjb's legend lasts forever!
 » 15 months ago, # |   +13 Nice problems!
 » 15 months ago, # |   +16 Congratulations Edward Gaming！
 » 15 months ago, # |   +13 EDG 666
 » 15 months ago, # |   +14 EDG 777
 » 15 months ago, # |   +13 The night of EDG!!!
 » 15 months ago, # |   +8 Glory to EDG and LPL!
 » 15 months ago, # |   -10 The problems are really nice!
 » 15 months ago, # |   +70 The game was a bit depressing to watch for us, but congratulations to Edward Gaming and LPL fans for their well-deserved victory!
•  » » 15 months ago, # ^ |   +46 Hey, at least your region isn't doing worse than NA.Congratulations to EDG!
•  » » 15 months ago, # ^ | ← Rev. 3 →   +70 LCK remains to be very strong over the years and the final is a close game that everyone was so nervous. Many thanks to both teams for presenting such an excellent game to us. I am pretty sure most contestants in CCPC Guilin were influenced by it because of staying up late though (oops).
•  » » 3 months ago, # ^ |   +20 GP of DRX when?
•  » » » 3 months ago, # ^ |   +10 I will hold a CF contest when T1 lifts a summoner's cup. Mark my words.
 » 15 months ago, # |   +8 Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).
 » 15 months ago, # |   0 Will there be a div.2 contest available?
•  » » 15 months ago, # ^ |   +52 div.2 Contest Link: https://official.contest.yandex.ru/opencupXXII/contest/31242
 » 15 months ago, # |   +48 Is there a simple way to solve problem B? We have a straightforward segment tree approach but it's hard to implement.
•  » » 15 months ago, # ^ | ← Rev. 3 →   +32 std::set to store !9
•  » » » 15 months ago, # ^ |   +16 How to solve it neatly with a set? We implemented that, but it was a nightmare to debug.
•  » » » » 15 months ago, # ^ |   +55 you can refer to the standard solution
•  » » » » » 15 months ago, # ^ |   +16 wow
•  » » 15 months ago, # ^ |   +8 I maintained segments of equal digits in std:;set(l,r,digit). Didn't have to debug tho
 » 15 months ago, # |   0 Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).
 » 15 months ago, # |   +43 Is L $O(N^3 + QN)$? I had that but was killed by constant factor :(
•  » » 15 months ago, # ^ |   -10 Yes.
•  » » 15 months ago, # ^ |   +34 the number of states in DP and the number of initial states in D&C affect the running time much :<
•  » » 15 months ago, # ^ |   +10 Exactly, I had a solution in the same complexity, but was afraid of constant factor from the very beginning and indeed my fears were justified cause I couldn't optimize it to pass :/ I hoped that optimizing from O(n^3 log n) to O(n^3) would be enough, but it wasn't :(
•  » » 15 months ago, # ^ | ← Rev. 2 →   +10 I've read the model solution (the one I've read was ugly as hell, don't recommend that) and understood the idea that I lacked to cut down the constant factor by 4. Basically in my D&C solution I was iterating through 4n intermediate states. n comes from iterating with one endpoint, 4 comes from iterating over cases which endpoints are bought. That 4 factor can be removed, because you can assume that you go through a state where the endpoint which is fixed is not bought, while the one you iterate with is bought (if your dp is appropriately written, because in the way I wrote it I needed a bit more sophisticated fix).
•  » » » 15 months ago, # ^ |   +21 Thanks for writing this comment!I spent whole day yesterday trying to squeeze my solution into TL. I also tried to read model solution, but didn't notice that idea about factor 4 :(Actually, we came to the idea how to reduce 4 into 2 during the contest, but didn't realize it could be improved two more times...I literally changed 1 byte in the solution today, and got AC!
 » 15 months ago, # |   +23 how to solve problem H and J?
•  » » 15 months ago, # ^ |   +20 Here's what I did in J: build a suffix array for $S$, answer all the queries offline in order of increasing $k$.Consider all substrings of length $\ell$ in the suffix array. All strings with shorter lengths can be considered as gaps, while all other suffixes will be split into several consecutive segments will equal prefixes of length $\ell$. Store these segments in a set (better yet, a treap).Consider some $k$. If the number of segments in the set is less than $k$, we need to increase the current length $\ell$ (and reduce $k$ accordingly, since we've skipped some substrings). When increasing $\ell$, one suffix will be removed, and some segments will be divided into parts, we just need to find places with $\texttt{lcp} = \ell$. The last thing to do is to find the $k$-th segment in this set. It can be done by a treap or the built-in order statistics tree.
•  » » » 15 months ago, # ^ |   0 I've implemented the solution with the inbuilt OST but I can't fit it into the TL ;(
•  » » » 15 months ago, # ^ |   0 Can you send me your code please? I wrote this solution, but got TLE. (suffix array was written with radix sort)
•  » » » » 15 months ago, # ^ |   0
•  » » » » » 15 months ago, # ^ |   0 Thank you so much :)
 » 15 months ago, # |   +18 How to solve C? On array I've came up with sqrt + CHT solution, but I can't even generalize it to tree.
•  » » 15 months ago, # ^ |   +33 Since C is never placed above A we can decide each ? separately by comparing the number of (A/?) above each node with the number of (C/?) below. If we store the difference between these two at each node, we need to support operations subtree increment/decrement, path to root increment/decrement, and maintain sum of positive nodes. We can turn these into interval increment/decrement with the HLD/euler tour layout trick and use sqrt blocks to maintain.
•  » » » 15 months ago, # ^ |   +23 The intended solution is $O(n^{1.5})$ without any log factor. Assume we know the next $K=O(\sqrt{n})$ operations, there are $K=O(\sqrt{n})$ vertices that will be modified, so we can compress the tree into a small tree with size $O(K)$, and run brute-force in each operation. After we finish all $K$ operations, fetch the next $K$ operations and rebuild the compressed tree again.
•  » » » 15 months ago, # ^ |   +13 Did you consume $O(n \sqrt n)$ memory to count appearance of each difference in a block, or was it unordered map, or am I missing something?
•  » » » » 15 months ago, # ^ |   +16 We had a hashmap at first, we switched to an array but only storing frequencies for O(sqrt(n)) closest values for each block and rebuilding it if needed.
 » 15 months ago, # |   +3 No more Perl among languages. Miserable :'(
 » 15 months ago, # |   +29 I wonder if K can be proven to be NP-hard...I've got some ideas about how to solve it (polynomially) with a min-cost flow, but can't complete them to get a full solution.So, create vertices $v_{1}, \ldots, v_{m}$, a vertex for each company. For every $i$ introduce edges with $\texttt{capacity} = 1$: from $1$ to $v_{i}$ with costs $w_{i}, 2w_{i}, 3w_{i}$, etc. If the shortest distance from $1$ to $t$ is $d$, then we want to find a flow of magnitude $d$ which selects several edges via the $v_{i}$'s. Every unit of the flow in $v_{i}$ allows us to select a single edge which is controlled by company $i$. Somehow we need to restrict the selected edges so that they form a path from $1$ to $t$. We can easily restrict the number of edges taken in each layer of the BFS-DAG to be equal to $1$.The only issue left to resolve is to connect the edges in a path, so that every intermediate vertex has in-degree and out-degree exactly $1$. No idea how to do it though =) Any thoughts?
•  » » 15 months ago, # ^ |   +29 There are at most $3^{n/3}$ shortest paths, so brute force.
•  » » » 15 months ago, # ^ |   +13 How can we prove this estimation?
•  » » » » 15 months ago, # ^ |   +16 Led $d_x$ be the distance from $1$ to $x$, you will only use an edge from $a$ to $b$ if $d_a + 1 = d_b$.Let $c_x$ be the number of vertices $u$ with $d_u = x$, the total number of shortest paths will be $c_1 \cdot c_2 \cdot ... \cdot c_m$.So the number ofshortest paths in a graph of size $n$ is the maximum along $c_1 \cdot c_2 \cdot ... \cdot c_m$ along some sequence such that $c_1 + c_2 + ... + c_m \leq n$.This is a classical problem, it is nonsense to use a $1$, if you use a number $x >= 4$, you can replace it with $x-2$ and $2$ and the product will be greater or equal, three $2$'s can be replaced with two $3$'s since $2^3 < 3^2$, so it is optimal to use as many $3$ as possible and fill the remainder with some $2$'s.
•  » » » » » 15 months ago, # ^ |   0 But in this particular problem, you can go from u to v in multiple steps instead of going there directly in one hop right? So will your analysis still remain valid?
•  » » » » » » 15 months ago, # ^ | ← Rev. 2 →   0 I can't understand you, the chosen path must be the shortest first by length and then by tax(the particular cost of the problem), so you can only move from $u$ to $v$ if $d_u + 1 = d_v$. Also, there is no multiple edges.
•  » » » » » » » 15 months ago, # ^ |   +10 Ah right. I missed the part where it said it is the unweighted shortest path. I kept thinking it is saying about weighted one.
 » 15 months ago, # | ← Rev. 2 →   +21 Any better solution for F than $O(nmlog(n))$? We used Dijkstra for every vertex, but it barely passed TL.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +13 You can iterate over the edges of smaller polygon in CCW and do two pointers to solve in $O(N+M)$.Suppose we're on the edge $p\rightarrow q$. If you extend this segment indefinitely, it'll partition the larger polygon into left and right piece. The contribution of the current edge to the answer is $len(pq) * len(RightPiece) / len(LargerPolygon)$. Let $l$ be the index of the most CCW-point on the left piece, and $r$ on the right piece. These two indices can be maintained with two pointers. If you maintain the prefix sum of length of edges of the larger polygon, you can find the sum of length of edges between $l$ and $r$ in constant time. Then find the intersection between $pq$ and the edges containing $l$ and $r$ to account for the first and last edges being cut. If it's still unclear, you can refer to the code.
•  » » 15 months ago, # ^ |   +40 Did you mean E? I used $n$ Dijkstras as well. And right, even though it passed in the first attempt, I used more than 0.75*TL
 » 15 months ago, # |   +21 Is there any solution of J via suffix automaton?
•  » » 8 months ago, # ^ |   -8 Yes
 » 3 months ago, # |   0 Can anyone help me? I always get wrong answer on #3. my submission: #180039582
•  » » 3 months ago, # ^ |   0