LOLTREE - Editorial

cfea2018
dfs
dynamic-programming
medium

#1

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*=T*+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


#2

can anyone explain what is the use of prev here, like how and why it is used and how we are getting the value of parent by subtracting child’s previous and child’s current??