Samsam's blog

Question about codeforces problem
By Samsam, 10 years ago, In English

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.

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

»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 :)

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

    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.

    → Reply