tutubalin: ещё на предыдущем ходе строится не просто список возможных вариантов, а дерево глубиной 1
tutubalin: когда получаю ответ, сразу из дерева беру тот набор, который соответствует этому ответу
tutubalin: потом в этом списке ищу подходящего кандидата и параллельно строю дерево
tutubalin: йоу! я на 6м месте
Uljahn: малаца
Uljahn: удачный сабмит решает?
tutubalin: блин, в топ10 пока не попал )
tutubalin: в топ11 только )
MadKnight: потому что биты информации не осилил
tutubalin: просто там рандом. надо искать удачный сабмит
MadKnight: сделай просто более умный экстрактор бит информации
tutubalin: в 50 миллисек умнее уже некуда
tutubalin: алгоритм почти оптимальный
MadKnight: ты часть тонн массивов можешь заменить на range()
tutubalin: не могу
tutubalin: во-первых, у меня нет массивов, только вектора
MadKnight: вот потому и не успевает в 50мс лол
tutubalin: во-вторых, в них хранятся комбинации в пожатом битмаповом виде. ренджом никак не заменить
MadKnight: а как фильтруется это всё потом?
MadKnight: при ходе уже
miklla: в этих ваших быках и коровах реверс тестов разве не заруинит соревнование полностью?
miklla: там ведь не рандомные тесты?
vrabosh: рандомные вроде
tutubalin: Uljahn ага, сабмит решает. причём я думал, что это будет казино: нужно будет решать, когда остановиться.
но оказалось, что система использует лучший достигнутый резальтат, поэтому ресабмитить полностью безопасно
MadKnight: интересная система
MadKnight: т.е. теперь лучше иметь бота который с вер-ю 1/10 возьмёт чуть лучше результат, чем у кого-то ещё у кого 90% ?
tutubalin: ну там всё вокруг вероятностей и крутится
tutubalin: те биты, про которые я говорил - они ведь тоже считаются на основе вероятности.
tutubalin: задача именно в том, что максимизировать СРЕДНЕЕ количество информации
tutubalin: в реальности там полный рандом и чисто теоретически можно каждый тест пройти за одну попыткку - просто вероятность этого крайне мала
MadKnight: так в итоге считается твой max() вероятности
tutubalin: там очень много тестов, поэтому откоклонения от среднего не такие большие. так что оптимальный вариант - минимизировать среднее количество попыток, а потом сабмитить до посинения
wlesavo: miklla там хитро-рандомный, секрет строится после первой попытки, чтобы было фиксированное количество быков-коров в тесте, как дбдр подсказал потом можно было бы вообще сделать динамический секрте на основе пула, но это все сильно усложняло бы, и главное не факт что было бы сильно лучше того что есть сейчас
vrabosh: жаль не видно из за чего проигрывает, по таймауту или по другому.
Uljahn: баг бы на тестах проявился, значит - таймаут, скорее всего
miklla: wlesavo найс
tutubalin: по-моему там за любой фейл просто 301 очков насчитывает
tutubalin: у меня чаще всего фейлится на N=8
tutubalin: wlesavo то есть получается, что секрет как-то зависит от первой попытки?
wlesavo: tutubalin вообще да, поэтому я и не публиковал рефери, может там и есть слабое место для реверса какого-нибудь
wlesavo: да, за поражение просто накидывается максимальное число действий
wlesavo: ну даже не для реверса, а просто для улучшения генерации
tutubalin: интересно... то есть дбдр интересовался процессом генерации. и удивительным образом он на первом месте
tutubalin: похоже, нарыл какую-то взаимосвязь
vrabosh: Uljahn там может, что доконца не дошел, это либо надо все варианты у себя проверять, что нереал..
wlesavo: не факт, вообще у него вроде что-то с максимизацией информации получаемой было
tutubalin: я так понимаю, то у всех в топ30 с максимальной информацией
wlesavo: у эйлера было просто случайное число из пула
vrabosh: первое число умеет одинаковую вероятность. хотть 123 хоть рандом
wlesavo: и кови по-моему тоже говорил, но сами сабмиты у них сильно рандомные были
wlesavo: vrabosh первое да, второе нет, например при одном быке в первом 123 124 и 123 145 пул сократят сильно по разному хотя оба случайные числа из пула
wlesavo: хотя мож и вру, 124 не в пуле
wlesavo: ну и числа не из пула тоже могут сильно увеличить получаемую информацию, но это все чисто догадки
vrabosh: как можно iter быстро прогнать впустую, мне допустим надо чтоб он начал работать с млн итерации
vrabosh: 10мс обходится
vrabosh: next(n for i,n in enumerate(tmp) if i>1000000) - я вот так делаю
tutubalin: я заметил, что при N=4 числа, содержащие ноль дают немного меньше информации, потому что ноль не может быть первой цифрой
tutubalin: но при больших N там уже зависимость какая-то неочевидная
tutubalin: возможно как-то связано с циклами в перестановках
vrabosh: кстати да, инфа про ноль думаю 1% прироста может дать)
tutubalin: отсекает 10% вариантов
vrabosh: я первые нули сразу отсикаю. я с масивом работаю, от него отсикаю
vrabosh: теоретически можно на питоне сделать, чтобы в топ вошел, но там замарачиваться надо вычислять формулу.
wlesavo: tutubalin зато при генерации ноль подсовывать может быть выгодно, потому что он не на первом месте будет, но вопрос в том что вероятнее получить при генерации ноль если он есть в первом числе или если его там нет
tutubalin: wlesavo не совсем понял, что значит выгоднее
wlesavo: больше информации получишь, потому что если ноль в числе есть ты знаешь что он не на первом месте и меньше возможных чисел. но это все так, маня рассуждения
Uljahn: типа если 1230 даёт на одного быка больше, чем 1234, то угадали ноль? по-моему, это рулетка какая-то
_vodkaSeeker: Привет всем
_vodkaSeeker: Ребят, вопрос есть
_vodkaSeeker: у всех сайт лагает или только у меня?
_vodkaSeeker: тип чат отваливается всё время и курсор во время кодинга перемещается на ввод сообщения
_vodkaSeeker: или тесты считаются криво
vrabosh: чат лагает, а остальное норм
quasR: У меня бывало такое, что в CoC тесты проверяются капздец как долго, хотя сам код максимально легкий для компилятора, там чисто арифметические действия с целыми числами, даже без циклов
miklla: у меня нет проблем
_vodkaSeeker: блин, ладно
_vodkaSeeker: инет вроде в норме, но зад горит
_vodkaSeeker: то тесты криво проверит и при 100% пройденных после окончания клэша говорит, что меньше 100
_vodkaSeeker: то курсор куда-то кинет, я скоро что-то разобью
tutubalin: ну с тестами всё понятно: есть видимые тесты, на которых проверяешь, когда кодишь
tutubalin: есть невидимые валидаторы, на которых проверяется при сабмите. иногда бывает, что ошибка в алгоритме не заметна на открытых тестах, но проявляется на валидаторах
tutubalin: по поводу прыжков курсора есть две версии: или это из-за автокомплита (он многих бесит здесь)
tutubalin: или из-за тачпада
_vodkaSeeker: прыжки при реконнекте к чату, когда он падает
_vodkaSeeker: на набор сообщения
tutubalin: кстати вот в быках и коровах я бы N=1 вообще убрал - это чистый рандом
wlesavo: tutubalin в валидаторах за него даются фиксированные 5 очков :slight_smile:
tutubalin: if (N==1) cout << "1\n2\n3\n4\n5\n6\n7\n8\n9\n";
wlesavo: вообще просто показалось что так целостнее задача, а в валидаторах оставил изза совета в гайдах чтобы валидаторы примерно соответствовали тестам
MadKnight: tutubalin за те многие разы как ты заливаешь - у тебя наверняка будет сабмитом с результатом в 1
tutubalin: да не, обычно в районе 320 получается
MadKnight: а стоп, это я лол
MadKnight: или нет
MadKnight: так а как в итоге генерится значение-ответ?
MadKnight: говорили что генерится по твоему первому выводу
tutubalin: ага. только я не понял, какая зависимость
MadKnight: так стоп
MadKnight: при n=1 же только 1
MadKnight: а при n=2 - 1..2
MadKnight: 12 либо 21
tutubalin: цифр всё равно 10
tutubalin: N=1: 1, 2, 3, ... 9
tutubalin: N=2: 10, 11, 12, 13, ... 99
MadKnight: так повторяться не могу
MadKnight: т
MadKnight: и говорили, что только 1..n
MadKnight: в любом случае - чё так мало цифр?
MadKnight: фигня же
MadKnight: надо сделать новую мульти
tutubalin: согласен
MadKnight: и назвать её
MadKnight: Bulls and Cows Over9000!
MadKnight: и сделать там n=9001
tutubalin: для N=2: 10, 12, 13, ... 98
MadKnight: и 10мс
MadKnight: ладно, 100мс
MadKnight: 10 рандомить может начать слишком сильно
MadKnight: го 9к символов отгадывать за <9к попыток?*
tutubalin: для over 9000 цифр уже квантовый компутер нужон
alopikon: как ты будешь играть? Кто первый угадает? Или по очереди?
MadKnight: не, там Optimize по числу ходов
MadKnight: tutubalin тыж говорил степень - 1.8
MadKnight: погоди, дай вспомнить матан
MadKnight: значит (10^9000-чтото) бит
MadKnight: значит надо найти log(2, числобит) от этого?
MadKnight: ненене, как вообще нам эти биты переконвертить в объёмы данных?
MadKnight: погоди я сам себя запутал
alopikon: 9000! всего значит лог(9000!) ~= 9000 * 14 бит
MadKnight: хммм 1 бит это по сути 2 реальных бита
MadKnight: потому что 1 реальный бит это по сути ровно 2 бита информации
MadKnight: 2 степень влияния на данные
MadKnight: крч
MadKnight: когда ты далеко от идеала, у тебя нет док-в близости к идеальному решению но у всех топов слишком близкие решения что сложно их сравнивать - значит надо "расширить" для них "поле боя"- а точнее задачи - а точнее пь
MadKnight: потенциал для улучшений
MadKnight: alopikon откуда ты взял 9000! ?
MadKnight: я именно про ...!
tutubalin: я ж ссылку давал на формулу Шеннона
tutubalin: пример 1: бросаем монетку. до броска мы не знаем, как она упадёт. после броска, если упала орлом, мы получили 1 бит, ссли упала решкой, мы получили 1 бит. исходы равновероятны, значит в среднем получаем 1 бит.
tutubalin: пример 2: встретить на улице динозавра. допустим, вероятность этого одна миллиардная.
если вышел на улицу и никакого динозавра нет, получаешь -log2(0.999999999) ~= 1.44e-9 бит.
если видишь динозавра, получаешь -log2(1e-9) ~= 30 бит.
tutubalin: в среднем - примерно 30 миллиардных бит
tutubalin: точнее, 31 миллиардных
MadKnight: пойду запилю пазл на n=999999
MadKnight: назову его Biggs and Bogs 2!
MadKnight: но в каждых 10 цифрах числа не должно быть повторений
MadKnight: если разделить на куски в 10 типа
alopikon: как ты будешь играть? Кто первый угадает? Или по очереди?
