@ctci_chat_ru - страница 465

Ilia

чтобы угадать число из 14 цифр нужно сделать 42 попытки. с учетом рейт лимитера придется потратить день, наверное, да. но можно если очень не хочется решать задачу 😂

получается так можно любую задачу решать, 5 аккаунтов и время сабмита в 3 минуты :D

Viktor

получается так можно любую задачу решать, 5 аккаунтов и время сабмита в 3 минуты :D

а в разных аккаунтах разные ж инпуты

Ilia

а в разных аккаунтах разные ж инпуты

точно, я забыл )

Viktor

думаю если с одной кукой зайти с разных айпишников, то не поможет

Viktor

он по куке блокирует

Viktor

но я уверен, что кто-то на редите уже написал такой скрипт для угадывания

Viktor

😂

Evgeniy

я со второй части затупил чет жестко: правильно я понимаю, что надо найти единственную точку в квадрате 0..4_000_000, которая никем не детектится? у меня не укладывается по каким правилам надо найти эту точку, там же непересекающихся тысячи будут

Там специально сделали, чтобы она была одна

Evgeniy

самое смешное, я для второй части просто использовал решение первой части и запустил брутфорс :D

Аналогично, только ещё склеивал интервалы

Ilia

Аналогично, только ещё склеивал интервалы

А я мердж интервалов в первой части сделал, поэтому во второй просто добавил проверку, что их 2 :)

Evgeniy

Всё так

Ilia

Но условия сегодня непонятно написаны конечно

Ilia

И примера визуального нет, сразу было бы понятно

Evgeniy

Мне кажется это специально

Evgeniy

В этом же и суть

Alexander

для первой computing time 0.187ms, для второй 3.427s

$ make release g++-7 -c -std=c++17 -O2 -I.. -I../.. -Wall code.cpp -o code.o g++-7 code.o ../../all.o -o a.out $ time ./a.out 56000011 13673971349056 real 0m0.591s

Alexander

но можно же распараллелить на несколько аккаунтов!

так там разные ответы на разных аккаунтах

Dzianis

$ make release g++-7 -c -std=c++17 -O2 -I.. -I../.. -Wall code.cpp -o code.o g++-7 code.o ../../all.o -o a.out $ time ./a.out 56000011 13673971349056 real 0m0.591s

printf(56000011) printf(13673971349056) 😄?

Ilia

$ make release g++-7 -c -std=c++17 -O2 -I.. -I../.. -Wall code.cpp -o code.o g++-7 code.o ../../all.o -o a.out $ time ./a.out 56000011 13673971349056 real 0m0.591s

естественно на плюсах будет быстрее, чем на жс )

Alexander

printf(56000011) printf(13673971349056) 😄?

usleep(500ms); cout << 56000011 << endl; cout << 13673971349056 << endl;

Alexander

я все таки си плюс плюс разработчик

Alexander

естественно на плюсах будет быстрее, чем на жс )

ну кстати нифига, js достаточно быстрый, это не питон

Alexander

printf(56000011) printf(13673971349056) 😄?

лучше было бы все таки по другому for (int64_t y = 0; y < 4000000; ++y) { for (int64_t x = 0; x < 4000000; ++x) { if (check_point_is_good(y, x)) { cout << x * 4000000 + y << endl; } }} а вы по другому решали?

Ilia

лучше было бы все таки по другому for (int64_t y = 0; y < 4000000; ++y) { for (int64_t x = 0; x < 4000000; ++x) { if (check_point_is_good(y, x)) { cout << x * 4000000 + y << endl; } }} а вы по другому решали?

один цикл, поиск интервалов пересечений на конкретной строке и мердж интервалов

Alexander

один цикл, поиск интервалов пересечений на конкретной строке и мердж интервалов

Спасибо, но даже плюсы такой перебор не сделают за полсекунды )

Alexander

Это был ответ на шутку про принтф

Dimchik

почти минута, и на этом спасибо 😆

Alex Azarov

интересно кто-нибудь распараллелил на GPU 16^12 проверок?

Alex Azarov

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

Dimchik

8 часов?

Alexander

правильно, а потом еще поднимут размерности и питонисты должны страдать

Alex Azarov

8 часов?

да, для 16трлн точек проверял каждый сканер отдельно ) но я оставлять считаться не стал конечно, просто лень было писать нормальное решение сначала

Dimchik

нормальное это которое за пару секунд считает?)

Dimchik

у меня за минуту почти 😆😆😆

Alexander

у меня за минуту почти 😆😆😆

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

Alexander

то есть перебрал - и отлично

Alexander

Прошлогодние биконы считались у меня минут 20, но уже в один поток

Alexander

То есть между два часа оптимизировать vs час перебирать я выбираю перебирать

Иван

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

Иван

Сегодняшняя интересная но как-то вчерашняя больше понравилась)

Dimchik

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

Ilia

сегодняшнюю тоже можно визуализировать, если масштаб подогнать ))

Captcha bot

Mariia К., если ты не бот, нажми "шесть". Удалено: 534.

Viktor

пранк, который вышел из-под контроля 😂

Dimchik

наконец-то понял как грид в джсе быстро заинициализировать :)

Ilia

наконец-то понял как грид в джсе быстро заинициализировать :)

Вариант посложнее запомнить )) Array.from({length: n+1},_ => Array(m+1).fill(0))

Ilia

ну что, началась жесть. задача простая снаружи, сложная внутри. я чет даже потерялся и не знаю как решать, потому что bfs на 15 итерации уже подыхает в бесконечности

Dzianis

ну что, началась жесть. задача простая снаружи, сложная внутри. я чет даже потерялся и не знаю как решать, потому что bfs на 15 итерации уже подыхает в бесконечности

Там dp :)

Ilia

Там dp :)

да это уже понятно, непонятно как его туда вкорячить ))

Alexandr

я первую часть dfs + memo решил, а на второй части чего-то застрял)

Ilia

я первую часть dfs + memo решил, а на второй части чего-то застрял)

dfs+memo и есть top-down dp :)

Alexandr

ага, мне так проще dp решать)

Dzianis

Это успех! 😄

Dimchik

7,5 минут между первой и второй частью?)

Dzianis

7,5 минут между первой и второй частью?)

Это выполнение всего, и первой и второй

Alex Azarov

дорешал вчерашнюю part 2 брутфорсом кстати

Alex Azarov

проверял все 4_000_000 столбцов для 4_000_000 строк

Alex Azarov

просто добавил оптимизацию что если у ближайшего сканера есть запас по рэнджу больше 10_000 то сразу скипаем на 9_000 по X координате

Alex Azarov

остальные точки по одной проверялись

Alex Azarov

меньше чем за минуту посчитало

Alexander

чат не читаю чтоб не спойлерить

Alexander

но визуализировал инпут сегодняшний

Alexander

если кому надо - обращайтесь :)

Alexander

ну или самостоятельно https://dreampuf.github.io/GraphvizOnline/#digraph%20%7B%22AA%3A0%22%20-%3E%20%22BK%3A0%22%3B%0A%22AA%3A0%22%20-%3E%20%22HY%3A0%22%3B%0A%22AA%3A0%22%20-%3E%20%22LW%3A0%22%3B%0A%7D%0A

Dimchik

the hardest advent of code problem ever, hmmmmm