Here is the link to the editorial. Feel free to discuss problems and ask me questions. I'll be glad to improve the editorial with your comments.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 12:13:05 (i1).
Desktop version, switch to mobile version.
Supported by
Let’s calculate part[mask]. Take a vertex like v from the mask. Let omask be a mask excluding v (omask = mask ^ (1 << v)). We need to find the rightmost group (with the largest index) that has a vertex that has an edge toward v, name it R. Similarly, find the leftmost group (with the lowest index) that has a vertex that v has an edge toward it, name it L. If R < L, v creates a new group. Otherwise, v will merge groups [L, R] together and join them.
How is it not $$$O(2^{n} n^{2})$$$ ?
A bit weird that the essential part of Hard is optimizing from obvious $$$O(2^{n} n^{2})$$$ (try all subsets and check if it is strongly connected) to anything faster (for example different $$$O(2^{n} n^{2})$$$).
You take 1 vertex $$$v$$$, check all its edges in $$$O(n)$$$, find segment [L, R], and change labels of all the vertices in $$$O(n)$$$. Why is it $$$\Theta (2^n n^2)$$$?
Also, dfs and bfs on graphs of size $$$\leq 64$$$ work in $$$O(n)$$$, so naive solution works in $$$O(2^n n)$$$ with bad constant. So this problem is all about constant optimization. :(
So you have $$$O(2^n \cdot n)$$$ states ($$$mask$$$ and first $$$v$$$ to consider) and transitions in $$$O(n)$$$.
No, only $$$O(2^n)$$$ states. For each mask you only consider one $$$v$$$.
Which one? If you mean the first non-set, then how do we get to masks without that $$$v$$$ set? The code attached to the editorial makes two transitions: one without setting the first $$$v$$$ and one with setting that $$$v$$$, which is effectively the same as having $$$2^n \cdot n$$$ states.
The code in the editorial tries for each $$$idx$$$ from $$$0$$$ to $$$n - 1$$$ two options: either to take it in our subset or not. Are you saying that full binary tree of depth $$$n$$$ has $$$2^n n$$$ vertices?
Ok, you're right, my bad.
CardboardBoxes:
While this is technically correct, a better bound (which matches the code below) is $$$O(\sqrt S)$$$. This is important because $$$S \leqslant 10^{13}$$$, so a linear solution would have timed out.
Hi. Thank you for reporting the issue. Im fact in the initial version of editorial it's correct, the issue appeared during transferring editorial to the blog. I'll ask team to fix it.
I have another incentive of Div1 250. Here, if we draw a net of a cardboard box, it's a complete rectangle!
For anyone struggling with Div 1 hard, particularly the latter part of the editorial:
Let's try to count the SCCs in the large graph and somehow connect that to the SCCs in the small (input) graph. I think of the nodes in the big graph arranged in the leaves of an imaginary N-ary tree (where N = b), with height k, so the path from the root to every leaf gives you the label for that leaf.
Property: Let L_u be the set of leaf nodes in the sub-tree of u. Then if v1 and v2 are siblings, from the standpoint of every node in L_v1, every node in L_v2 "looks the same" and vice versa. That means either everyone in L_v1 has directed edges to everyone in L_v2, or the same thing in the opposite direction.
Now take any subset of nodes in the large graph. We're going to reason about when this subset is an SCC. Metaphorically "select" the nodes from the subset, in the above N-ary tree. Now keep going up the tree until you reach the lowest common ancestor among all of the "selected" nodes. Take those children of this ancestor which lead to some selected leaf (i.e. which are themselves an ancestor of at least one selected node). Let's call this subset ANCESTORS. Remember the tree is a "B-ary" tree, therefore elements of ANCESTORS each are digits from 0 to b. Now the subset that you had selected is an SCC if and only if ANCESTORS is an SCC in the small graph: If ANCESTORS make an SCC in the small graph, with the property that the nodes in L_u "look the same" to L_v (with u and v being siblings), you can go from any L_a to any L_b (for a != b and a, b in ANCESTORS). For a = b we can do complete induction on the height of a node (with the base case of any single node being an SCC). If the selected nodes make an SCC, then there should be a way to go from all L_a's to L_b's (a, b in ANCESTORS). We know L_a is connected to L_b (=all nodes in L_a are connected to all nodes in L_b) in the large graph iff we a is connected to b in the small graph (from the problem statement). Therefore ANCESTORS is an SCC in the small graph.
Therefore all that matters is choosing subsets of nodes from the above tree, but keeping track of the set ANCESTORS each time. However as far as the counting is concerned, all of the ANCESTORS sets of the same size in the same level of the tree look the same: the moment you fix the elements of the ANCESTORS the SCC-ness is fixed.
Therefore whenever you find an SCC subset in the small graph, you'll ask "How many ANCESTORS sets are there in the graph with this many elements? Add that many to the total count of induced SCCs of the large graph".
One last thing which may be obvious: be careful when exponentiating 2 to a power which is itself a modulo'd power: a^(p — 1) = 1 mod p, therefore the behavior of the exponentiation of a repeats every p — 1 steps (rather than p). Therefore the exponent must be calculated modulo p — 1.