You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFTRVL - Editorial

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.

This question is marked "community wiki".

asked 20 May, 16:17

hloya_ygrt's gravatar image

3★hloya_ygrt
17
accept rate: 0%

edited 21 May, 17:26

admin's gravatar image

0★admin ♦♦
19.0k348495531

1

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

(21 May, 14:16) divik5444★
1

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

(21 May, 15:11) hloya_ygrt3★
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) meooow ♦6★

Nice question! Any similar questions available on any platform?

(22 May, 03:22) thegeniushead1★

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) divik5444★

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

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

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

link

answered 21 May, 19:51

sudip_95's gravatar image

4★sudip_95
7556
accept rate: 10%

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 :) .

link

answered 21 May, 18:59

vijju123's gravatar image

5★vijju123 ♦
13.6k11036
accept rate: 19%

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) vijju123 ♦5★

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

link

answered 25 May, 13:57

sonu_628's gravatar image

4★sonu_628
3288
accept rate: 8%

edited 25 May, 18:05

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

link

answered 21 May, 17:49

staystrong's gravatar image

3★staystrong
1
accept rate: 0%

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

link

answered 21 May, 19:12

sanchit1999's gravatar image

5★sanchit1999
11
accept rate: 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) ??

link

answered 26 May, 13:00

prnjl_rai's gravatar image

4★prnjl_rai
1
accept rate: 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.

link

answered 13 Jun, 19:05

ciphereck's gravatar image

5★ciphereck
172
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×255
×55

question asked: 20 May, 16:17

question was seen: 943 times

last updated: 13 Jun, 19:05