Kefa and Company and Z-algorithm

Правка en1, от ps06756, 2015-09-24 23:45:59

Hello, in this article I would be telling an alternative solution to the 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 13210461

Теги dp, sorting, binary search

История

 
 
 
 
Правки
 
 
  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)