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

This subtask was meant to reward brute-force solutions.

Time Complexity:

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:

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.

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

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

Your solution is not . However, yes, this problem can be solved with XOR basis.

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

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

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

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

Fixed, thanks