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)$ ~\mathcal 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)$ ~\mathcal O(N \log N)~ solution.

We can precompute an array of $friends[]$ ~friends[]~, where the $i^\text{th}$ ~i^\text{th}~ index of the $friends[]$ ~friends[]~ array will keep the number of champions that has a lower strength value than the $i^\text{th}$ ~i^\text{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]$ ~friends[i]~, where $i$ ~i~ is the current champion.

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

Comments

There are no comments at the moment.