Editorial for COCI '15 Contest 2 #5 Vudu

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.

In this task, we need to find the number of consecutive subsequences such that the average value is \ge P.

To begin with, it is important to notice that, if we subtract the value P from each number, we have reduced the task to finding the number of consecutive subsequences such that their sum is non-negative.

Therefore, now the task is to find the number of consecutive subsequences that have the sum of values non-negative in the sequence of numbers. We can do this in two ways, one of which will be described here, while the official solution implements the other.

Let pref(x) be the sum of the first x elements in the transformed sequence. It is easy to see that the sum of elements in the interval [L, R] = pref(R)-pref(L-1). Because we are searching for a number in the interval [L, R], we can calculate how many positions L there are so that the sum in the interval [L, R] is non-negative for each R. Therefore, for each pref(R) we ask how many pref(L-1) there are such that L \le R and pref(R) \ge pref(L-1). If we imagine that we are moving from left to right in the array, for each R we need to be able to answer how many pref(L-1) \le pref(R), L \le R there are.

Because we only want to know about the relative order between the prefix sums, we can hash the value of each prefix sum and convert it to a single number from the interval [0, N), depending on their relative order. The hashing needs to be implemented in order to efficiently answer queries using a data structure. The simplest data structure to implement that enables inserting number X and querying how many numbers smaller than Y there are is the Fenwick tree data structure. For details about this data structure, consult https://wiki.xfer.hr/logaritamska_tutorial/. (DMOJ curator note: Good luck reading this.)


There are no comments at the moment.