sunohara25's blog

How to approach circular deletion problems?
By sunohara25, history, 4 years ago, In English

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

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 ??

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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/

→ Reply