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

The ceil trap (Beginners Only Topics)
Автор ivplay, история, 9 лет назад, По-английски
  • I fell into a very interesting situation today , while solving CF — 599D.
  • say long long a = 1000000000000000363,b= 91
  • I wrote long long c = ceil(a*1.0/b) thinking (long * double) / double should be perfect double and ceil(double) — should work out.
  • I was expecting correct answer, c = 10989010989010993, but it produced c= 10989010989010994 , 1 more than the actual — result!!!! Damn to the precision issue.

  • Lesson :

    • Option 1 : Study lot lot and lot about your compiler and how it manages precision while both implicit and explicit cast.
    • Option 2 : Use your own ceil function like this
  • template inline T ceil(T numerator ,T denominator)
  • {
    • return (numerator+denominator-1)/denominator;
  • }

  • Moral : Avoid fraction as much as you can.

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

»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Yes, doing (num + den - 1) / den is what I always do. You only have to be careful with overflow if working with very big numbers, in which case you should do return num%den == 0 ? num/den : num/den + 1. The last option is more expensive because of the modulo operation, so I only use it in case of possible overflow.

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

    Ya, good reminder... :)

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

    Not necessarily slower due to modulo. On x86 div instruction returns both quotient and reminder, so modulo operation comes for free as you need to do division anyway. GCC does this optimization. Only additional cost comes from the conditionally adding + 1. It can be compiled to something like this:

    (quot, rem) = DIV(num, den)
if (quot) rem++;
return rem;

    On other architectures reminder can be obtained by doing multiplication of division result. In either case it is not as expensive as doing completely unrelated modulo operation.

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

    Any specific problem where overflow occurs? People also suggest the same in binary search. If some problem related to that?

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

Doubt has been cleared.

I have edited this comment because some people find it inappropriate.

If you are still curious you can check the 1st version of this comment.

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

    I assume you want somebody to give you a hack for problem A of the most recent educational round. I'm not sure about rules regarding collaboration for hacks but this seems very sketchy. In any case you can just wait until the round is over, and then view the hacks.

    Also, there's basically no point in hacking at this stage. The ceil hack tests will be added to system tests so any solution you'd be able to hack would just FST anyways.

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

      Thanks buddy for replying. I searched over some more blogs and got the answer to my doubt. Also I know that hack tests are added in the final test set and me hacking every single solution involving ceil function make no sense. It was just for knowledge purpose. I really appreciate the fact that you respect codeforces' rules and so does I.

      I myself once encountered the same problem while using ceil function in some round (may be educational) and I could not find the exact reason at that time. That time I only understood that ceil function should be avoided.

      Just because of the last educational round I knew that some people are going to land on this blog :-) so I asked my doubt.

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

      Yeah right. Always assume malicious intent.

      I landed here because my solution got hacked and not because I want to hack anybody.

      → Ответить