Arpa's blog

By Arpa, history, 4 years ago, In English

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.

  • Vote: I like it
  • +13
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it
Part of editorial

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})$$$).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So you have $$$O(2^n \cdot n)$$$ states ($$$mask$$$ and first $$$v$$$ to consider) and transitions in $$$O(n)$$$.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, only $$$O(2^n)$$$ states. For each mask you only consider one $$$v$$$.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ok, you're right, my bad.

»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

CardboardBoxes:

So possible options of width + length are divisors of S / 2. We can find divisors of S / 2 in O(S).

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I have another incentive of Div1 250. Here, if we draw a net of a cardboard box, it's a complete rectangle!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.