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

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

Since I didn't find a place to discuss the CCO problems, I decided to post this blog.

How to solve Day 2 Problem 3 (Good Game)?

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

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

The contest is really tough

Failed to solve anything except P1

How to do P2? I only have a O(N*10^9) solution

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

    My approach to Problem 2:

    We can reduce the problem to the following MCMF problem:

    • For each $$$1 \leq i \leq N-1$$$, there's an edge $$$(S, V_{P_i})$$$ with capacity $$$P_i$$$ and cost $$$0$$$.
    • For each $$$1 \leq i \leq N-1$$$, there's an edge $$$(V_{P_i}, T)$$$ with capacity $$$U_i$$$ and cost $$$1$$$.
    • For each $$$1 \leq i \leq N-1$$$, there's an edge $$$(V_{P_i}, V_{B_i})$$$ and $$$(V_{P_i}, V_{B_{i+1}})$$$ with capacity $$$+\infty$$$ and cost $$$0$$$.
    • For each $$$1 \leq i \leq N$$$, there's an edge $$$(V_{B_i}, T)$$$ with capacity $$$B_i$$$ and cost $$$0$$$.

    If the maxflow from source $$$S$$$ to the sink $$$T$$$ isn't equal to $$$\sum_\limits{i=1}^n V_{P_i}$$$, the answer will be simply $$$-1$$$. Otherwise, the answer is the minimum-cost maxflow to be sent from source $$$S$$$ to sink $$$T$$$.

    Consider the Successive Shortest Path algorithm ( i.e. send flow from s to t along the shortest path ). We can use a segment tree to maintain the capacity of the (only) augmenting path from vertex $$$V_{P_i}$$$ to $$$V_{P_j}$$$. Let's find the augmenting paths in increasing order of $$$i$$$. Note that if there's no augmenting path from vertex $$$V_{P_i}$$$ to $$$V_{P_j}$$$, then the vertex $$$V_{P_j}$$$ can be deleted since it cannot appear in any other paths. So we can greedily check all possible paths in the non-decreasing order of the cost. The time complexity is $$$O(N \log N)$$$.

    Code

    BTW this approach seems to be a bit overkill. Maybe there's a simpler way to find this greedy solution...

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

    Solution to P5 is as so (I got WA so there might be a mistake though):

    1. iterate through every A and while maintaining the smallest possible B

    2. to do that have 2 DSUs, one for edges in A and one for edges in B.

    3. merge components in first dsu when increasing A, split components in second dsu when decreasing B (merge in reverse order beforehand and undo one at a time)

    4. for each merge or split maintain total number of pairs by looping over all nodes in the smaller half and recalculating how many it can reach

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

Hi, I'm the author of Good Game. Here is the solution sketch I presented during CCO's solution session. (If the syntax highlighting annoys you, you may paste the text into a text editor)

hints
part 1
part 2
part 3
part 4
problem history (no spoilers)
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Thanks for your excellent task and solution sketch! I really enjoyed this problem!

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

Are there any statements of CCO 2022?

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

my Solution to P3:

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

I understood that we have to use two pointers in problem 1 of day 1. But how to detect when the directed cycle will form when we move the right pointer and when will it be broken when we remove the left pointer? Any hints on this?

Edit : Got how it that it can be done in o(n^2) by finding SCCs after moving each pointer. Curious if there if any way we can do the same thing in o(n+q)?