C
The question
Summary of the question: The goal is to count the number of brilliant consecutive subarrays of a given array. What is a brilliant array? an array (that now is no more important if set or array) from which we can arrive at a set of consecutive numbers by taking the mean of two elements in the set (the procedure may obviously be repeated several times). The length of the given array does not exceed 4x1e5.
Initial thoughts:
- just counting the number of these subsets is important, not determining them.
- It is interesting thing to notice that a produced number is always the average of 2, 4, 8, … numbers in the set (if we use the same number n times, we count it n times! for example, if we have a,b,c in the set and then (a+b)/2=d and then (d+c)/2=e, then e is actually (a+b+c+c)/4)
- we know what are the lowest and highest numbers in the set, and producing numbers between min and max and like producing numbers, only shifted, between 0 and max-min. Shifting does not change the brilliance of a set!
Post-initial thoughts:
B
The question Solved; revision on the algorithm to add …