Editorial for COCI '07 Contest 1 #5 Srednji
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
One obvious observation is that if the median of subsequence is then the subsequence contains
.
For a subsequence , we define a function
as the difference of elements greater than
and elements smaller than
. Thus
is the median of
if and only if
contains
and
.
Furthermore, if we split into subsequences
– part that is left of
and
– part that is right of
, then
has median
if
.
This leads to the following algorithm:
For each subsequence ending with we calculate the delta function and store the number of subsequences having delta value of
in
.
For each subsequence starting with we calculate the delta function and store the number of subsequences having delta value of
in
.
To obtain the solution for each value from
, we sum
.
Comments