Editorial for DMOPC '20 Contest 4 P6 - Petty Children
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
This subtask was meant to reward brute-force solutions.
Time Complexity:
Subtask 2
Observe that the answer is always . We provide a proof later.
Since the answer is always , we can reduce this problem to a system of equations in
. Our solution is a vector
, that is to say, a binary vector. We have
cases:
- If the degree of a node is even and our colour is
, then the number of
s must be even, that is, the right side of our equation must be
.
- If the degree of a node is even and our colour is
, then the number of
s must be even, so the number of
s must be even, so the right side of our equation must be
.
- If the degree of a node is odd and our colour is
, then the number of
s must be even, so the right side of our equation is
.
- If the degree of a node is odd and our colour is
, then the number of
s must be odd, so the right side of our equation is
.
If we represent the system with a matrix, and start with as the adjacency matrix, we can set
and
if
is odd, and
otherwise, where
is a vector representing the right side of our equation.
In fact, , and
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 and the right side reduces to a non-zero number. Since we are operating in
, this is simply a subset.
Let be the rows chosen. Since the left side is zero, we have
, and similarly for any other column. Then:
But we have , so:
but this is just the XOR of the diagonals, which is just the right side of our equation, and we see that it equals .
We conclude that this system is consistent.
We can solve this system in with Gauss-Jordan.
Time Complexity:
Subtask 3
We can optimize the previous solution with a bitset.
Time Complexity:
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 .
Note 3: Fast I/O is very helpful on this problem, since there can be lines.
Comments
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.
Your solution is not
. However, yes, this problem can be solved with XOR basis.
Oh, yes, I didn't noticed, fixed now, thanks.