[Contest][1]
[Practice][2]
Author: [Shivam Garg][3]
Tester: [Shiv Dhingra][4]
DIFFICULTY
EASY
PREREQUISITES
Basic Knowledge of Sets (STL)
PROBLEM
Given a list of integers, for each of them find the maximum number less than the given number preceding it.
EXPLANATION
The brute approach will turn out to be of complexity O(N ^2), and hence is bound to time out.
We can maintain a sorted set of numbers by iterating over the array. In other words, if we have a set of numbers preceding the given number, we can easily find out the largest number smaller than the given number.
We can simply perform binary search in this set to find the number just less than the given number.
This can be done by using lower_bound command of the set in C++, or equivalent in other languages.
set<long long>::iterator it = s.lower_bound(val);
it--;
return (*it);
This will fulfill our task. The complexity of accessing/inserting elements in the set is O(Log(N)).
So, the overall complexity turns out to be O(N \hspace{1 mm} Log(N)).
SOLUTION
Setter’s Solution -
[5]
[1]: https://www.codechef.com/CODR2018/problems/KRYP6
[2]: https://www.codechef.com/problems/KRYP6
[3]: http://codechef.com/users/shivamg_isc
[4]: http://codechef.com/users/lucifer2709
[5]: https://www.codechef.com/viewsolution/17468627