###
Thoughts on UVA: 10137: The trip

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:

*15*
*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