Блог пользователя ps06756

Автор ps06756, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • -27
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Your solution is too complicated for a div2_B problem. you could simply solve the problem using the two pointers method. :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Of course, I just wanted to share my approach after I found that most people were applying the two pointer binary_search solution.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by ps06756 (previous revision, new revision, compare).

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Your solution uses two pointers method. It is the author's solution.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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?