RestingRajarshi's blog

By RestingRajarshi, 5 years ago, In English

I recently came across something called fractured Searching.

Example prob : Kth MST. Outline : We basically find a MST, now fix a prefix of the edges used and say the rest can be changed, and depending on length of the prefix, we divide the rest of our search space into different regions, and search in them again.

Another prob : Third Prob of this link

Editorial Solution : click

There is also a video on this on youtube by Algorithms Live.

Can someone provide more problems that can be solved by this technique, since its hard to find tags that describe such approach.

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

5 years ago, # |
  Vote: I like it 0 Vote: I do not like it task: "Olympiads"