Блог пользователя chenjb

Автор chenjb, история, 2 года назад, По-английски

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, Sugar_fan, shb123, 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.

  • Проголосовать: нравится
  • +350
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

I Love ChenJB

»
2 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Good problems.

»
2 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Edward Gaming!

»
2 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

EDG NB!

»
2 года назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

chenjb's legend lasts forever!

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Nice problems!

»
2 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Congratulations Edward Gaming!

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

EDG 666

»
2 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

EDG 777

»
2 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

The night of EDG!!!

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Glory to EDG and LPL!

»
2 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

The problems are really nice!

»
2 года назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +46 Проголосовать: не нравится

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

    Congratulations to EDG!

  • »
    »
    2 года назад, # ^ |
    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).

  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    GP of DRX when?

    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      I will hold a CF contest when T1 lifts a summoner's cup. Mark my words.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

с детства за спиритов!

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be a div.2 contest available?

»
2 года назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

    Yes.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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 :(

  • »
    »
    2 года назад, # ^ |
    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).

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +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!

»
2 года назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

how to solve problem H and J?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +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.

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +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?

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +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.

»
2 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

No more Perl among languages. Miserable :'(

»
2 года назад, # |
  Проголосовать: нравится +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?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

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

    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      How can we prove this estimation?

      • »
        »
        »
        »
        2 года назад, # ^ |
          Проголосовать: нравится +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.

        • »
          »
          »
          »
          »
          2 года назад, # ^ |
            Проголосовать: нравится 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?

          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
            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.

            • »
              »
              »
              »
              »
              »
              »
              2 года назад, # ^ |
                Проголосовать: нравится +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.

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
    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.

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +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

»
2 года назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Is there any solution of J via suffix automaton?

»
17 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me? I always get wrong answer on #3.

my submission: #180039582