Qingyu's blog

CCO 2022 Discussion?
By Qingyu, history, 2 years ago, In English

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

Tags cco
  • Vote: I like it
  • +100
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
2 years ago, # |
  Vote: I like it +10 Vote: I do not like it

The contest is really tough

Failed to solve anything except P1

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

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

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

    → Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    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

    → Reply
»
2 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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)
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Are there any statements of CCO 2022?

→ Reply
»
2 years ago, # |
← Rev. 6   Vote: I like it +3 Vote: I do not like it

my Solution to P3:

Spoiler
→ Reply
»
2 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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

→ Reply