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

Автор sunohara25, история, 4 года назад, По-английски

How to approach problems like this Playlist or Josephus problem, where we delete some element and rejoin the circle. Also, if anyone can provide 2-3 similar problems, it will be really helpful to master this concept.

Thank you

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

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

In many deletion problems, only a small change occurs in the array/circle. For example, in the problem Playlist, at most three GCD pairs change. This can usually help in either simulating the problem or getting to some other observation.

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

    In this problem the number of elements in circle get reduced by 2-3 , but how to approch problems where we have to reduce it to 1 element.

    Ex : Given an circular array , you can merge two adjacent elements and replace to by F(a[i],a[i+1]) .Find the maximum value you can get after n-1 operations ??

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

In deletion problems, there are some common approaches like doubling the array, using a data structure (set, segment tree) to erase and then binary searching or observing minor changes after deleting an element.

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

I like to use a circular linked list. It is extremely intuitive as it is literally a circle (I feel this makes more sense than for example, doubling the array).

https://www.geeksforgeeks.org/circular-linked-list/