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)?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 156 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Название |
---|
The contest is really tough
Failed to solve anything except P1
How to do P2? I only have a O(N*10^9) solution
My approach to Problem 2:
We can reduce the problem to the following MCMF problem:
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)$$$.
BTW this approach seems to be a bit overkill. Maybe there's a simpler way to find this greedy solution...
Solution to P5 is as so (I got WA so there might be a mistake though):
iterate through every A and while maintaining the smallest possible B
to do that have 2 DSUs, one for edges in A and one for edges in B.
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)
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
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)
Thanks for your excellent task and solution sketch! I really enjoyed this problem!
Are there any statements of CCO 2022?
day1 day2
You can also find them on DMOJ: https://dmoj.ca/problems/?search=%2722&show_types=1&category=24
my Solution to P3:
treat each alternating run (eg. ababab) as a block type 1 (block1) with value equal to length
each run of the same character (eg. aaa) is a block type 2 (block2) with value equal to 1
the problem is then as follows:
a block1 i can collide with block i-2 or block i+2 when this happens, both lose one value. when a block has value 0 it explodes and dies. (what you are actually doing is removing the block2 in the middle and immediately forming a new one eg. abab aaaa bab -> aba bb ab)
a block2 at the start or end can be removed (consumed by the void)
you need to destroy all blocks
note
no block1s will ever be in direct contact. if they were so at the beginning, they would just be considered one block1. there is no way to destroy all block2s between 2 block1s without destroying at least one of the block1s first
you only need to destroy all block1s. block2s left over can be dropped into the void at the end.
if you are successful, the last operation will always be to drop a block2
the only way to destroy a block1 is to annihilate it with other blocks.
what blocks can you collide block i with? all except i-1,i,i+1
let x_i=(value of block i) — (sum of blocks it can collide with)
note that block i-1,i+1 must be block2s
so x_i=-(sum of all blocks) + 2(value of block i) — number of neighbors
if you manage always keep all x<=0, all block1s will be removed
if any x>0 at any point, you've failed
strategy 1: always collide the block with the largest x_i — does this work?
in each move, largest x stays the same, rest can increase by at most 2
so if all x<=0 initially, there must be at least 2 x>=-1 at some point to fail
there can also be at most 2 such x or else the sum of x is too high
the 2 x must not have distance of 2 (eg. ...x1x...), or you can collide both at once
when can this happen?
x11x for any x>=1
^ if you never reach this case, strategy 1 is optimal
strategy 2: - assume both ends are block1s. otherwise, x11x is impossible and strategy 1 works
let y=sum of endpoints — sum of nonendpoints -1
if y>=-1, collide the larger endpoint
then y does not increase
if y<=0 initially, y never >0
so you will never get to x11x
also, x_i<=0 is maintained
if y<-1, follow strategy 1
if y>0 initially failure is inevitable
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)?