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)$ ~\delta(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$ ~\delta(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$ ~\delta(P_L) + \delta(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.