Kefa and Company and Z-algorithm

Revision en1, by ps06756, 2015-09-24 23:45:59

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 13210461

Tags dp, sorting, binary search

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ps06756 2015-09-25 00:03:13 6 Tiny change: 'sion:13210461]' -> 'sion:13210753]'
en1 English ps06756 2015-09-24 23:45:59 1097 Initial revision (published)