Dimchik
Это решение О(n) time, можно в O(1), но я бы не парился))
Lynn «Кофеман»
Основное, неправильно выбраный способ решения «в лоб».
Подсказка: сколько нечётных чисел от 1 до 2N?
Vilena
почему способ решения "в лоб" неправильный?
Роман
почему способ решения "в лоб" неправильный?
не оптимальный, наверняка попросят улучшить
Viktor
почему способ решения "в лоб" неправильный?
не то что “неправильный”, а именно что неоптимальный. в данном случае этот не сильно важно, но бывают задачи где в лоб просто не решается, то есть будет считаться очень долго.
Dimchik
в основном это задачи с AoC 🤣🤣
Viktor
n?
направление верное. теперь надо учесть, что в задаче интервалы не строго 2*N, то есть четные, бывают и нечетные.
Viktor
четвертая задача в контестах всегда в лоб не решается
Lynn «Кофеман»
Потому что перебор миллиарда чисел это долго и если с ними нужно делать хоть что-то нетривиальное, то ты гарантированно не уложишься в лимиты времени.
В общем случае, если твое решение перебирает миллиард чисел значит оно с вероятностью 99.99% неоптимально и нужно придумать другое.
Viktor
направление верное. теперь надо учесть, что в задаче интервалы не строго 2*N, то есть четные, бывают и нечетные.
Зачастую помогает понять, если рассмотреть больше тестов, надо придумать самому. Например, здесь рассмотри вот такие:
3 7
3 8
2 7
2 8
Alexander
Потому что перебор миллиарда чисел это долго и если с ними нужно делать хоть что-то нетривиальное, то ты гарантированно не уложишься в лимиты времени.
В общем случае, если твое решение перебирает миллиард чисел значит оно с вероятностью 99.99% неоптимально и нужно придумать другое.
Есть такая штука, большие данные
Alexander
Я понимаю, что ты про задачу с литкода, это шутка
Lynn «Кофеман»
Есть такая штука, большие данные
Есть. Но не на литкоде в начальных этапах.
И там будут миллиард после выбора оптимального алгоритма против триллионов/квадриллионов в «лобовом»
Viktor
Я понимаю, что ты про задачу с литкода, это шутка
ты шутишь, а там на редите кто-то всерьез обсуждал, что запустил обсчет какой-то задачи AOC в AWS
Alexander
ты шутишь, а там на редите кто-то всерьез обсуждал, что запустил обсчет какой-то задачи AOC в AWS
Я посчитал, что решить 17 день эмуляцией заняло бы 27 часов на одном ядре
Viktor
ты шутишь, а там на редите кто-то всерьез обсуждал, что запустил обсчет какой-то задачи AOC в AWS
просто мап редьюс 😂
Dzianis
ты шутишь, а там на редите кто-то всерьез обсуждал, что запустил обсчет какой-то задачи AOC в AWS
зачем aws если есть yt 😃
Alexander
В прошлом году я хотел рыб сделать на яндексовом MR кластере
Alexander
там 2Т выходная таблица получалась
Alexander
Кстати, поясните плиз
Alexander
17 день
Alexander
цикл я нашел просто перебором seed и размера цикла
Роман
@vylenne Вы senior front end?
Alexander
int64_t s = 15;
int64_t v = 1015;
auto seed_height = chamber.run(s);
auto cycle_height = chamber.run(v) - seed_height;
auto leftover_height = chamber.run((Q - s) % v) - cycle_height + seed_height;
int64_t total_height = seed_height + ((Q - s) / v) * cycle_height + leftover_height;
cout << total_height << endl;
Alexander
почему код выше не работает? chamber.run(x) возвращает текущую высоту, chamber не сбрасывается
Alexander
ошибка ровно в 2 seed_height
Alexander
то есть я прогоняю сид, нахожу высоту которую добавляет цикл и потом прогоняю еще остаток цикла до Q
Lynn «Кофеман»
Lynn «Кофеман»
вот именно, открывающие есть, а закрывающих нет!
Alexander
браузер сам закроет
Lynn «Кофеман»
мой парсер сломался! 😂
Alexander
убрал чуть вывода, он там в общем ни о чем
Evgeniy
Поделитесь инпутом со вчерашнего дня. Проверить эвристику.
Evgeniy
На моих данных терпимо считает. Но неясно, будет ли на других так же.
Dimchik
https://github.com/StaffEngineer/adventofcode-2022/blob/main/day19/input.txt
Dimchik
ответ 1294 и 13640
Evgeniy
Совпало. Максимум 40 миллионов перебирало.
Evgeniy
(28, 50, 8, 16, 3, 7, 5, 4, 0), counter=40000000 cacheHits=6850906 (0,17127%, maxGeHits=20133853 (0,50335%)
Evgeniy
Проценты только неверные, на 100 не умножено
Evgeniy
https://github.com/edevyatkin/AdventOfCode/blob/2097f604f637cb3d7cc90d98e27c437c380ac037/AdventOfCode2022/Day19.cs#L56
Evgeniy
Немного поправил эвристику, вместо использования времени поставил просто -1. Скорость выросла аж в 4 раза. Считало где-то 30 с чем-то секунд, теперь около 7 (на данных из примера). Оптимизировать можно бесконечно, надо остановиться =)
Dimchik
Viktor
Вот и пригодился бинарный поиск, во второй части сегодняшней 🙂
Alexandr
Вот и пригодился бинарный поиск, во второй части сегодняшней 🙂
у меня диапозон был 0..1e15
Viktor
А, диапазоны. Просто цикл запустил от 1 до 1e13 и проверил где граница.
Viktor
у меня была на 1e13
Viktor
ну да, сами границы в коде захардкодил.
Dzianis
Что именно? 🤔
Ответ)
Я сегодня вторую часть просто перебором, с момента где diff между a и b менялся с + на -, добавлял значащую цифру)
Viktor
Ответ)
Я сегодня вторую часть просто перебором, с момента где diff между a и b менялся с + на -, добавлял значащую цифру)
не, бинарный поиск же 😄
Dzianis
Но к слову норм задачи вернулись, не хардкор как в середине aoc, вполне сносно и с удовольствием можно поделать)
Viktor
хотя может можно было и не упарываться
Viktor
Но к слову норм задачи вернулись, не хардкор как в середине aoc, вполне сносно и с удовольствием можно поделать)
ага, предрождественский чил начался
Dzianis
не, бинарный поиск же 😄
А откуда у тебя гарантия монотонности?
Если бы там была степенная зависимость можно было бы выйти из клюшки и пытаться найти ответ в бесконечности)
Viktor
А откуда у тебя гарантия монотонности?
Если бы там была степенная зависимость можно было бы выйти из клюшки и пытаться найти ответ в бесконечности)
gut feeling, хаха. ну если была бы степенная, то да, но в root операция + (у меня). соответственно должна быть монотонной.
Evgeniy
А я уже начал делать вычислением, переделывая выражения
Evgeniy
Ну да ладно)
Viktor
gut feeling, хаха. ну если была бы степенная, то да, но в root операция + (у меня). соответственно должна быть монотонной.
не то сказал. не в root, в humn
Viktor
вот если бы там было умножение скажем, то как-то уже хз.
Dzianis
gut feeling, хаха. ну если была бы степенная, то да, но в root операция + (у меня). соответственно должна быть монотонной.
Root_A + Root_B * humn * humn
ну вот так же могло было быть)
Dzianis
да, именно. но так нет.
Лан) это я оправдываюсь что руками подобрал ответ задачи 😃
Хорошая мысль тут бинпоиск)
Evgeniy
хм, а как ты хотел?
Заменить один из ключей в выражении root = a * b (например) на a * a. В других выражениях b заменить тоже на a. Потом сделать что-то подобное:
a = b + c
c = a - c
c = a - b
и так далее, для вычитаний, делений и умножений. И так же, как к первой части отсортировать топологической сортировкой.
Viktor
Неплохо
Viktor
С бинарным поиском даже мысли не было. Это (бинпоиск) легче, быстрее.
непрерывные и гладкие кривые наше всё
Viktor
как Вселенная