×

# CHEFTRVL - Editorial

Author: Yuri Shilyaev
Editorialist: Yury Shilyaev

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.

This question is marked "community wiki".

18
accept rate: 0%

19.6k349497539

1

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

(21 May, 14:16) 4★
1

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

(21 May, 15:11)
1

A nice problem that resolves to a simple solution :)
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.

(21 May, 19:39) 6★

Nice question! Any similar questions available on any platform?

(22 May, 03:22)

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

(22 May, 10:15) 4★

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

(24 May, 18:39) 6★
showing 5 of 6 show all

 4 I feel this problem deserves more explanation :( 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 :) . answered 21 May, 18:59 14.9k●1●18●56 accept rate: 18% 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. (21 May, 19:02) sorb19974★ "The proof is left as an exercise for the reader" :P Also @sorb1997, always feel free to ask if you have a doubt. It is quite likely someone will answer. (21 May, 19:46) meooow ♦6★ 1 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 (21 May, 20:16)
 1 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 answered 25 May, 13:57 4★sonu_628 346●8 accept rate: 8%
 0 @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. answered 21 May, 17:49 1 accept rate: 0%
 0 @hloga_ygrt, yeah i also can't seem to find the definition of parity anywhere below the question. answered 21 May, 19:12 21●4 accept rate: 0%
 0 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) ?? answered 26 May, 13:00 54●4 accept rate: 0%
 0 @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. answered 13 Jun, 19:05 27●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×280
×55