Monday, April 8, 2013

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:
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?


  1. 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
    same 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);

  2. int sum = 0;
    fr (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) {
    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);