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

Question about codeforces problem
Автор Samsam, 10 лет назад, По-английски

Hello everyone, I am trying to solve this problem so I've read the tutorial and every thing is clear,but there is one thing that I couldn't understand: in the solution we used binary search to find the minimum value of c(a),so if the range is [L,R] and mid = (R+L)/2 then if we found that mid can't be a value c(a) because we have to change more than k elements then the binary search will be applied on the new range [mid+1,R],so the question is: why if we found that the mid can't be a value of c(a) because it needs making more than k changes then all the values of c(a) that is from the range [L,mid-1] will also cost more than k changes? Thanks a lot.

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

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

When binary searching we don't say c(a)=x. We say c(a)<=x. What I mean is that if the binary is currently checking number x then it is checking whether we can construct a solution with c(a) less or equal to x.

For example if we are checking for x=5, then any solution with c(a)=0,1,2,3,4,5 is fine. The DP described in the analysis checks that.

Well once it is defined like that it is now obvious that if x isn't a solution, then obviously any number less than x wouldn't be either, as it would give positive answer to x itself.

Hope I helped :)

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

    Thanks, you are right

    but could you tell me how the DP checks whether we can construct a solution with c(a) less or equal to x? because I think the DP is just checking if x can be a solution or not and if not then there is a theorem that proves that numbers 0,1,2...x-1 also can't be solutions.

    → Ответить