dkyu021's blog

What's the difference?
By dkyu021, history, 3 years ago, In English

Hello Codeforces,

I have one doubt, are these statements not same ?

Statement 1: int up = x/y;

Statement 2: int up = floor((float)x/(float)y);

I might be doing a very naive or silly mistake but I'm not able to see the difference.

Question is like:

Link to problem (Total Pairs): Question Link

Question

My solutions to problem:

Wrong Solution
Accepted Solution

Thanking You all in advance!!!

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

»
3 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Float has precision errors, I replaced it with double and that fixed it.

UPD: as purplesyringa said, it's better to avoid floating point numbers entirely, so I'll show you how to do that.

We want to calculate $$$\left\lceil \frac x y \right\rceil$$$, where $$$x$$$ and $$$y$$$ are integers. But notice that $$$\left\lceil \frac x y \right\rceil = \frac x y$$$ when $$$x$$$ is a multiple of $$$y$$$, and $$$\frac x y + 1$$$ otherwise. So this is one way you can calculate the ceiling division.

Another (more widely used) way is to do $$$\left\lfloor \frac x y \right\rfloor$$$ with a bit of a modification. Let's add a $$$1$$$ to the whole expression, because we can notice that most of the time (except for multiples), the ceil is exactly 1 more than the floor. So we can try $$$\left\lfloor \frac x y \right\rfloor + 1 = \left\lceil \frac {x + y} y \right\rceil$$$. But notice that this, too, fails for multiples of the denominator. A way we can fix this is to subtract $$$1$$$ from the numerator, so $$$\left\lceil \frac x y \right\rceil = \left\lfloor \frac {x + y - 1} y \right\rfloor$$$, but always remember that this only works for integer numerators and denominators.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    double has precision errors too. Avoid floating point numbers whenever you can.

    → Reply