Hello, in this article I would be telling an alternative solution to the problem 580B - Kefa and Company
Most of the solutions , which I have seen use Binary search to solve the problem after sorting of course, so the overall complexity of the solution is O(nlogn) + O(nlogn). I am discussing approach with the complexity of O(nlogn) + O(n). Here , the first O(nlogn) is due to sorting. So, after sorting there is a great improvement in the algorithm complexity. My approach is similar to Z-algorithm for string matching.
Just like Z-algorithm, we maintain a Z[i] array which will contain two things (ie a pair<int,int>), first the maximum index till which we can invite friends starting at ith position and second the total cost of doing so.
Now, while iterating over the entire array, we check whether the current index is less than the Z[i-1].first, if it is so then we immediately know that Z[i].first is at least Z[i-1].first and we iterate from there and update the Z array.
For any clarification, please see my following submission 13210753
Your solution is too complicated for a div2_B problem. you could simply solve the problem using the two pointers method. :)
Of course, I just wanted to share my approach after I found that most people were applying the two pointer binary_search solution.
Auto comment: topic has been updated by ps06756 (previous revision, new revision, compare).
Your solution uses two pointers method. It is the author's solution.
You're using sorting + two pointers method, just like the solution posted in the Editorial.
Besides, what does this have to do with Z-Algorithm and string matching?
The idea of both Z-algorithm and this solution is same.