kkdrummer's blog

By kkdrummer, history, 4 years ago, In English

In the editorial of problem:1237D - Balanced Playlist i read terms like:

'binary search over segment tree in O(nlog2n), binary search over sparse table in O(nlogn), binary search over stack in O(nlogn)'

Are these general concepts(like BIT or segment tree) or only specific for this problem? If former , then Anyone who knows these concepts well , kindly explain.

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

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

i dont get it how can a binary search have more time complexity than linear search!!

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

    logn for binary search and the other term for the data structure its being implemented on, but don't know how, i heard these terms for the first time , so asked for help, couldn't find any help on google

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

I think this is a very general concept — binary searching a space. In a given a search space, you can define a predicate function on some data structure (sorted arrays in the case of a basic lowerbound calculation for example — it can get as complicated a data structure as you want) and an argument (say some positive integer for our sake). The predicate function would output a yes/no answer. The property that the predicate needs to satisfy is that for progressively increasing the argument, the series of answers by the predicate is of the form — No ... No No Yes Yes ... Yes. Now given this series, you can quite easily see that if you are just given this boolean array of outputs, its quite easy to perform a binary search in log(n) time with O(1) query time. But in general, its probably not feasible to get the output array, a more useful thing to do is query the predicate every time on the middle element of your current search space. Now the reason you see these weird complexities is because for each of the log(n) queries that your binary search makes, the calculation of the predicate itself can take more than O(1) complexity. A simple example problem to illustrate a non-O(1) predicate is — Find the number of nodes in a complete binary tree (a binary tree whose every layer but the last have two children, and the last layer’s nodes are to as far left as possible) in less than O(n) time. Here you’d have to notice that the root-leaf path length is O(log(n)) and for each root to leaf path, the predicate finds the answer to — is the path length less than h(the max height of tree)? Hence upon a binary search with O(log(n)) queries and for each query you have an O(log(n)) predicate calculation — the total overall complexity is O(log^2(n))

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks..made it very clear. Share some problems with similar concept if possible.

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

      Well, most 1600+ binary search tag problems in CF are of this sort. The hard part about cracking them is realising that you can create such a predicate which is non-trivial. I’ll update this comment with good problems I’ve solved of this sort tomorrow.