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

Authors: oipotato, Claris, chenjb, lxlxl, Subconscious, pb0207, Heltion, syvjjp416, lwn_16, quailty, Suika_predator.

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

Contest link: https://official.contest.yandex.ru/opencupXXII/contest/31241/enter (Only visible for users with OpenCup login)

Gym link: https://codeforces.com/gym/103409

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

**UPD1: The link posted.**

**UPD2: The contest has been uploaded to Gym.**

Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).I Love ChenJB

Good problems.

Edward Gaming！

EDG NB!

chenjb's legend lasts forever!

Nice problems!

Congratulations Edward Gaming！

EDG 666

EDG 777

The night of EDG!!!

Glory to EDG and LPL!

The problems are really nice!

The game was a bit depressing to watch for us, but congratulations to Edward Gaming and LPL fans for their well-deserved victory!

Hey, at least your region isn't doing worse than NA.

Congratulations to EDG!

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

Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).Will there be a div.2 contest available?

div.2 Contest Link: https://official.contest.yandex.ru/opencupXXII/contest/31242

Is there a simple way to solve problem B? We have a straightforward segment tree approach but it's hard to implement.

std::set to store !9

How to solve it neatly with a set? We implemented that, but it was a nightmare to debug.

you can refer to the standard solution

wow

I maintained segments of equal digits in std:;set(l,r,digit). Didn't have to debug tho

Auto comment: topic has been updated by chenjb (previous revision, new revision, compare).Is L $$$O(N^3 + QN)$$$? I had that but was killed by constant factor :(

Yes.

the number of states in DP and the number of initial states in D&C affect the running time much :<

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 :(

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

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!

how to solve problem H and J?

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.

I've implemented the solution with the inbuilt OST but I can't fit it into the TL ;(

Can you send me your code please? I wrote this solution, but got TLE. (suffix array was written with radix sort)

https://ideone.com/Id1Ytz

Thank you so much :)

How to solve C? On array I've came up with sqrt + CHT solution, but I can't even generalize it to tree.

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.

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.

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?

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.

No more

Perlamong languages. Miserable :'(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?

There are at most $$$3^{n/3}$$$ shortest paths, so brute force.

How can we prove this estimation?

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.

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?

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.

Ah right. I missed the part where it said it is the unweighted shortest path. I kept thinking it is saying about weighted one.

Any better solution for F than $$$O(nmlog(n))$$$? We used Dijkstra for every vertex, but it barely passed TL.

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.

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

Is there any solution of J via suffix automaton?