lama_codes's blog

How to apply binary search to this problem!
By lama_codes, history, 9 years ago, In English

Hi, Can anybody help me to figure out how to apply binary search for the problem 231C - To Add or Not to Add.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why not to read editorial?

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

    Referring to editorial was my first destination but ,I can't clearly get the idea. So if you could help me out , it'd be great.

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

      Well. First part — second number in answer should be a number from initial array. It's explained good enough there. So, we need to check all the numbers from array and calculate, how many operations of "+1" we need to use — the first number for our answer depends on that. That's true, as much operations we use — so much equal numbers we can obtain. Consider the following forward algo: first, we take a[i-1] and apply "+1" to it until a[i-1]==a[i], then go to a[i-2] and so on: we apply more operations — we get more numbers. Hence, first part of answer is monotonic function, which depends on number of applied operations. And we can use binary search here. Let cnt be that number of operations... And then — last part of editorial as it is. Is it better now?

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        clear thinking. I think lama_codes will solve it.

        → Reply