Kefa and Company and Z-algorithm
Разница между en1 и en2, 6 символ(ов) изменены
Hello, in this article I would be telling an alternative solution to the problem [problem:580B]↵

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 [submission:13210
461753]

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский ps06756 2015-09-25 00:03:13 6 Tiny change: 'sion:13210461]' -> 'sion:13210753]'
en1 Английский ps06756 2015-09-24 23:45:59 1097 Initial revision (published)