Doctor Who - The Gift puzzle discussion

IIRC, I found the ceiling function useful. Or the floor. One or the other.

has anybody solved the gift puzzle? i compiled it with GNU using code::blocks and it works perfectly, but the tests either add a 0 in the beginning of the output or it says this http://prntscr.com/av6czo

Bonjour
Pour le dernier niveau du cadeau, je n’arrivait pas à le faire. J’ai donc afficher toute les valeurs des budgets et j’ai eu à un moment de l’affichage un budget avec trois petits point et un trou
9482646137…62
Est ce que c’est normal? Est ce que je dois verifier que ce soit bien un chiffre?

Quand tu affiches trop de choses, c’est coupé.
Un peu comme une citation de texte :
“blablabla blablabla […] blablabla blablabla”

Bonjour,
J’arrive à passer tous les tests de l’ide et pourtant juste 33% des tests passent après soumission.
échecs sur les tests 2, 3, 5, 6, 7 et 8
J’utilise bash
Une idée ?

IMHO the sorting for this solution is a really bad thing because after you sort the result you don’t get which Ood pays what amount. This is really visible by a test case provided to the problem:

Input
3
100
100
1
60
Output
1
49
50

With this the first Ood would pay 1 from its 100 budget, the second Ood would pay 49 from its budget of 1, and the last Ood will pay 50 from its 60 budget. And this would violate the rules of the Doctor.

4 Likes

The actual canon plural of ‘Ood’ is ‘Ood’. One Ood, several Ood; they are the Ood.

The rule says that the optimal solution is the one for which the highest contribution is minimal. In your solution the highest contribution is 60 which is clearly greater than the 50 which the system expects.

Think about this way: they have budgets of 100, 1 and 60. The second Ood can only pay 1, that means the rest should pay 99 total. Now, they want to split this 99 in such a way that the highest contribution is minimal. It would be 49.5-49.5, but that’s not valid because the Doctor wants each financial participation to be an integer of the local currency (nobody should give any cents).So they split it 49-50,

1 Like

If we also sort the input budgets then it can perfectly match the outputs

Is this really worth 100XP? Got it done in about 15mins maximum. From the first ood to the last, calculating the mean left.

It is nowhere mentioned that we can rearrange the elements in any order, as the results of the test cases I figured out that all outputs are in sorted order. Because if you re-arrange, there is problem that you cannot find out who will pay how much.
I think this should be mentioned in the problem or this should not be allowed.

quote from the statement:

Output
If it is possible to buy the present : N lines, each containing the contribution of a participant. The list is sorted in ascending order.

1 Like

Can you please give a better “Budget limit” case, because my code is passing your test, but fails when I submit ?

Found one:

IN:
3
100
12
100
43

OUT:
12
43
45

Because now my program outputs:
12
44
44

And now I can look for the answer :slight_smile:

I agree with the comments saying it is an easy puzzle. I spent hours on some easy ones because they needed optimization and now I did it in only 5 minutes 100% succeeded. I would also like to point out that it talks about the “glutton algorithm”. I couldn’t find relevant informations and wrote a code with no glutton in it, with less code lines than the top rated solution. I sincerely think that puzzle needs to be upgraded.

My progress 100%; achievements 0/2

Could you please, advise where is the problem?

There are 3 criteria in this puzzle:

  • no Ood can pay more than his maximum budget
  • the optimal solution is the one for which the highest contribution is minimal
  • if there are several optimal solutions, then the best solution is the one for which the highest second contribution is minimal, and so on and so forth…

You passed the first one, not yet the 2nd or 3rd.
You can try again to find better solutions to get 2/2 achievements.

Thanks for clarifying. Progress 100% is misleading, thou.

edit:
Well, I still don’t get it. I think I passed all the tests with accordance to the three rules you’ve mentioned. Where is my misunderstanding of the puzzle?

edit2:
I got that achievements without code change.
Maybe it was a manual touch :wink:

:+1::grinning:

Hey, I have a problem with the last test “Big random”. What may be causing the problem ?

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <list>

#include <numeric>

using namespace std;

int checkBudget(int& budget, vector<int> &costs)

{

    return accumulate(costs.begin(), costs.end(), 0);

}

void makeDistributionList(int &budget, int &sum_budget, vector<int> &costs, vector<int> &new_costs, list<int> &t_list)

{

    for (auto i = costs.begin(); i != costs.end(); i++)

    {

        if (*i < budget / costs.size())

        {

            new_costs.push_back(*i);

            sum_budget -= *i;

        }

        else

        {

            t_list.assign(i, costs.end());

            break;

        }

    }

}

void distributeBudget(int &sum_budget, vector<int>& costs, vector<int> &new_costs, list<int> &t_list)

{

    int t_sum = 0; // temporary sum, that is a distribution of the sum_budget

    while (!t_list.empty())

    {

        //cout << "LIST SIZE = " << t_list.size() << endl;

        //cout << "SUM BUDGET = " << sum_budget << endl;

        

        t_sum = sum_budget / t_list.size();

        //cout << "TEMP SUM = " << t_sum << endl;

        if (t_list.size() == 1)

        {

            new_costs.push_back(sum_budget);

        }

        else

        {

            new_costs.push_back(t_sum);

            sum_budget -= t_sum;

        }

        t_list.pop_front();

        //cout << "_________________________" << endl;

    }

    list<int>().swap(t_list); // frees up the memory taken by temporary list

}

void viewIndividualCosts(vector<int>& new_costs)

{

    for (auto& c : new_costs)

    {

        cout << c << endl;

    }

}

void gift(int &budget, vector<int>& costs)

{

    int sum_budget = checkBudget(budget, costs);

    if (sum_budget < budget)

    {

        cout << "IMPOSSIBLE";

    }

    else

    {

        sum_budget = budget; // current budget that will be updated after each subtraction

        vector<int> new_costs; // will store final values

        list<int> t_list; // temporary list storing bigger budgets, which need to be distributed

        sum_budget = budget; // current budget that will be updated after each subtraction

        sort(costs.begin(), costs.end(), less<int>()); // sort the costs vector in ascending order to keep the largest budgets at the end of container

        makeDistributionList(budget, sum_budget, costs, new_costs, t_list);

        distributeBudget(sum_budget, costs, new_costs, t_list);

        viewIndividualCosts(new_costs);

    }

}

/**

 * Auto-generated code below aims at helping you parse

 * the standard input according to the problem statement.

 **/

int main()

{

    vector<int> costs;

    int N;

    cin >> N; cin.ignore();

    int C;

    cin >> C; cin.ignore();

    //cout << "C = " << C << endl;

    for (int i = 0; i < N; i++) {

        int B;

        cin >> B; cin.ignore();

        //cout << "B = " << B << endl;

        costs.push_back(B);

    }

    gift(C, costs);

}