CHEFTRVL - Editorial

general
,
1

PROBLEM LINK:

Practice
Contest

Author: Yuri Shilyaev
Tester: Hasan Jaddouh
Editorialist: Yury Shilyaev

DIFFICULTY:

Easy-medium.

PREREQUISITES:

Xor operation, dfs.

PROBLEM:

You are given a tree with N vertices and N - 1 edge. Each vertex i has a value a_i associated with it. You have to count the number of unordered pairs (u, v), that the parity of the number of one-bits in a_u \oplus a_v is not equal to the parity of the shortest path between u and v.

QUICK EXPLANATION:

Let’s use the fact that parity of the number of one-bits a_u \oplus a_v will not change if we replace a_u with parity of one bits in a_u.

EXPLANATION:

Let |x| be the number of one-bits in binary representation of x, dist(u, v) be the length of the shortest path between u and v, and x\ \%\ 2 be the remainder of the division x by two.

It is easy to prove the fact, that |a_u \oplus a_v|\ \%\ 2 = (|a_u|\ \%\ 2) \oplus (|a_v|\ \%\ 2). To use it, let’s transform b_i = |a_i|\ \%\ 2.

Now the task is the following: count the number of pairs (u, v), that b_u \oplus b_v \neq dist(u, v)\ \%\ 2. If we had rooted our tree, calculated for each v it’s dist(root, v) (the number of edges in the path from the root), then:

dist(u, v)\ \%\ 2 = (dist(root, u)\ \%\ 2) \oplus (dist(root, v)\ \%\ 2).

That’s why we apply transform d_i = dist(root, i) \ \%\ 2 for array d and reduce a problem to an easy one: count the number of pairs (u, v), such that b_u \oplus b_v \neq d_u \oplus d_v.

By transfering everything to the left we achieve:

b_u \oplus b_v \oplus d_u \oplus d_v = 1

Easy problem, right? Let’s just calc cnt[bvalue][dvalue] - number of vertices with b_u = bvalue and d_u = dvalue, and iterate all possible pairs of bvalue and dvalue that give xor 1, and add cnt[bvalue_u][dvalue_u] \cdot cnt[bvalue_v][dvalue_v] to the answer.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

1 Like
2

what does in particular “parity” mean? I am even having trouble understanding problem statement due to this.

1 Like
3

It was commented under the problem that parity is 1 or 0, is the number even or odd.

1 Like
4

@hloga_ygrt Can you please state clearly, where under the problem is the definition of parity mentioned. I’m sorry I’m not able to find it.

5

I feel this problem deserves more explanation :frowning:

Like, -

“Let’s use the fact that parity of the number of one-bits a_u \oplus a_v will not change if we replace a_u with parity of one bits in a_u.”

What does this mean? Are you intending to say that we are replacing a_u with "Parity of 1's in a_u" ? If yes, then why does this work? Do you have a proof of correctness, or is it some random observation we had to make?

I agree that strong practice gives you a killer instinct of making observations, but a formal proof and explanation helps newbies to learn that thing and grasp the concept. I hope you understand what I am trying to convey :slight_smile: .

4 Likes
6

Yes I read the editorial twice but did not get it. Then I thought it’s just me and may be I am not smart enough. In my opinion, CHEFLAKE also needs a better explanation.

7

@hloga_ygrt,
yeah i also can’t seem to find the definition of parity anywhere below the question.

8

A nice problem that resolves to a simple solution :slight_smile:
However it is worth mentioning that both author and tester solutions here use a slightly different approach than the one described in the editorial, in case someone gets confused.

1 Like
9

“The proof is left as an exercise for the reader” :stuck_out_tongue:

Also @sorb1997, always feel free to ask if you have a doubt. It is quite likely someone will answer.

10

This is the best explanation of this problem I think.

Courtesy: Silence_ for_Melody (CF)

Comment Link(Codeforces)

