Thread: Help with an algorithm

Ok, I am posting this here since there seems to be so many people at this forum who love problem solving and a good challenge. First off, this is not homework. I am studying for a programming competition coming up and am doing so problems I found at a website. I wanted to start off on an easy one, but for the life of me I can't understand why this one won't work. I keep submitting it but I keep getting back from the judge that for some test data my algorithm returns the wrong answer - but it won't say which test data and everything I can think of gives a correct answer. The problem statement is here.

Basically this is my algorithm. First find out what the average amount is, rounded down. Then I cycle through all of the amounts, and if the amount is less than the average, I add the difference to the LESS pile, and if the amount is more than the average, then I add the difference to the MORE pile. If I had to round down when I first calculated the difference, then I add one to the average when I do the difference between a pile that is greater and the average.

Now I figure that the greater of the two amounts is the minimum amount of money that needs to be transferred. Like for example if the LESS pile is $2.00 and the MORE pile is $2.01, then the minimum amount of money transfered is $2.01 since if only 2 dollars were transferred, then the MORE people wouldn't be within one cent. So I always return the greater of the two numbers. But I get the wrong answer even though every thing I have tried has given me a correct answer!

Can anyone at all think of a set of data that breaks my algorithm or a logical reason why it is flawed? This is driving me nuts!

Here is the code:

Code:

#include<iostream> 
#include<string> 
#include<vector> 
using namespace std; 

int max(int x, int y) {if (x>y) return x; else return y;} 
int min(int x, int y) {if (x<y) return x; else return y;} 

int main() 
{ 
  while (1) 
  { 
     int num;  // number of students
     int x;
     int total=0; // total amount spent in pennies
     int more=0; // amount over the average spent in pennies
     int less=0; // amount under the average spent in pennies
     bool round=false; // average came out evenly or not
     vector<int> vecF; // vector holding each amount paid

     cin>>num; 
     if (!num) 
        break; 

     for (x=0; x<num; x++) 
     { 
         double d; 
         cin>>d; 
         vecF.push_back(int(d*100)); 
         total+=(vecF[x]); 
     } 

     if (total%num!=0) 
         round=true; 

     total/=num; 

     for (x=0; x<vecF.size(); x++) 
     { 
         if (round && vecF[x]>total+1) 
            more+=(vecF[x]-(total+1)); 
         else if (!round && vecF[x]>total) 
            more+=(vecF[x]-total); 
         else 
            less+=(total-vecF[x]); 
     } 

     less=max(less,more); 

     cout<<"$"<<less/100<<"."; 

     if (less%100<10) 
         cout<<"0";
     
     cout<<less%100<<endl; 

   } 
    
   return 0; 
}

Um, if you noticed, our programs do pretty much the exact same algorithm, just done a little differently. The only difference is that you only add up the people above while I add up both above and below. The more I think about it, I agree that those above will always be greater, so adding up the below is pointless, but in the end it doesn't affect anything.

And since ours are the same, we get the same wrong answer.

[edit]
Yep, just submitted your exact program, only changing the formatting of the output, and the judge spits back wrong answer. Now you know why this is so frustrating!! There is nothing wrong with what you or I did!

Hmm...

My plan was to find the average of the values, and add together the distance of the values above it. (The values above it will equal the values below it because it all comes back to the average. The movie is tranfered from the high numbers to the low numbers.)

I believe our error is in disregarding the limitations of the contest. We don't check for a max of $10,000, or a max of 1,000 people. Perhaps we need to send error messages when that happens.

//edit: and with silly things, like negative money and people.

Unfortunately I dont think so. I have done about 20 problems so far on the site, and none of them needed the program to check for bad input and all got correct answers. I need to find where it explicitily says that, but I'm almost positive that when it says the input needs to be within a boundary, then none of the test data will be outside the limitations. I really do think they screwed up on this one, or else its a rounding error but I used doubles and I can't imagine getting a rounding error only two decimal places deep.

Oh, not that it matters, but the money above doesn't always equal the money below. Take for example $10, $10, $10 and $30.03: the average is $15.0075 and the below total is $15 and the above total is $15.02. So you always need to take the bigger number which is what I was doing, it just turns out that on further thought the above is always bigger if they aren't equal so its pointless to worry about the below.

Salem, are you using MSVC++? Because when I run my program on MSVC++ I get the correct answers of $10.00 and $11.99 without changing anything at all. And the resizing the vector thing isn't a problem because it is reinitialized every time through the while loop. Unless for some reason some compilers skip the declaration of the vector the second time through as though it were declared as static.

But you bring up an important point, if on your compiler it is rounding incorrectly, then perhaps the compiler the judge uses isn't rounding correctly either. Hmmm... I'll try your suggestion and see if the judge likes it. Thanks!

Blech, still got a wrong answer.

I tried several different ways to avoid a possible rounding error, all which produced correct results when I ran it. I even moved the declaration of the vector outside the while loop and then just cleared it each time through. All attempts got a wrong answer. Looks like I should just move on and chalk it up to a judge's error.

Could you post your modified program?

Yeah, the messages you can get back are Correct!, Presentation error, Program error (like a divide by zero or seg fault), and Wrong Answer. And if you get a wrong answer, then thats all you get, no details at all.

And I just tried it without the '$', and no go <sigh>

Seems like there are a lot of people complaining about this problem, but at the same time according to the statistics there have been a few people who have gotten it correct, but they are keeping their mouths shut on the site boards.

Woot! I finally got it to work!! It turns out that the compiler the judge uses is getting rounding errors in C++, but I was told that they wrote my exact program in Java and got accepted. So that got me to scrap using ints at all and only use doubles, and it got accepted, finally! Here is my final code that the judge liked:

Code:

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

long max(long x, long y) {if (x>y) return x; else return y;} 
long min(long x, long y) {if (x<y) return x; else return y;} 

long main() 
{ 
  vector<double> vecF; // vector holding each amount paid
  long num;  // number of students
  long x;
  double total=0; // total amount spent in pennies
  double more=0; // amount over the average spent in pennies
  double less=0; // amount under the average spent in pennies
  bool round=false; // average came out evenly or not

  while (1) 
  { 
     total=0;
     more=0;
     less=0;
     round=false;

     vecF.clear();

     cin>>num; 
     if (!num) 
        break; 

     for (x=0; x<num; x++) 
     { 
         long double d; 
         cin>>d;
         vecF.push_back(d); 
         total+=(vecF[x]); 
     } 

     if (double(long(total*100.0/num)/100.0)!=total)
          round=true;


     total=double(long(total*100.0/num)/100.0); 

     for (x=0; x<vecF.size(); x++) 
     { 
         if (round && vecF[x]>=total+.01) 
            more+=(vecF[x]-(total+.01)); 
         else if (!round && vecF[x]>total) 
            more+=(vecF[x]-total); 
         else 
            less+=(total-vecF[x]); 
     } 

     if (more>less)
          less=more; 

     cout<<setiosflags(ios::fixed)<<setprecision(2);

     cout<<"$"<<less<<endl;

   } 
    
   return 0; 
}

Yeah, I'll be competing in the ACMs for the first time, looking forward to it! But that whole not telling you where you went wrong will bug the hell out of me. At least over at topcoder.com they tell you what broke your algorithm.