Editorial for COCI '08 Contest 2 #5 Setnja

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Suppose that the root of the tree is not labeled $1$ $1$ , but with an arbitrary label $x$ $x$ .

For some $x$ $x$ , let $f_i(x)$ $f_{i} (x)$ be the value of all paths in the set described by the substring of the input starting with the $i^\text{th}$ $i^{th}$ character.

The following recursive relations hold:

$f_i(x) = f_{i+1}(x)$ $f_{i} (x) = f_{i + 1} (x)$ ; if the $i^\text{th}$ $i^{th}$ character is P (we stay in the root of the tree, with value $x$ $x$ )
$f_i(x) = f_{i+1}(2x)$ $f_{i} (x) = f_{i + 1} (2 x)$ ; if the $i^\text{th}$ $i^{th}$ character is L (we move to the left child, with value $2x$ $2 x$ )
$f_i(x) = f_{i+1}(2x+1)$ $f_{i} (x) = f_{i + 1} (2 x + 1)$ ; if the $i^\text{th}$ $i^{th}$ character is R (we move to the right child, with value $2x+1$ $2 x + 1$ )
$f_i(x) = f_{i+1}(x) + f_{i+1}(2x) + f_{i+1}(2x+1)$ $f_{i} (x) = f_{i + 1} (x) + f_{i + 1} (2 x) + f_{i + 1} (2 x + 1)$ ; if the $i^\text{th}$ $i^{th}$ character is *

The base case is the empty substring – $f_{N+1}(x) = x$ $f_{N + 1} (x) = x$ .

The recursive formulas are linear, meaning that we only add constants or multiply by them. Because of this every term $f_i(x)$ $f_{i} (x)$ can be written in the form $f_i(x) = A_i x + B_i$ $f_{i} (x) = A_{i} x + B_{i}$ .

The above recursive formulas can then be rewritten as:

$f_i(x) = A_{i+1} x + B_{i+1}$ $f_{i} (x) = A_{i + 1} x + B_{i + 1}$
$f_i(x) = A_{i+1} (2x) + B_{i+1} = (2A_{i+1})x + B_{i+1}$ $f_{i} (x) = A_{i + 1} (2 x) + B_{i + 1} = (2 A_{i + 1}) x + B_{i + 1}$
$f_i(x) = A_{i+1} (2x+1) + B_{i+1} = (2A_{i+1})x + (A_{i+1}+B_{i+1})$ $f_{i} (x) = A_{i + 1} (2 x + 1) + B_{i + 1} = (2 A_{i + 1}) x + (A_{i + 1} + B_{i + 1})$
$f_i(x) = A_{i+1} x + B_{i+1} + A_{i+1} (2x) + B_{i+1} + A_{i+1} (2x+1) + B_{i+1} = (5A_{i+1})x + (A_{i+1}+3B_{i+1})$ $f_{i} (x) = A_{i + 1} x + B_{i + 1} + A_{i + 1} (2 x) + B_{i + 1} + A_{i + 1} (2 x + 1) + B_{i + 1} = (5 A_{i + 1}) x + (A_{i + 1} + 3 B_{i + 1})$

The output is $f_1(1) = A_1 1 + B_1$ $f_{1} (1) = A_{1} 1 + B_{1}$ .

We can use dynamic programming to calculate the sequences $A$ $A$ and $B$ $B$ . Because the terms in the sequences can get large, it is required to implement big integer arithmetic supporting long addition.

Comments

There are no comments at the moment.