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

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

Hello, Codeforces!

The China Collegiate Programming Contest (CCPC) is a competitive programming contest series for college students in China, organized by the CCPC Committee, which consists of coaches of the competitive programming teams of Chinese universities. It started in 2015, and this year is the 5th edition of CCPC. There are 4 onsite CCPC contests this year, including three regional contests in Qinhuangdao, Harbin and Xiamen, as well as the CCPC Final in Beijing. Many Chinese universities use CCPC as an opportunity to practice before the ICPC regionals.

The 2019 CCPC Harbin Site has recently ended on October 13 in Northeast Forestry University. A total of 272 teams, most of whom were selected from the preliminary online contest, took part in the official onsite contest in Harbin. The problems for this contest were mostly prepared by retired ICPC participants of Zhejiang University, and the head judge was me.

We are glad to invite you to participate in its online mirror: The 2019 China Collegiate Programming Contest Harbin Site in Codeforces::Gym! Please note that the mirror contest will start at Saturday, November 2, 2019, 18:00 (UTC+8). Click on the link to see when it starts in your timezone. We will be able to answer your questions during the mirror contest. The ghosts of the onsite participants are available, so you may take advantage of it.

This contest uses ACM-ICPC rules and of course, it is unrated. Team participation is recommended, but it is also possible to participate individually. As usual for Gym contests, you may register for this contest 6 hours before it starts, and you will be able to virtually participate and upsolve the problems after it ends.

My thanks go to:

We kindly ask everyone who has already know the problems not to participate or discuss them before the mirror contest has ended. Hope you enjoy the problems!

UPD: Contest has ended, thanks everyone for your participation. Here is the link to the official editorial, unfortunately it is in Chinese. But feel free to ask in the comments if you have any questions about the problems.

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

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

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

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

One more proof that 300iq is Chinese

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

long awaited mirror game

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

How to solve A — Artful Paintings

  • »
    »
    12 дней назад, # ^ |
    Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

    Binary search the answer. To check the answer, notice that each condition can be transformed into an inequality involving $$$pre_{l - 1}$$$ and $$$pre_{r}$$$, where $$$pre_x$$$ denotes the number of paintings chosen from the range $$$[1, x]$$$ i.e. the prefix sum up to $$$x$$$. Moreover, we have some more inequalities involving the prefix sums itself, such as $$$pre_i \leq pre_{i + 1}$$$ and $$$pre_n = pre_0 + \text{current_answer}$$$.

    Let's say we transform all inequalities into the same type $$$pre_x + u \geq pre_y$$$, then we add a directed edge from $$$x$$$ to $$$y$$$ with cost $$$u$$$ onto a graph. Our goal is to find a negative weighted cycle, and if such cycle exists then we cannot build the prefix sum array, else we can always build one ($$$pre_x$$$ is equals to the minimum distance from $$$0$$$ to $$$x$$$).

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

      This is the intended soltion, but we have another $$$O(nm)$$$ solution without binary search.

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

        Can you elaborate?

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

          In binary search you need to check whether there is a negative cycle, so assume a cycle has the cost $$$A\times x+B$$$, we have $$$x\geq -\frac{B}{A}$$$.

          So let's just find the cycle with the minimum mean weight using some $$$O(n^2)$$$ formula.

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

      Can you please explain what does an edge from x to y with cost u signify? It is not very trivial for me to understand.

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

        If we take the shortest path from node $$$0$$$ to every other node, then the edge from $$$x$$$ to $$$y$$$ with cost $$$u$$$ enforces that $$$d(x) + u \geq d(y)$$$, where $$$d(x)$$$ is the minimum distance from $$$0$$$ to $$$x$$$.

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

      How would you transform the second rule from the problem into such an inequality $$$pre_x + u \geq pre_y$$$? How would you transform $$$pre_i \leq pre_{i + 1}$$$ into a directed edge (let u = 0)?

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

        $$$pre_{i + 1} + 0 \geq pre_i$$$, so directed edge of weight $$$0$$$ from vertex $$$i + 1$$$ to vertex $$$i$$$.

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

          Hello, sorry if this is a dumb question, but how would you transform this into such an inequality?

          The number of painted cubes whose index does not belong to the interval [Li,Ri] must not be strictly fewer than Ki (1≤i≤M2)

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

            That means the number of painted cubes in the range $$$[L_i, R_i]$$$ must be less than or equal to $$$\text{current_answer} - K_i$$$.

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

      I simulated some cases and found that it actually works but I have no idea why converting the inequalities to edges in such a way works for this problem.

      Can you suggest any article to gather some more in-depth knowledge/observations?

      Thanks

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

My submissions in this contest were moved to practice during this contest and I was unregistered. On registering again and asking for a clarification they replied that they didn't do it and It was a bug or someone else with coach rights did it. It was very displeasing and ruined the contest for me. I think it is trolling by some user which is obviously against CF rules. MikeMirzayanov please look into it. Thanks

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

Is there any editorial available (maybe, not in English)?

How to solve D?

  • »
    »
    12 дней назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    We have official editorial in Chinese.

    D can be reduced to calculate the length of a segment or a parabola using intergration.

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

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

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

Can someone tell how to solve L-LRU Algorithm

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

Will there be mirror contest for CCPC 2019 final?

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

    I don't know. The problem setters of CCPC Final this year are from Google China.

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

First time doing a Chinese contest :'(

On ABCEL, the top 5 teams had a cumulative 63 wrong submissions.

This contest had some harsh time limits.