maharun's blog

By maharun, history, 8 months ago, In English
less_equal PBDS set has certain problems:
  1. Erase doesn’t work (if the value is sent)
  2. upper_bound gives lower_bound
  3. and lower_bound gives upper_bound
To demonstrate this problem, let's see a code and it's output:
Code
Output

As you can see, here the lower bound and upper bounds are flipped. Erase doesn't work either.

In short, PBDS uses the same comparator for sorting, equality check, upper bound, and lower bound.
less_equal just replaces < sign with <= sign. Nothing else.

Let’s see what kind of problem it arises:

Sorting comparator: No problem. It is the order we want the elements to follow.

Equality Check:

In std::set, !comp(a, b) && !comp(b, a) is used.
Which works for strictly increasing/decreasing order like set.

But, if a = 5 and b = 5
Then !(5 <= 5) and !(5 <= 5) returns false.

That’s why erase doesn’t work if only value is passed.

But if the iterator is provided, it will work.
So, always do this:
s.erase(s.find_by_order(5));

Lower bound and Upper bound:

  • Lower bound is the first element that is not less than a given key
normal lower = !(value <  target)
   here comp = !(value <= target)
Elements = 1 2 3 3 4 5
Normal   = F F T
Here     = F F F F T
  • Upper bound is the smallest element greater than the given value
normal upper = (value >  target)
   here comp = (value >= target)
Elements = 1 2 3 3 4 5
Normal   = F F F F T
Here     = F F T

As you can see, how upper and lower bound flips here.

Note: If there are any problems please let me know.

Not sorry for my poor English.
(^ヮ^)/

Full text and comments »

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

By maharun, history, 11 months ago, In English

I can access 'Code Forces' through this link: https://mirror.codeforces.com/

But can't be accessed through https://www.codeforces.com/
[It show's 403 Forbidden]

Does anyone know what is happening?

Full text and comments »

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