Коррупция - непобедима?

[LuckyZeeRo]

Всем привет!
Пока подтягиваю знания по C++ для решения целевой задачи, о которой писал ранее, решил добить старую добрую олимпиадную задачу, которую еще встречал в школьные времена во время подготовок. По Java у них беда (JIT не работает, 90мс минимум). На вид простая, на алгоритм - простая. На прохождение тестов - адовая.
Сама задача:
https://www.e-olymp.com/ru/problems/21

Классика, жадный алгоритм. Насколько я понял, за каждую "итерацию" нам нужно мержить 2 минимальные суммы, чтобы за N-1 итераций забрать как можно меньше денег у фирмы. Чтобы не парится на первое время с массивами и смещением элементов, используем multiset<>, идеально подходит для хранения возможных повторяющихся значений в RB-дереве. Получился примерно такой код (*):

Спойлер: Код

#include <iostream>
#include <iterator>
#include <set>

using namespace std;

int main() {
    // read data
    int amount;
    double percent;
    multiset<double> cash;

    cin >> amount >> percent;
    percent = 1 - (percent / 100.0);

    double input;
    for (int i = 0; i < amount; ++i) {
        cin >> input;
        cash.insert(input);
    }

    // remove first & second lowest elements
    // apply new value and insert
    while (amount-- > 1) {
        auto it_orig = cash.begin(), it = it_orig;
        double summ = percent * ((* it++) + (* it++));
        cash.erase(it_orig, it);
        cash.insert(summ);
    }
    cout << * cash.begin();
    return 0;
}

И вот незадача - по тестам проходит только 50% положительно, 1 тест выходит за время (ну да ладно, это на десерт), остальные неправильный ответ. (Для отправки решений нужна регистрация)

Вот здесь загвоздка. Ничего не известно о выходной точности, но не помогает ни округление до 2 (еще меньше заходит), ни увеличение точности (long double - те же 50%). И все же как то ребята порешали некоторые...

Вдруг есть идеи? Какие еще подводные камни могут быть?

 

[Code]

Выходные данные #1
4151.50

кажется с форматом все понятно, 2 знака после запятой, типа копейки
а вот как округлять промежуточные расчеты непонятно
а то это бред пытаться по тестам домыслить условие
мне удалось до 75% поднять процент прохождения, и дальше эта лотерея надоела

 

[Code]

мб идеи у меня были верные, но я накосячил с реализацией, поэтому напишу, что пытался сделать
моя идея в том, что на счету должно быть целое число гривен и копеек, поэтому я вместо даблов хранил инты * 100. а дальше пытался понять, как округлять комиссию. ни вверх, ни вниз не дало осоьо резултьтата, ближе всех оказался round, но 25% все равно остались неверными.
непроходящий в 100 мс тест кстати влез в лимит после замены double input на int
...хотя может в этом же и моя ошибка, могут ли быть исходные суммы на счетах дробными опять же непонятно, в примере все целое

 

[LuckyZeeRo]

Выходные данные #1
4151.50

кажется с форматом все понятно, 2 знака после запятой, типа копейки
а вот как округлять промежуточные расчеты непонятно
а то это бред пытаться по тестам домыслить условие
мне удалось до 75% поднять процент прохождения, и дальше эта лотерея надоела

Странно, у меня какой то 1 не зашел с подобными условиями (70%):

Спойлер: Код с 70%

#include <iostream>
#include <iterator>
#include <cmath>
#include <set>

using namespace std;

int main() {
    // read data
    int amount;
    int percent;
    multiset<long long> cash;

    cin >> amount >> percent;
    percent = 100 - percent;

    int input;
    for (int i = 0; i < amount; ++i) {
        cin >> input;
        cash.insert((input * 100));
    }

    // remove first & second lowest elements
    // apply new value and insert
    while (amount-- > 1) {
        auto it_orig = cash.begin(), it = it_orig;
        long long summ = (long long) round(percent * ((* it++) + (* it++)) / 100.0);
        cash.erase(it_orig, it);
        cash.insert(summ);
    }

    long long result = * cash.begin();
    cout << result / 100 << '.' << result % 100;
    return 0;
}

В чем наши отличия?
Я раньше пытался делать округления, но не на промежуточных, а на выходе, в итоге получалось 45%.
Короче я так понимаю нужно решать методом проб и анализов прохождения тестов. Вот у меня на 70% не зашли тесты: 13-15, 18-20, а при 50% (первых проб с double) зашли тесты 14 и 15 . Там проценты / счета хранились в float:

Спойлер: Код с 50%

#include <iostream>
#include <iterator>
#include <set>

using namespace std;

