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

×

LOLTREE - Editorial

PROBLEM LINK:

LOLTREE

Author: Abdullah768

Editorialist: Abdullah768

DIFFICULTY:

MEDIUM

PREREQUISITES:

Dfs, Fibonacci Numbers, Dynamic Programming

PROBLEM:

Given a rooted tree T (root = node 1) with N vertices (all containing value 0), Perform Q queries of the following type and output the final tree (nodes 1 to N).

U X A B: The character ‘U’ followed by 3 integers X A B

For each query, let f be defined as

f(1)=A

f(2)=B

f(i)=f(i-1)+f(i-2)

For every node on the path from root to X (both inclusive):

T[i]=T[i]+f[level(i)]

Where level of root node is 1.

EXPLANATION:

The problem does not require intermediate results, since we only need to calculate the final tree, we need to store some lazy values during update queries so that the final tree can be built by adding all queries at once.

The update queries are nothing but Fibonacci numbers with an offset (a,b). Kth term can be calculated as:

f(k)= afib(k)+bfib(k-1)

where fib represents the Fibonacci numbers starting with 0,1

Another observation that can be made is:

f(i)=f(i-1)+f(i-2)

therefore, f(i+2)=f(i+1)+f(i)

or, f(i)=f(i+2)-f(i+1)

At every node, 2 values can be stored previous and current.

During query:

Add depth(i)th term of the given sequence in the node’s ‘current’.

Add (depth(i)+1)th term of the given sequence in the node’s ‘previous’.

After all queries:

The value to be added at the parent node can be calculated as child’s ‘previous’– child’s ‘current’.

A node can have multiple children and hence the expression would be:

(C1Prev -C1cur)+(C2Prev-C2Cur)+(C3Prev-C3Cur)+……+(CnPrev-CnCur)

Which can be re written as:

(C1Prev+ C2Prev+C3Prev+…..+CnPrev)-(C1Cur+ C2Cur+C3Cur+…..+ CnCur)

Hence, a final Dfs can be done to do the above calculations in O(n)

AUTHOR'S SOLUTION:

Author's solution Solution

This question is marked "community wiki".

asked 09 Apr, 21:18

mehul_dholiya's gravatar image

3★mehul_dholiya
242
accept rate: 0%

edited 11 Apr, 20:19

admin's gravatar image

0★admin ♦♦
18.4k348492529

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:

×2,292
×1,614
×560
×17

question asked: 09 Apr, 21:18

question was seen: 86 times

last updated: 11 Apr, 20:19