Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

iaNTU's blog

By iaNTU, history, 6 weeks ago, In English,

Story

I just participated as an unrated contestant in Educational Codeforces Round 88 (Rated for Div. 2). I was trying hard to solve problem C, yet keep getting WA on test 4. I didn't solve the problem during the contest, and when I was testing my solutions after the contest, something weird happened.

Check this out

Compiler : C++17 AC

Compiler : C++17 (64bit) WA

I know nothing about the compiler.

I am just curious about what causes this difference, and what should I do to avoid these bugs.

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

»
6 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

For the second part of your question, of avoiding the bugs — it was possible to solve this problem using long long arithmetic alone, there was no need for doubles / floating point arithmetic.

I often use this technique: instead of storing a fraction a/b, I store 2 integers a and b. Then to check if a/b < c/d, I check if a*d < b*c, as its "if and only if".

Special care needs to be taken for no overflow, but thats easier than debugging floating point errors.

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

Yep, exact same thing happened to me with my python code which behaved same as your WA code.

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

I noticed while testing that this

#include <stdio.h>

int main(void)
{
    printf("%Lf\n", 1.0l);
}

Outputs 0.000000 while changing stdio.h into cstdio and adding std:: results in 1.000000. It doesn't seem to be related to your problem but I find this very weird. It also outputs 1.000000 when I compile as C.

»
6 weeks ago, # |
Rev. 10   Vote: I like it 0 Vote: I do not like it

The first two numbers outputted by this:

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
	cout << setprecision(20);
	cout << 999977.0 * 249944 / 249943 - 499998.0 << '\n';
	for (int i = 249944; i <= 249946; i++)
	{
		cout << 999977.0 * i / 249943 - 499998.0 << '\n';
	}
}

Are different on custom invocation with GNU G++17 7.3.0. I'm really puzzled on what's going on since I don't see any undefined behavior and IEEE 754 conformant floats should round consistently. IIRC GCC optimizations shouldn't affect the output unless a flag is used to specifically allow optimizations affecting floating point rounding.

Edit: It's because Codeforces G++17 7.3.0 apparently isn't IEEE 754 conformant for some reason. See https://codeforces.com/blog/entry/21844.