Skiena's Programming Challenges: The Trip problem

Question

I have the following solution for the Trip problem from Skiena's and Revilla's Programming Challenges (full problem description here).

#include <stdio.h>
double truncate_to_2_decimals(double n)
{
 return (double)((int)(n*100.0)) / 100.0;
}
double mean(int n, double numbers[])
{
 double r;
 int i;
 for(i = 0; i < n; i++) {
 r += numbers[i];
 }
 return r / (double)n;
}
double min_exchange(int n, double expenses[])
{
 double r;
 double mu = mean(n, expenses);
 int i;
 for(i = 0; i < n; i++) {
 double e = expenses[i];
 if(e < mu) {
 r += mu - e;
 }
 }
 return truncate_to_2_decimals(r);
}
int main(int argc, char *argv[])
{
 int n_students;
 while(scanf("%d", &n_students) != EOF) {
 if(n_students == 0) {
 break;
 }
 double expenses[n_students];
 int i;
 for(i = 0; i < n_students; i++) {
 scanf("%lf", &expenses[i]);
 }
 printf("$%.2lf\n", min_exchange(n_students, expenses));
 }
 return 0;
}

The solution handles both the sample input and the following "tricky" input correctly:

4
9999.10
9999.10
9999.00
9999.10
3
1.01
0.99
0.99
0

Output:

0ドル.07
0ドル.01

Yet for some reason the online judge returns a "Wrong Answer" error. What could I be missing?

Answer 1

Now I see it. There's a flaw in your logic. Your code first calculates the mean to max precision, then takes the difference between each expense and the mean (still at max precision), and adds together the positive differences. At the end you round off the grand total to the nearest penny and return it.

That's the wrong approach. It doesn't solve the problem as stated. The key observation is that the problem says the smallest unit you can transfer is a penny, not fractions of a penny.

For instance, say there are 100 students on the trip, and the expenses are 50 x 1ドル.01 and 50 x 1ドル.00. The correct answer is obviously zero (they already agree to within a penny), but your code will calculate the mean as 1ドル.005, and then decide that the amount needing to be transferred is 50 x 0ドル.005 = 0ドル.25, which doesn't change when you round it off.

Answer 2

• return (double)((int)(n*100.0)) / 100.0; fails for values of n greater than 2.147483648E7 as product n*100.0 would be larger than the maximum value of a 32-bit signed int. Use floor() instead. But that's (削除) probably (削除ここまで) not the reason the online judge fails it. **EDIT**problem size is restricted so this isn't an issue.
• your mean() function is theoretically numerically instable, but that's (削除) probably not it either. (削除ここまで) EDIT definitely not it due to the problem description.
• double expenses[n_students]; is not supported in C89 as it is a variable-length array. This feature was required in C99, but in the newer C11 it is an optional feature that compilers are not required to support. I suspect that your compiler supports variable-length arrays a la C99 but the online judge's compiler doesn't. Try using double * expenses = malloc(sizeof(double)*n_students); and changing other types as appropriate. Don't forget to free() your memory too. EDIT Checked the website and they say it supports "ANSI C". My guess is they mean C89.

• sjakobi: Thanks for your suggestions! I have followed your recommendation with malloc but the judge still responds with "Wrong Answer". My error must be elsewhere.