Editorial for COCI '15 Contest 5 #3 Perica

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.

We need to calculate how many times each number from the input appears as the largest of K numbers in every combination. If we sort the numbers in ascending order, we can see that this number is going to be maximal in an array of K numbers if all other numbers are located to its left. Therefore, the i^\text{th} number is maximal the exact number of times as the number of ways to choose K-1 numbers out of the first i numbers. If we denote the number of ways to choose K numbers out of N numbers as f(n, k), then it is easy to see that f(n, k) = f(n-1, k)+f(n-1, k-1).

Using this relation, we can calculate each f(n, k).

The solution is therefore the sum of the product of the corresponding f(i, k-1) and v[i], where v[i] is the value on that location.


There are no comments at the moment.