int main() {
    // read data
    int amount;
    float percent;
    multiset<float> cash;

    cin >> amount >> percent;
    percent = 1 - (percent / 100.0F);

    float input;
    for (int i = 0; i < amount; ++i) {
        cin >> input;
        cash.insert(input);
    }

    // remove first & second lowest elements
    // apply new value and insert
    while (amount-- > 1) {
        auto it_orig = cash.begin(), it = it_orig;
        float summ = percent * ((* it++) + (* it++));
        cash.erase(it_orig, it);
        cash.insert(summ);
    }

    float result = ((float) ((long long) (* cash.begin() * 100.0F))) / 100.0F;
    cout << result;
    return 0;
}

Похоже что считывать целые или не целые проценты / счета не имеет различий.

 

[Code]

вот такое говно дало 75%

Спойлер

#include <cmath>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <set>

using namespace std;

int main() {
    // read data
    int amount;
    int percent;
    multiset<long int> cash;

    cin >> amount >> percent;

    long int input;
    for (int i = 0; i < amount; ++i) {
        cin >> input;
        cash.insert(input * 100);
    }

    // remove first & second lowest elements
    // apply new value and insert
    while (amount-- > 1) {
        auto it_orig = cash.begin(), it = it_orig;
        long int summ = (*it++) + (*it++);
        summ = round(summ - percent * summ / 100.0);
        cash.erase(it_orig, it);
        cash.insert(summ);
    }
    cout << fixed << setprecision(2) << *cash.begin() / 100.0;
    cin >> amount;
    return 0;
}

 

[LuckyZeeRo]

вот такое говно дало 75%

Спойлер

#include <cmath>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <set>

using namespace std;

int main() {
    // read data
    int amount;
    int percent;
    multiset<long int> cash;

    cin >> amount >> percent;

    long int input;
    for (int i = 0; i < amount; ++i) {
        cin >> input;
        cash.insert(input * 100);
    }

    // remove first & second lowest elements
    // apply new value and insert
    while (amount-- > 1) {
        auto it_orig = cash.begin(), it = it_orig;
        long int summ = (*it++) + (*it++);
        summ = round(summ - percent * summ / 100.0);
        cash.erase(it_orig, it);
        cash.insert(summ);
    }
    cout << fixed << setprecision(2) << *cash.begin() / 100.0;
    cin >> amount;
    return 0;
}

Изменили:

long long result = * cash.begin();
cout << result / 100 << '.' << result % 100;

На:

cout << fixed << setprecision(2) << * cash.begin() / 100.0;

Получили прохождение 13 теста. Возможно там результат без точки, но было бы слишком глупо. Обычно там все задания адекватные в этом смысле.

 

[Reality_SC]

cout << result / 100 << '.' << result % 100;

Это некорректный код. Что будет при result = 109?

 

[LuckyZeeRo]

Это некорректный код. Что будет при result = 109?

Хм, точно
Это уже моя параноя на заход по времени

 

[Code]

Это уже моя параноя на заход по времени

ну уж до такого можно не параноить) не заходит по времени скорее всего вариант с максимальным N = 100000 просто из-за количества. а всё вне цикла - пустяк

 

[jwplaster]

Так. Если я правильно понимаю, это хрень должна работать так:
В результате всего остаётся лишь 1 счёт.

Мммм...
Пусть:
n=6 p=10
1000 1300 1500 1800 2000 2200
Сразу вспоминается какая-нить задачка экономическая ЕГЭшная. Только там мы прибавляли процент и платили его так, чтоб в меньшее количество месяцев покрыли, а здесь отнимаем, но кол-во месяцев статичное. Попробуем сделать так, чтоб всё шло от меньшего к большему:
((((1000*0.9+1300*0.9)*0.9+1500*0.9)*0.9+1800*0.9)*0.9+2000*0.9)*0.9+2200*0.9=7254,477

Или 1000*p^n-1+1300*p^n-1+1500*p^n-2+1800*p^n-3+2000*p^n-4+2200*p^n-5

