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.

One obvious observation is that if the median of subsequence is $B$ $B$ then the subsequence contains $B$ $B$ .

For a subsequence $P$ $P$ , we define a function $\delta(P)$ $δ (P)$ as the difference of elements greater than $B$ $B$ and elements smaller than $B$ $B$ . Thus $B$ $B$ is the median of $P$ $P$ if and only if $P$ $P$ contains $B$ $B$ and $\delta(P) = 0$ $δ (P) = 0$ .

Furthermore, if we split $P$ $P$ into subsequences $P_L$ $P_{L}$ – part that is left of $B$ $B$ and $P_R$ $P_{R}$ – part that is right of $B$ $B$ , then $P$ $P$ has median $B$ $B$ if $\delta(P_L) + \delta(P_R) = 0$ $δ (P_{L}) + δ (P_{R}) = 0$ .

This leads to the following algorithm:

For each subsequence ending with $B$ $B$ we calculate the delta function and store the number of subsequences having delta value of $d$ $d$ in $L(d)$ $L (d)$ .

For each subsequence starting with $B$ $B$ we calculate the delta function and store the number of subsequences having delta value of $d$ $d$ in $R(d)$ $R (d)$ .

To obtain the solution for each value $d$ $d$ from $[-N, N]$ $[- N, N]$ , we sum $L(d) \times R(-d)$ $L (d) \times R (- d)$ .

Comments

There are no comments at the moment.