Editorial for DMOPC '20 Contest 4 P6 - Petty Children


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Riolku

Subtask 1

This subtask was meant to reward brute-force solutions.

Time Complexity: \mathcal O(N \times 2^N)

Subtask 2

Observe that the answer is always N. We provide a proof later.

Since the answer is always N, we can reduce this problem to a system of equations in \mathbb{Z}_2. Our solution is a vector \mathbb{Z}_2^N, that is to say, a binary vector. We have 4 cases:

  • If the degree of a node is even and our colour is 1, then the number of 1s must be even, that is, the right side of our equation must be 0.
  • If the degree of a node is even and our colour is 0, then the number of 0s must be even, so the number of 1s must be even, so the right side of our equation must be 0.
  • If the degree of a node is odd and our colour is 1, then the number of 1s must be even, so the right side of our equation is 0.
  • If the degree of a node is odd and our colour is 0, then the number of 1s must be odd, so the right side of our equation is 1.

If we represent the system with a matrix, and start with A as the adjacency matrix, we can set A_{ii} = 1 and \vec{b}_i = 1 if deg(i) is odd, and A_{ii} = \vec{b}_i = 0 otherwise, where \vec{b} is a vector representing the right side of our equation.

In fact, \vec{b} = diag(A), and A is symmetric.

We want to prove that this system is consistent. If the system is inconsistent, there exists a linear combination of rows such that the left side reduces to \vec{0} and the right side reduces to a non-zero number. Since we are operating in \mathbb{Z}_2, this is simply a subset.

Let R_1, R_2, \ldots, R_k be the rows chosen. Since the left side is zero, we have A_{R_1R_1} \oplus A_{R_2R_1} \oplus \ldots \oplus A_{R_kR_1} = 0, and similarly for any other column. Then:

\displaystyle A_{R_1R_1} \oplus A_{R_2R_1} \oplus \ldots \oplus A_{R_kR_1} \oplus A_{R_1R_2} \oplus A_{R_2R_2} \oplus \ldots \oplus A_{R_kR_2} \oplus \ldots \oplus A_{R_1R_k} \oplus A_{R_2R_k} \oplus \ldots \oplus A_{R_kR_k} = 0

But we have A_{ab} = A_{ba}, so:

\displaystyle A_{R_1R_1} \oplus A_{R_2R_2} \oplus \ldots \oplus A_{R_kR_k} = 0

but this is just the XOR of the diagonals, which is just the right side of our equation, and we see that it equals 0.

We conclude that this system is consistent.

We can solve this system in \mathcal O(N^3) with Gauss-Jordan.

Time Complexity: \mathcal O(N^3)

Subtask 3

We can optimize the previous solution with a bitset.

Time Complexity: \mathcal O(N^3)

Note 1: It seems like if you write your functions well and compile with -O3 or above, sometimes C++ will just... optimize it into a bitset for you.

Note 2: This problem is solvable in PyPy, if you use a custom bitset, with your bitset size equal to 63.

Note 3: Fast I/O is very helpful on this problem, since there can be 2 \times 10^6 lines.


Comments


  • 3
    humbertoyusta  commented on March 15, 2021, 5:56 p.m. edited

    This problem can also be solved using the same idea from the editorial, but implementing it with xor-basis, which is easier to code, a good related tutorial on this technique can be found here.

    Thanks for the contest, some problems were pretty interesting.


    • 2
      Riolku  commented on March 15, 2021, 9:54 p.m.

      Your solution is not \mathcal O(N^2). However, yes, this problem can be solved with XOR basis.


      • 1
        humbertoyusta  commented on March 16, 2021, 11:07 a.m.

        Oh, yes, I didn't noticed, fixed now, thanks.


  • 2
    Tony1234  commented on March 15, 2021, 9:04 a.m.

    If the degree of a node is even and our colour is 0, then the number of 0s must be even, so the number of 1s must b even, so the right side of our equation must be 0.

    There is a spelling error b should be be.


    • 1
      4fecta  commented on March 15, 2021, 11:01 a.m.

      Fixed, thanks