Однако, по понятным причинам, эта сумма будет меньше самой большой. Просто потому что процентов много.
Попробуем стандартно, брать меньшее из чисел в нынешнем разряде пар:
(1000*0.9+1300*0.9)=2070
(1500*0.9+1800*0.9)=2950
(2000*0.9+2200*0.9)=3780
(2070*0.9+2950*0.9)=4518
И последнее:
(4518*0.9+3780*0.9)=7468,2
О, уже больше!
Попробуем другой вариант:
Пусть будем пытаться брать процент всё так же от самого наименьшего, но только проверять каждый раз.
Выходит:
(1000*0.9+1300*0.9)=2070
(1500*0.9+1800*0.9)=2950
И тут, из оставшихся сумм-пар у нас имеется 2000 и 2200, второе из которых больше, чем первая сумма. Следовательно, берём уже её
(2000*0.9+2070*0.9)=3663
2200=2200
Выходит 3 различных числа:
2950, 3663, 2200
Берём опять по парам меньшее:
(2950*0.9+2200*0.9)=4635
3663=3663
И последнее складываем:
(4635*0.9+3663*0.9)=7468,2
Похоже, самый лучший результат, ещё и как предыдущий вышел. Вау! Но, так ли это? Давайте немного поменяем местами числа:
(1000*0.9+1500*0.9)=2250
(1300*0.9+1800*0.9)=2790
(2000*0.9+2200*0.9)=3780
Теперь
(2250*0.9+2790*0.9)=4536
3780=3780
И в конце:
(4536*0.9+3780*0.9)=7484,4
Воу! Немного, но всё же больше! Как так вышло?
Что у нас получилось то?
Сначала разница между числами была 200, теперь 500. Может, всё дело в увеличении разницы между парами?
(1000*0.9+2200*0.9)=2880
(1300*0.9+2000*0.9)=2970
(1500*0.9+1800*0.9)=2970
(2880*0.9+2970*0.9)=5265
2970=2970
(5265*0.9+2970*0.9)=7411,5 , что всё же немногим меньше результатов.

И вот как из этого всего найти зависимость некую? Я пока ничего не вижу...

 

[Code]

Воу! Немного, но всё же больше! Как так вышло?

так вышло потому что ты просчитался)

(1500*0.9+1800*0.9)=2950

=2970
если посмотреть внимательнее, раскрыть скобки в этих двух вариантах, то становится ясно что ты просто слагаемые чуть местами поменял. результат и там, и там 7484,4

Мммм...
О, уже больше!
Вау! Но, так ли это?
Воу! Немного, но всё же больше! Как так вышло?

можно не устраивать клоунаду, а конструктивно предложить, почему уже предложенный автором вариант складывать два наименьших счета плох. пока кажется что это нормальное решение, просто непонятно как его нормально запрогать из-за кучи округлений и нечеткой постановки задачи.

 

[jwplaster]

можно не устраивать клоунаду, а конструктивно предложить, почему уже предложенный автором вариант складывать два наименьших счета плох. пока кажется что это нормальное решение, просто непонятно как его нормально запрогать из-за кучи округлений и нечеткой постановки задачи.

Да нет там никаких округлений.

Вообще, у меня просто сначала появились последние два результата, пересчитав которые я немного впал в ступор.
Т.к. число таки меняется.
1) ((x1k+x2k)k+(x3k+x4k)k)k+(x5k+x6k)k !=
2) (x1k+x2k)k+((x3k+x4k)k+(x5k+x6k)k)k !=
3) (x3k+x4k)k+((x1k+x2k)k+(x5k+x6k)k)k

1) ((1*2+2*2)*2+(3*2+4*2)*2)*2+(5*2+6*2)*2=124
2) (1*2+2*2)*2+((3*2+4*2)*2+(5*2+6*2)*2)*2=156
3) (3*2+4*2)*2+((1*2+2*2)*2+(5*2+6*2)*2)*2=140
Я вот это хотел показать. А я ведь всего лишь поменял местами слагаемые. Только вот скобки попереставил, в 3х случайных возможных вариантов работы программы.

А, и это не клоунада. Я просто в таком виде пишу свои мысли) Я вот там в сообщении и разбирал для себя задачку. Варианты, какие придумывал и тэдэ. Вот.

 

[Code]

Да нет там никаких округлений.

всмысле нет? то что в твоих примерах не ушло дальше двух знаков после запятой не означает что так будет в других примерах.

Т.к. число таки меняется.

ну естественно меняется.

Я просто в таком виде пишу свои мысли) Я вот там в сообщении и разбирал для себя задачку.

жаль решению контеста на 100% это не помогло никак)

 

[IlyaHaker]

Очевидно же, что чем меньше сумма двух чисел будет, тем меньше будет произведение их на p/100
Значит нужно складывать 2 минимальных числа, умножать на (1 - p/100) и записывать в этот "мультисет", ведь он автоматически все сортирует. Все там правильно в алгоритме, чего вы устроили))

Еще одно замечание:
double fract = *cash.begin() - (int)*cash.begin();
if (fract < 0.58 && fract > 0.52) cout << *cash.begin();
при таком условии заходят тесты 14-15, очевидно, в выводе числа что-то. Какое-то число с дробной частью в промежутке (0.52, 0.58) корректно выводить в double, а остальные в виде, указанном выше, на 75% захода

 

