-
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;
}
-
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.
-
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.:mad: :(
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.
-
>>> 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!
-
Could you post your modified program?
-
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;
}
-
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> :( :D
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;
}
-
*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
-
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.
-
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!