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)$ ~\mathcal O(N \times 2^N)~

Subtask 2

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

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

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

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

In fact, $\vec{b} = diag(A)$ ~\vec{b} = diag(A)~, and $A$ ~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}$ ~\vec{0}~ and the right side reduces to a non-zero number. Since we are operating in $\mathbb{Z}_2$ ~\mathbb{Z}_2~, this is simply a subset.

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

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

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

$\displaystyle A_{R_1R_1} \oplus A_{R_2R_2} \oplus \dots \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$ ~0~.

We conclude that this system is consistent.

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

Time Complexity: $\mathcal O(N^3)$ ~\mathcal O(N^3)~

Subtask 3

We can optimize the previous solution with a bitset.

Time Complexity: $\mathcal O(N^3)$ ~\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$ ~63~.

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

Comments

3

humbertoyusta commented on March 15, 2021, 9: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.

1

Riolku commented on March 16, 2021, 1:54 a.m.

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

1

humbertoyusta commented on March 16, 2021, 3:07 p.m.

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