Editorial for COCI '14 Contest 2 #6 Norma
Submitting an official solution before solving the problem yourself is a bannable offence.
The goal of this task is, for each two integers and , calculate the price of the subsequence of input array and to sum up the given values. Let us imagine that we are moving the right bound from left to right and maintaining the array of solutions for current , so that at position of that array, call it array , there is the price of subsequence .
A high-level algorithm would look like this:
initialize array T to 0
solution = 0
for B from 1 to N
subsequences are expanded from [A, B-1] to [A, B] by adding X[B]
therefore refresh values in array T at positions 1 to B
add to the solution T[1] + T[2] + … + T[B]
Let's imagine that every member of array internally contains values , and , minimal number of sequence , maximal number of sequence and length of subsequence , respectively.
We need to have an efficient update of values (prices) in array . Since the value of a member is the product of its internal values, let us observe how these are changing when incrementing by (moving to the right). Values of each member with index smaller than or equal to are incremented by .
Let be the position of the rightmost member of array that is to the left of such that it holds . Value of all members of array at position from the interval will be left unchanged while the value of all members of array on positions from the interval will become exactly .
Similarly, be the position of the rightmost member of array that is to the left of such that it holds . Value of all members of array at position from the interval will be left unchanged while the value of all members of array on positions from the interval will become exactly .
Therefore, it is necessary to implement a data structure that will allow the following operations:
- - increment value by to all members of the array at position from the interval .
- - set value to to all members of the array at position from the interval .
- - set value to to all members of the array at position from the interval .
- - return the sum of products of values , and of all the members of the array at position from the interval .
It turns out that the required operations can be efficiently achieved using a tournament tree. For this purpose, every node of the tree must contain the following values:
- - length of the interval of members of the array that the node is covering, for example, for leaves it holds
- - sum of values of all members from the interval
- - sum of values of all members from the interval
- - sum of values of all members from the interval
- - sum of values of all members from the interval
- - sum of values of all members from the interval
- - sum of values of all members from the interval
- - sum of values of all members from the interval
How would incrementing values to all members from the interval belonging to the node of the tree look like?
It is necessary to suitably change the value of each node in the following way:
Let's observe how setting values to all members from the interval belonging to the node of the tree looks like:
And, finally, setting values to all members from the interval belonging to the node of the tree:
Because of the fact that all values in the nodes are sums, merging two nodes of a child for the purpose of calculating values of the parent node is simply the summation of the corresponding values from both nodes.
The nature of mentioned operations on the structure is such that it is necessary to use tournament tree with propagation. The details of this expansion are general and left out from this description, but can be looked up in the attached code.
We are still left with efficiently finding the rightmost smaller or larger number than the current . This can be simply implemented using a stack. Here we will describe finding the rightmost smaller value that is to the left of , and finding the rightmost larger value is done in a similar manner.
If we take into consideration that is being moved from left to right, from to , then we are actually talking about the last member of array that we passed, and is smaller than . For each from the stack, we will pop all the numbers larger than or equal to since from now on they can't ever be someone's last smaller number ( is smaller than them and is located after them). After that, the stack's peak will be exactly the member of array that we were looking for, the last one smaller than . Before incrementing and moving to the right, we push on the stack. The given algorithm is of linear complexity because each member of the array is pushed and popped from the stack at most once.
All operations on tournament tree are of the complexity , and they are done times, so the total complexity of this solution is .
Comments