Ресторан(10)

Хм... сделал, закрыв не совсем все условия, но валидатор принял. 0) Создаю в классе список, который будет хранить ролики для показа. 1) Пишу компаратор, который выводит сначала самые оплачиваемые ролики. 2) Пишу метод, который делает следующее: - сортирует список из хранилища по компаратору - для каждого видео в списке, если оно умещается по времени, а также имеет положительное количество оставшихся просмотров и ещё не находится в списке для показа, добавляю его в список роликов для показа, также добавляю в свежесозданный вспомогательный список - если в конце работы метода вспомогательный список не пустой, рекурсивно вызываю этот же метод - когда больше никакие ролики не подойдут, вспомогательный список окажется пустым и метод завершится 3) Сортирую получившийся список на показ ещё раз по тому же самому компаратору. Сдал с 3-й попытки - в первый раз забыл убрать временную строчку, которую выводил в консоль, второй раз забыл не показывать видео, число оплаченных просмотров которых закончилось.

Для понимания того как решать такие задачи очень помогло это видео Видео Там есть ссылка на гит и решение всяких разных похожих задач.

чокнутый валидатор. Мучил меня, когда уже результат был правильный, но по двум пунктам не пропускал. Искал решения и так и эдак и вот сделал откат решения, нажал на проверку и о чудо! Взял и принял. Ничего не понимаю, но главное прорвался!

решил в меру понятия, проверил по мере возможности на соответствие всем требованиям, всё как в выводе. Гарантировано не прошёл валидацию... скопировал готовое решение (иначе это уже всё слишком на долго затягивается 2,5 недели) ну вот разве что надо будет всё таки в готово решении разобраться что и почему как

Получилось по принципу "рюкзака"! Комментарий Maxim Dimitrov помог не улетать в тайм-аут при проверке!

Часа два разбирался с алгоритмом, решил делать через рюкзак, сделал, все работает, валя не принимает по 1 и 4 пунктам. Начал разбираться, улучшил алгоритм, сделал доп проверки перед рекурсией. У меня все работает, у вали опять 1 и 4. Ломал голову, почитал кучу постов отсюда, ничего не помогает. Плюнул, разобрался в "правильном решении", изначально в эту сторону думал, переделал кучу кода, а валя непреклонен. В итоге убил целый день.20 попыток. А проблема оказалась в сортировке уже правильно отобранного списка. Вот так не принимал.

bestList.stream().sorted(
        Comparator.comparingLong(Advertisement::getAmountPerOneDisplaying).reversed()
        .thenComparingLong(a -> a.getAmountPerOneDisplaying() / a.getDuration()));

А вот так можно.

bestList.sort((o1, o2) -> {
            long l = o2.getAmountPerOneDisplaying() - o1.getAmountPerOneDisplaying();
            return (int) (l != 0 ? l : o2.getDuration() - o1.getDuration());
        });

Я не очень со стримами и лябдами дружу, кто в теме, подскажите, это прихоть вали, или действительно не так сортирует, как надо. Вывод: Валидатор показывает и дает рекомендации совсем не на те места, которые ему не нравятся, придется угадывать здесь самому, почему он капризничает. Обращение к создателям. Если вы в задаче не в состоянии наладить подсказки валидатора, уберите их совсем......

Решил через динамическое программирование. Сначала в массиве хранил листы -- ну, удобно же, не надо делать "обратный ход" всё готовенькое лежит в последнем столбце :) Это оказалось ооочень ресурсоёмким решением, которое приводило к тайм-ауту. Поэтому вернулся к классике: прямой ход (заполняем массив, где строки это видеоролики, столбцы это секунды, числами), обратный ход (для каждой строки из последнего столбца восстанавливаем список использованных видеороликов). Потом проверки готовых решений на 4.1, 4.2 и сортировка из прошлых пунктов. Задача отличная, заставила подумать. Не халявьте, отправляя жадные алгоритмы (валидатор и их примет) :)

Подсказка для тех, кто делает через рекурсию и улетает в тайм-аут при валидации: При каждой итерации проверяйте, может ли ваш текущий вариант оказаться оптимальным по цене, или уже нет. Если нет, обрубайте ветку итерации, это сокращает время.

Не получилось решить с помощью рюкзака (рекурсивный подход), уходил в бесконечность. Период ожидания при роликах 10 штук около 2 минут. Пробовал создавать отдельный список, где есть только hits > 0 и потом использовать его в качестве подбора, но не получилось. Ожидание слишком высокое. Как решил я. Во 1-х переопределил toString() в соответствии с выводом в задании

First Video is displaying... 50, 277

2) Имплемитировал Comparable<Advertisement> и переопределил метод compareTo(), который сравнивнивает по уменьшению стоимости одного показа и если стоимость одинаковая, то сравнивает по увеличению стоимости показа одной секунды рекламного ролика в тысячных частях копейки. 3) Сделал отдельный метод, который вычисляет стоимость показа рекламного ролика в тысячных частях копейки

amountPerOneDisplaying * 1000 / duration;

4) В самом решении использовал "жадный алгоритм". В отсортированном списке добавлял ролики до тех пор, пока время позволяло. Несколько попыток потерял из-за того, что запускал валидацию не с корневого файла, а с пакета ad класс AdvertisementManager. В результате выдавал ошибку:

Ошибка в файле com/javarush/task/task27/task2712/ad/AdvertisementManager.java в строке :  3
Не могу найти описание класса "ConsoleHelper" в packageе "com.javarush.task.task27.task2712". Возможно вы забыли его импортировать (указать в import)

Видимо какой то баг. Итого 9 попыток. -1162 участников на 10 задании. | 29% | 3343 | (8.76) |

Задача решена, за алгоритм спасибо Кириллу и задачу про рюкзак. Что не понравилось, перебор в алгоритме достаточно однобокий, попытка исправить такое поведение с более полным перебором ведёт к превышению времени работы алгоритма, в итоге существует совсем не хилая вероятность пропустить нужную комбинацию. Так же есть большая претензия к составителям задачи, а именно к тестовым данным и форматам хранения, в частности возможна комбинация, при которой показ вообще ни чего не стоит и в итоге ролик мы просто не показываем, хотя количество показов сильно больше нуля.