Help with an algorithm

This is a discussion on Help with an algorithm within the C++ Programming forums, part of the General Programming Boards category; Ok, I am posting this here since there seems to be so many people at this forum who love problem ...

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    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; 
    }

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    Code:
    #include <iostream>
    #include <fstream>
    #include <vector>
    using namespace std;
    int main() {
      ifstream in("inputfile");
      ofstream out("outputfile");
      
      int n = -1;
      while (true) {
        in >> n;
        if (n == 0) return 0;
        float f = 0;
        float max = 0;
        float g;
        vector<float> results;
        for (int i=0;i<n;++i) {
          in >> g;  //or use getline if you prefer
          f += g;
          if (g > max) 
    	max = g;
          results.push_back(g);
        }
        float average = f / n;
        float prev = average;
        int temp = (int)((float)average*(float)100);
        average = (float)temp / (float)100;
        if (prev != average)
          average += 0.01;
        float answer = 0;
        for (int i=0; i<n; ++i)
          if (results[i] > average)
    	answer += (results[i] - average);
        std::cerr << answer << std::endl;
        out << "$" <<  answer << std::endl;
      }
    }
    You're thinking too hard.
    Last edited by ygfperson; 06-09-2003 at 05:07 PM.

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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!

  4. #4
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    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.

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  6. #6
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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!

  7. #7
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  8. #8
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,831
    >>> Looks like I should just move on and chalk it up to a judge's error.

    I would be very careful about assuming a judges error!
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

  9. #9
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    Could you post your modified program?

  10. #10
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I agree about assuming the judges error, but I don't know what else to do at this point since I still can't find anything that breaks my proggie And besides its a computer judge not a human judge, and there is a disclaimer saying that it isn't perfect.

    And ygfperson, I just realized that unfortunately your program doesn't work on all cases. It turns out that you do need to calculate the difference for those below the average. Take for instance the case of 3 students who pay $1.00, $3.00, and $3.00. The average is $2.333 which means the below average need to pay $1.33 and the above average need to receive $1.32. So the answer needs to be $1.33 but your program prints out $1.32.

    Anyways, here is my latest code that got turned down:
    Code:
    #include<iostream> 
    #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() 
    { 
      vector<int> vecF; // vector holding each amount paid
    
      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
    
         vecF.clear();
    
         cin>>num; 
         if (!num) 
            break; 
    
         for (x=0; x<num; x++) 
         { 
             double d; 
             cin>>d;
             d*=100;
             vecF.push_back(int(d)); 
             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; 
    }
    Last edited by PJYelton; 06-10-2003 at 10:50 AM.

  11. #11
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  12. #12
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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; 
    }

  13. #13
    Registered User
    Join Date
    Mar 2003
    Posts
    28
    *Looks at problem statement*

    *Experiences de ja vu*

    *Head explodes*

    Okay, maybe not the last one, but anyway... are you competing in the ACM programming competition? 6 hours, 8 (9?) questions, groups of 3 people, one computer?

    At least, the question was in the exact same format as the ACM competition. I competed in it in 1999, I think it was, but admittedly didn't do especially well (this is where I blame it on my teammates... . I was going to enter last year (I was at uni, and the department was paying the entry fees) but decided not to at the last minute due to being too busy.

    Damn, I wish I could enter this year... *sigh*

    *Contemplates enrolling in uni again, and then dropping out after the competition*

    Just
    "C++ is like jamming a helicopter inside a Miata and expecting some sort of improvement."
    - Drew Olbrich

  14. #14
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    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.

  15. #15
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,831
    On the other hand, when you are programming real applications in the real world, you don't even get a "right" or "wrong" - just an angry customer with a lawyer!
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21