[jwplaster]

Очевидно же, что чем меньше сумма двух чисел будет, тем меньше будет произведение их на p/100
Значит нужно складывать 2 минимальных числа, умножать на (1 - p/100) и записывать в этот "мультисет", ведь он автоматически все сортирует. Все там правильно в алгоритме, чего вы устроили))

Еще одно замечание:
double fract = *cash.begin() - (int)*cash.begin();
if (fract < 0.58 && fract > 0.52) cout << *cash.begin();
при таком условии заходят тесты 14-15, очевидно, в выводе числа что-то. Какое-то число с дробной частью в промежутке (0.52, 0.58) корректно выводить в double, а остальные в виде, указанном выше, на 75% захода

ну, вообще, я о том и говорил. Что так и надо делать. Только вот прикинь:
Простой перебор чисел уже выходит за рамки времени (по крайней мере, в C# точно). А терь прикинь, что это надо ещё и каждый заход выставлять числа в порядке возрастания.

 

[IlyaHaker]

ну, вообще, я о том и говорил. Что так и надо делать. Только вот прикинь:
Простой перебор чисел уже выходит за рамки времени (по крайней мере, в C# точно). А терь прикинь, что это надо ещё и каждый заход выставлять числа в порядке возрастания.

в мультимножестве идет автоматическая сортировка, достаточно всегда брать первые 2 элемента
хз к чему ты это все расписывал, ведь у тса написано тоже самое, только другими словами

 

[Code]

хз к чему ты это все расписывал, ведь у тса написано тоже самое

+

только другими словами

замечу, намного более короткими и осмысленными

Простой перебор чисел уже выходит за рамки времени

естественно, только простой перебор никто не предлагает. простой перебор это сложность n факториал или даже n!*(n-1)!
(на первом шаге это n(n-1) вариантов взять 2 числа, потом (n-1)(n-2) и все перемножается и так далее). это самый самый худший вариант решения

А терь прикинь, что это надо ещё и каждый заход выставлять числа в порядке возрастания

а брать два минимальных числа и вставлять результат в multiset это n*log(n) на изначальную сортировку + еще n*log(n) вставка в multiset результатов сложений (вставить элемент в отсортированный multiset это log(n) + так надо сделать n раз), получается примерно 2*n*log(n) действий, что во много быстрее полного перебора.
непонятно зачем ты сравниваешь почти идеальное по сложности решение с наихудшим. лучше только линейное время, но вряд ли такая задача решается за линейное время.

 

[IlyaHaker]

ммм, теория алгоритмов

 

[jwplaster]

естественно, только простой перебор никто не предлагает. простой перебор это сложность n факториал или даже n!*(n-1)!
(на первом шаге это n(n-1) вариантов взять 2 числа, потом (n-1)(n-2) и все перемножается и так далее). это самый самый худший вариант решения

а брать два минимальных числа и вставлять результат в multiset это n*log(n) на изначальную сортировку + еще n*log(n) вставка в multiset результатов сложений (вставить элемент в отсортированный multiset это log(n) + так надо сделать n раз), получается примерно 2*n*log(n) действий, что во много быстрее полного перебора.
непонятно зачем ты сравниваешь почти идеальное по сложности решение с наихудшим. лучше только линейное время, но вряд ли такая задача решается за линейное время.

ТАК СТОП СТОП СТОП. У меня щас мозг взорвётся.

У нас имеется некий набор N элементов, которые хранятся в памяти.
Я говорю, что перебор этих самых элементов и поиск среди них даже одного наименьшего уже задача, выбивающаяся из рамок 1/10 секунды.
Ты мне говоришь, что существует некая магическая функция, выполняющая ровно ту же функцию, но, в несколько раз быстрее. И вот вопрос. Как, если оно всё реализовано в рамках одного языка?
P.S. Я кншн загуглил мультимножества, и понимаю, что это такое. Просто я никогда не сталкивался особо с проблемами времени, т.к. пишу на C#. Но всё же, как так в плюсах вышла такая дичь? Сортировка эта идёт на уровне... чего? Как это работает так? лол и... зачем?

 

[jwplaster]

в мультимножестве идет автоматическая сортировка, достаточно всегда брать первые 2 элемента
хз к чему ты это все расписывал, ведь у тса написано тоже самое, только другими словами

Ну, я писал это всё не ТС, а людям, которые вдали от программирования и забредут в эту тему в поисках интересного. Я просто размышлял "вслух" ну и решил отправить для остальных. Вот и всё