krishrb2517_'s blog

By krishrb2517_, history, 6 months ago, In English

https://codeforces.me/contest/1783/problem/C

This is the link of the problem

https://codeforces.me/blog/entry/111194

This is the tutorial

In the editorial for problem C , why is it written we should check

m+b[ans-1]>=a[ans]

why is it depending on a , as it is not in any ordered pair , rather isn't it much logical that we will check with b[ans] that is it possible that instead of this we can switch it up with next element possible.

If anyone can help in pointing out where I am going wrong.

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can find the reason for that in the tutorial.

If ax contains among x smallest values, then we'll take place n−x.Otherwise, let's try to "insert" ax in this set, i.e. let's erase the biggest among them and insert ax. If the sum is still lower or equal to m, it's success and we get place n−x. Otherwise, our place is n−x+1.

For checking this we use the condition m+b[ans-1]>=a[ans], if it is condition true, we get n-x else we get n-x+1.