I will give you the theory behind and you have to figure it out, sorry for my English since now.

You must know some properties about trees and XOR operation.

  1. Given a rooted tree, a Lowest Common Ancestor of two nodes u,v is a node w which is an ancestor of u and v and its height (measured from root – root has height 0, his direct neighbors had height 1 and so on) is as big as possible. This node w could be equal to u or v. For more information, you can check this tutorial. We will not use this but the concept is part of understanding my solution.

  2. A well know problem to apply LCA is to find distance between any pair of nodes in a tree. You can try it here. The property said that dist(u, v) = dist(root, u) + dist(root, v) - 2 * dist(root, lca(u, v)). Please stop here if you do not completely understand this part. Draw a tree in a paper and prove it by yourself. This is important.

  3. Sum of a list numbers mod 2 is the same to take XOR between the mod 2 of each of them. Again, to be convinced about this do some test in paper and continue.

  4. A XOR A = 0. This is something that you can apply to get XOR of a continuous subarray of array A. You can preprocess XOR of prefixes in XA, so XA[i] = “xor of all the elements until i”. Then, to get xor from itoj just calculate XA[j] xor XA[i - 1]. Again, do some test in paper to understand why this works.

  5. Now let us combine all above. If we define XORDIS as distance between two nodes where the distance is the xor of the lengths of edges in their path, how would you calculate that using concepts of LCA and XOR of prefixes? (Hint: you will not need to calculate LCA).

For one moment forget about ages in the problem and try to solve the following: How many pairs of cities are so their distance is even? How many there are so their distance is odd?

Now forget about the distance on work over ages. How many pairs of cities there are so the bits in their XOR are even? How many there are so the bits in their XOR are odd?

Last, and what makes this problem awesome, observation: When you want to evaluate parity of bits in the XOR of A and B, does the order of bit in A and B matter? Just think about it. Hope everything is clear

5 Likes
11

The proof is left as an exercise for the reader :P

There was a nice come back to it in past. Lemme copy it-

Why not leave entire editorial as an exercise for readers :) xD

I believe yes, its good to leave exercises for readers, but if I were there, I’d at least give some hints or the answer in my bonus part of editorial :3

IDK as an editorialist I feel restless elsewise XD

1 Like
12

Nice question!
Any similar questions available on any platform?

13

Explanation about parity is given neither in problem nor in comments under the problem and although setter commented but still i don’t get it what is parity implying here? “parity of number of one bits”, “parity of shortest path” what does these clauses imply???

14

@divik544 you can consider parity of x as x mod 2. Wiki page: parity

15

Root the tree at 1 and run simple dfs to calculate dept of each node

let x[i] be number set bits in a[i] \oplus a[1]

now we divide all nodes 2 catogories

  1. where parity of dept[i] and x[i] is same - c1

  2. where parity of dept[i] and x[i] is is different - c2

consider a node of c2, right now with a1 he has parity of distance and difference in bits, as different and he wants that to remain the same, So he wants to be paired with someone who has either

a) parity of dept[i] and x[i] both are 0. pairing with them will not any effect on overall parity

b) parity of dept[i] and x[i] both are 1, pairing with them will result with inverting the parity of both (dept[i] and x[i]), but since in a node of c2 it was different before, it will different after pairing also.

Clearly, both are attributes of nodes of c1 . Hence every node of c2 can be paired with c1. So the answer is simply c1*c2

Solution link

1 Like
16

From Editorial : bu⊕bv⊕du⊕dv=1 .
Can we proceed further in this way ? - bu and du is known and so are bv and dv. now store bi⊕di for each i and count the number of ones (cnt1) and zeros (cnt0) in the array thus formed. and the answer is (cnt0*cnt1) ??

17

@sonu_628
That’s the algorithm you explained. But why it worked in the first place, please can you explain that.
And what led to you this algorithm of using distance from root and set bit in a[i]^a[1], please can you expplain that.