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.
5 Likes
The actual canon plural of âOodâ is âOodâ. One Ood, several Ood; they are the Ood.
1 Like
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,
2 Likes
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 
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 
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);
}I had timeout problem in big random but curiously I got 100% when submitted. so why complain?
anyway my solution in groovy except for the input is only 16 lines length.