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

Автор lama_codes, история, 9 лет назад, По-английски

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

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

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

Why not to read editorial?

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

    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.

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

      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?