Atomsky's blog

By Atomsky, history, 5 weeks ago, In English

In CF Round #727 (Div. 2), I submitted 120147862 for Problem-C: Stable Groups. It gave a wrong result on test 62 in GNU C++17. When I submitted the same code in GNU C++11, it was accepted (120149347).

I tried to figure out what went wrong in C++17. If I simply add a line that prints out the array output after line 14, like cout << foo[i] << endl;, the code gives the correct result in C++17. I am having trouble understanding why this might happen! What can I do in such cases?

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

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

It's probably the fact that you are using doubles, and (I heard that) doubles in C++11 and C++17 work differently

instead of

ceil((jar[i] - jar[i-1])/(double)x);

you can try

(jar[i] - jar[i - 1] + (x - 1)) / x;

this will avoid working with doubles, as ceil(a / b) can be equivalent to (a + b - 1) / b

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! That's an elegant way to convert from ceiling to floor.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

Dont use ceil because 2+eps might be ceilied to 3. As a rule of thumb avoid floats when you can in CP. It is not UB, mingw 32bit is configured to use excess precision by default it means that it will do all the operations in 80 bit float or sth like that. 64 bit one isn't it seems.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot! I will make sure to keep this in mind.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +31 Vote: I do not like it

I have fallen into this trap at least twice. For a rational number $$$r=\frac pq$$$, when you want to calculate $$$\left\lceil\frac pq\right\rceil$$$, don't use ceil(1.0 * p / q) (which can cause serious accuracy errors when $$$p$$$ and $$$q$$$ are very large), but use (p + q - 1) / q instead. Note that some changes need to be made when $$$p,q$$$ is negative, because in C++ signed integer division truncates towards zero. You can read this post for more information.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you! I'll be using these formulas for ceiling function from now on.