chenjb's blog

By chenjb, history, 2 months ago, In English

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.

 
 
 
 
  • Vote: I like it
  • +350
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +47 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +48 Vote: I do not like it

I Love ChenJB

»
2 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Good problems.

»
2 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Edward Gaming!

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

EDG NB!

»
2 months ago, # |
  Vote: I like it +17 Vote: I do not like it

chenjb's legend lasts forever!

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Nice problems!

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Congratulations Edward Gaming!

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

EDG 666

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

EDG 777

»
2 months ago, # |
  Vote: I like it +13 Vote: I do not like it

The night of EDG!!!

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Glory to EDG and LPL!

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

The problems are really nice!

»
2 months ago, # |
  Vote: I like it +70 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

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

    Congratulations to EDG!

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +70 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be a div.2 contest available?

»
2 months ago, # |
  Vote: I like it +48 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +43 Vote: I do not like it

Is L $$$O(N^3 + QN)$$$? I had that but was killed by constant factor :(

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Yes.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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!

»
2 months ago, # |
  Vote: I like it +23 Vote: I do not like it

how to solve problem H and J?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

No more Perl among languages. Miserable :'(

»
2 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      How can we prove this estimation?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    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

»
2 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Is there any solution of J via suffix automaton?