Editorial for Champion Contest

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.

Author: magicalsoup

There are several ways to approach this problem. I will be explaining one of them.

Since $N$ $N$ is quite big, we cannot do a simple brute-force $\mathcal O(N^2)$ $O (N^{2})$ solution.

The solution is to sort the array, and binary search for the farthest indexed champion which the current champion can defeat. This is an $\mathcal O(N \log N)$ $O (N \log N)$ solution.

We can precompute an array of $friends[]$ $f r i e n d s []$ , where the $i^\text{th}$ $i^{th}$ index of the $friends[]$ $f r i e n d s []$ array will keep the number of champions that has a lower strength value than the $i^\text{th}$ $i^{th}$ champion. This way, when calculating the number of champions the current champion can defeat, all we need to do is binary search, then subtract $friends[i]$ $f r i e n d s [i]$ , where $i$ $i$ is the current champion.

Time Complexity: $\mathcal O(N \log N)$ $O (N \log N)$

Comments

There are no comments at the moment.