The trip is a very interesting problem, but the fact for me is that I haven't been able to solve it even after a long time. I have collected all the test cases available in the board and all except 1 test case fails and I have no idea how to solve it. Here's the failing test case:
0.01
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
0.03
The expected answer is: $0.02, while my solution says $0.01.
To me, it looks like there is some key piece in the problem statement that is missing for me to correctly figure out the answer. I also felt that arriving at my current solution was also not very straight forward. I believe that clearing up the problem statement will help people to understand it better and solve it. The problem's success rate is average probably because of this reason.
My learnings:
1. Program to use money like the way it is being by people. Do not go for floats and doubles. That will help in avoiding magic like floor, ceiling. I got this hint from Prof.Skiena's programming challenges videos. The original link seems to be dead :(
2. The way to compute average is very key to be able to get to a solution and to be able to explain it to others. What is a solution if it cannot be understood by others? What is a solution if it cannot be explained to others?
So I want to take money from underpairs and give them to overpairs such that i take minimum money through hand and all people at the end pay
ReplyDeletesame money (within a cent i.e difference between money paid by 2 people is atmost 1 cent)
So i find average money(Avg) and tryh to take every person's payment closer to it..
1) if (Avg) is integer , then all people can pay exactly Avg amount of money . Neither can pay less or more amount of money
than Avg. as even if I increase anyone by one I'll have to decrease some other by one also to get toal money unchanged.
Avg Avg - 1 Avg + 1 Avg Avg
So difference(avg - 1, avg + 1) = 2 ..(not within a cent)
2) if Avg is not integer
i want to take minimum money through hand . Now as I need to take money from underpairs, I try to take minimum money from them
Eg .. if Avg = 3.3333, I take 3 from them.
So I take floor(Avg) from them and hope that all money equalizes within a cent amongst all people.
# Note : average of OverPairs (avgOver) avgOver > Avg necessarily. So I want to reduce it to take it to ciel(Avg) or less.
----------------------------------------------------------------------------------------------------- -> Ciel(Avg) -> integer
...................................................................................................... -> Avg -> floating point
----------------------------------------------------------------------------------------------------- -> floor(Avg) -> integer
There are people who overpaid . Let sum they paid be someOver and obviously the average money paid by them (avgOver)
avgOver > Avg
So in hope to decrease the avgOver, I reduce the sumOver by money I recieved from underpairs (floor(Avg) - expence[i] from every underpair i)
Now again I find average avgOver .....
if avgOver < ciel(Avg) then it means Now Overpairs can have equal money within no one having to pay more than ciel(Money)
So i need not to take more money
ANS = money took from underpairs sigma(floor(Avg) - expence[i] from every underpair i)
else I want to take more money from underpairs such that avgOver reaches ciel(Avg)
# So I want total Money Paid by OverPairs.. wantedMoney = ciel(Avg) * overPairs(number of overpairs)
money I have alreadyGiven... presentGivenMoney = money i took from underpairs
more money required ... moreMoneyRequired = sumOver - (wantedMoney) .. This money come from underpairs (moreMoneyRequired < numver of underpairs)
ANS = totalMoney = presentGivenMoney + (moreMoneyRequired);
int sum = 0;
ReplyDeletefr (i, 0, n) {
int dollar, cent;
char temp;
cin >> dollar >> temp >> cent;
expense[i] = dollar * 100 + cent;
sum += expense[i];
}
bool isAvgInteger = (sum % n) == 0;
double average = (double)sum / (double)n;
int underPaidAverage = floor(average);
int overPaidAverage = ceil(average);
int moneyTranferred = 0, overPairs = 0, overPaidSum = 0;
fr (i, 0, n) {
if (expense[i] < underPaidAverage) {
moneyTranferred += underPaidAverage - expense[i];
} else if (expense[i] > underPaidAverage) {
overPairs++;
overPaidSum += expense[i];
}
}
int overPaidSumToGet = overPaidAverage * overPairs;
int overPairsSumReducedTo = overPaidSum - moneyTranferred;
int ans;
if (overPairsSumReducedTo <= overPaidSumToGet) {
ans = moneyTranferred;
} else {
ans = moneyTranferred + (overPairsSumReducedTo - overPaidSumToGet);
}
double dollars = (double)ans / 100.0;
printf("$%0.2lf\n", dollars);
https://dheerajvatscodinator.blogspot.com/2017/09/10137-trip-uva.html
ReplyDelete