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

×

TREEEE - Editorial

PROBLEM LINK:

Practice

Contest

Author: Akshay Venkataramani

Tester: Timothy Jeyadoss

DIFFICULTY:

Easy-Medium

PREREQUISITES:

XOR Property, Graphs, BFS/DFS

EXPLANATION:

The optimal answer can be reached, only if we perform the operation starting from the root till the leaf. Any other sequence of operations will affect previously produced answer, and hence this observation is crucial.

Hence we perform a depth-first-traversal (also known as depth-first-search (DFS)) on the tree, and if we find that a node has a value different from its target, we increment our overall answer.

We need to maintain two variables - each for odd and even heights respectively. Let us store it an array of 2 variables(named as parity in Author's solution). Both parity[0] and parity[1] are initialized to zero.

This is essential due to the following reason :

Consider a tree with root 1 , and 3 being its granchild . In this tree, if both 1 and 3 have initialValues not equal to targetValues, performing the operation once(on node 1) is enough for node 3 to also have its value flipped(i.e., to the target value).

In the author's solution, the height of root is set at 1 and the remaining nodes' heights are set appropriately.

Hence, during the dfs, we check for two things :-

1) Let x be the height of the current node. if parity[x%2] == 0, it means that the current node has no effective flips in it, i.e., its current value is equal to its initial value. If initialValue[currentNode] is not equal to target[currentNode] , we incremement overall answer, and do parity[x%2]=(parity[x%2]+1)%2 . Try to understand why this step is done by yourself, using pen or paper and by constructing various trees, before moving to the next part.

2) The next part should be simple, if you understood the first part well. If parity[x%2]==1, it means there's an effective flip waiting in the currentNode. Hence, if initialValue[currentNode]==target[currentNode], the effective flip waiting to be performed on the current node is done. When we perform it, the value is no longer equal to target. Hence, we need to increment overall answer and also do parity[x%2]=(parity[x%2]+1)%2.

Third case -> parity[x%2] == 0 and initialValue[currentNode] == target[currentNode]. Here, we needn't do anything and leave it as such.

Fourth Case -> parity[x%2] == 1 and initialValue[currentNode] != target[currentNode]. Here, we needn't do anything again and leave it as such. This is because, the effective flip remaining in the node, when performed, makes the values equal.

AUTHOR'S SOLUTION:

Author's solution can be found here.

TESTER'S SOLUTION:

Tester's solution can be found here.

This question is marked "community wiki".

asked 21 Jan '18, 17:26

akshayvenkat97's gravatar image

5★akshayvenkat97
1.1k416
accept rate: 0%

edited 05 Feb '18, 13:55

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×15,683
×1,672
×726
×303
×29
×3

question asked: 21 Jan '18, 17:26

question was seen: 347 times

last updated: 05 Feb '18, 17:39