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

Can this problem be solved using Binary Search
Автор Hadras, история, 3 года назад, По-английски

Can this problem be solved using Binary Search

Link: https://mirror.codeforces.com/problemset/problem/1606/C

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

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

NO. First test case, 100 can be represented with 1 banknote. And so does 1. Basically, you cannot compare it to the final answer.

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

    What do u mean by final answer

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

      For each test case, print one integer — the minimum positive number of burles s that cannot be represented with k or fewer banknotes.

      → Ответить
»
3 года назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

You can use binary search in the array a so that you can say that the cost(10^b) = 10^(b-last) where last is the last ai such that ai <= b and use this to solve the problem(this is quite useless since n = 10 but actually optimize it 157598538), otherways I don't where to use binary search. If you meant binary search the answer, it is not possible since the cost(x) does not strictly increment, in a case like a: {0, 4} cost(10000) = 1, cost(9999) = 9999.

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

No. Binary search requires the searchspace to have a special property. If it can be done for some value x then it can be done also for x+1 and it's enough.

(The direction can be reversed, ie x -> x-1).

This problem clearly doesn't satisfy this.

9: 9notes
10: 1 note.
(decreased)
11: 2 notes
(increased)
→ Ответить