SRM 733, D1, 250-Pointer (MinimizeAbsoluteDifferenceDiv1)

James S. Plank

Tue Aug 21 17:57:10 EDT 2018

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
Problem Given in Topcoder: April, 2018
Competitors who opened the problem: 198
Competitors who submitted a solution: 190
Number of correct solutions: 100
Accuracy (percentage correct vs those who opened): 50.5%
Average Correct Time: 13 minutes, 39 seconds.

This seems way too easy, doesn't it? Call next_permutation, calculate the value and you're done. Whenever a topcoder problem seems too easy, you should ask yourself, "what can go wrong?"

Well, here, the one thing that can go wrong is roundoff error. Take a look at the following C++ program:

#include <cstdio>
using namespace std;

int main()
{
  printf("%.20lf\n", 9995.0/10000.0 - 9994.0/10000.0);
  printf("%.20lf\n", 9995.0/10000.0 - 9996.0/10000.0);
  return 0;
}

Those two values should be the same, but when you run the program, you see roundoff error:

UNIX> a.out
0.00010000000000010001
-0.00009999999999998899
UNIX>

How can you avoid the roundoff error? For each expression, calculate its numerator and denominator as long long's. Keep track of the best numerator/denominator pair. How do you do that? Test whether

new_numerator / new_denominator - best_numerator / best_denominator

is less than zero. You'll have to do that without floating point again.

It's pretty clear that this is a really easy program, so the challenge here was avoiding the floating point pitfall, and as you see above, nearly half of the programmers did not avoid the pitfall!