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