## Editorial for DMOPC '20 Contest 4 P6 - Petty Children

**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:

#### 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.

There is a spelling error b should be be.

Fixed, thanks