The Trip Programming challenge UVA10137

Question

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

//#include "stdafx.h"
#include <iostream>
#include <string> //Always import <string> if piping std input to a string in .net 
#include<algorithm>
#include<math.h>
#include<fstream>
using namespace std; 
int main()
{
    //ofstream myfile;
    //myfile.open("example.txt");

    int n; //number of students sharing trip costs.
    while (cin >> n) { 
        if (n == 0) {
            return 0;
        }

        double *ammounts_spent = new double[n];
        double total_spent = 0;
        for (int i = 0; i < n; i++) {
            cin >> ammounts_spent[i];
            total_spent += ammounts_spent[i];
        }
        double ammount_exchanged = 0; 
        double ammount_exchanged_below = 0;
        double ammount_exchanged_above = 0;

        double average_spent = total_spent / n;
        double rounded_down_average_spent =(double)((int)(average_spent * 100)/(double)100);
        double rounded_up_average_spent = rounded_down_average_spent + 0.01;
        if (rounded_down_average_spent - average_spent < 0) {
            for (int i = 0; i < n; i++) {
                if (average_spent > ammounts_spent[i]) {
                    ammount_exchanged_below += rounded_down_average_spent - ammounts_spent[i];
                }
                else {
                    ammount_exchanged_above += ammounts_spent[i] - rounded_up_average_spent;
                }
            }


        }
        else {
            for (int i = 0; i < n; i++) {
                if (average_spent > ammounts_spent[i]) {
                    ammount_exchanged_below += average_spent - ammounts_spent[i];
                }
                else {
                    ammount_exchanged_above += ammounts_spent[i] -average_spent;
                }
            }

        }

        ammount_exchanged = max(ammount_exchanged_above, ammount_exchanged_below);
        if (ammount_exchanged == floor(ammount_exchanged)) {
            cout << "$" << ammount_exchanged << ".00\n";

        }
        else {
            cout << "$" << ammount_exchanged << "\n";
        }
    }
}

It works for all debug input given on udebug and even for tricky instances such as

> 4
> 1.01
> 1.01
> 1.00
> 1.00

Where the amount exchanged is $0.00. Yet the UVA online judge is giving me a verdict of wrong answer.

Answer 1

Printing loses precision

Using this input file:

6
0 0 0 0 10000 10000

Your program gives this answer:

$13333.3

The actual answer should be $13333.32. The program seemed correct, but the printing only printed out 6 digits of precision. I made this change to your program which made it print out the correct answer:

cout.precision(15);

Better to use integers

It would be safer to use integers throughout your program. There could be any number of floating point roundoff problems that might show up unexpectedly, especially since 0.01 is not perfectly representable by a double.

Answer 2

You should consider using descriptive names rather than textual comments. For example this line here

int n; //number of students sharing trip costs

Would be way better as

int numStudents;

That way if you look at the code some time later or when you have a lot of those one character variables you do not have to always look up what it means.

It is generally beneficial to sort your includes alphabetically, so one can easily check if a header is included or not. Also double includes do not happen that way. Also try to use the c++ headers aka cmath instead of math..h

More in detail regarding the code.

1. Do not use namespace std;. It is a bad practice even in coding challenges.

2. Use the std containers e.g. std::vector That way you do not have to deal with memory. So this

   double *ammounts_spent = new double[n];
   double total_spent = 0;
   for (int i = 0; i < n; i++) {
       cin >> ammounts_spent[i];
       total_spent += ammounts_spent[i];
   }
   

   becomes this

   std::vector<double> ammounts_spent(numStudents);
   double total_spend;
   for (double moneySpend : ammounts_spent) {
       std::cin >> moneySpend;
       total_spend += moneySpend;
   }
   

3. Do not cramp your main function with all the code. Generally the main should only handle inputs/ouputs and calling functions. So restructure your code into little well named functions.

4. Use proper functions for example this

   double rounded_down_average_spent =(double)((int)(average_spent * 100)/(double)100);
   

   Is equal to

   double rounded_down_average_spent = std::ceil(average_spent);
   

5. I do not understand why rounded up is equal to rounded down + 0.01?

6. You are checking whether the rounded down value is smaller than the original one. From my perspective it is more logical to check for equality instead rounded_down_average_spent == average_spent as this is what you meant.