Uljahn: Automaton2000: нагуглить выходит быстрее, чем от тебя помощи дождаться :(
Automaton2000: а то у меня с самого начала
KcalbCube: Привет
amurushkin: таки подловил момент. апнулся на 4 место :)
Uljahn: прошмыгнул промеж таймаутов?
amurushkin: ага )))
Uljahn: малаца, полчата в топе теперь)
amurushkin: давай подтягивайся
amurushkin: вчера сидел сам в нее играл. возникла мысль что иногда можно не сливать в одну ячейку а подождать и оставить так. чтобы привести в порядок хвосты. но как это обьяснить я хз
amurushkin: ему же очень хочется счет увеличить :)
Uljahn: начал пилить 2048, а потом свернул куда-то не туда и залип в пазле Cloudy weather с оптимизацией флудфила в numpy…
amurushkin: :)
wlesavo: тьфу тьфу вроде бимсерч заработал, надо параметры потеребить сегодня вечерм будет
wlesavo: о даже апнулся чуть чуть, и еще секунд двадцать запаса по времени есть, норм
wlesavo: короче выезжаю за вами
amurushkin: где взял 20 секунд запаса? ))
wlesavo: ну все тесты были за 100-200 ходов
amurushkin: главное счет а не ходы ))
amurushkin: ходов и мне хватает еще :)
wlesavo: счет фактически жестко привязан к количеству мувов же. а 200 ходов в том смысле что еще 400 ходов остается, это 20 секунд как раз
amurushkin: там просто чем дальше тем меньше зависимость счета от количества мувов. начинает стримиться к пределу. и все решает соберется 131к или нет
amurushkin: если собирается то счет будет 2,6-3,3, если не соберется то 1,7
wlesavo: не ну это понятно, .но собраный 131к и не собраный это тоже привязано к количеству мувов
amurushkin: просто ты не дошел до стадии когда результат всегда одинаковый примерно :)
amurushkin: вот сколько у тебя сейчас ходов всего на игру? сколько будет если ты весь запас используешь времени?
wlesavo: да у меня решение не масштабируется, дохожу где-то до 30к часто, но с изменением параметров и использованием большего времени только хуже становится, у меня есть идеи что делать, просто ща на работе
Uljahn: свежачок про плюсы и кэши
https://habr.com/ru/company/yandex/blog/522900/
amurushkin: а так мы как раз это видео недавно упоминали
amurushkin: но почитаю все равно
wlesavo: опа, 44М
amurushkin: сколько мс на ход ставишь? часто таймит?
wlesavo: 45, вообще не таймит
wlesavo: но у меня оставшиеся 5 мс ничего кроме cout не происходит
wlesavo: сабмитнул с 49мс на ход, тоже 0 таймаутов
amurushkin: а сортировать когда успеваешь?
wlesavo: а у меня pq
amurushkin: хоть кто то воспользовался идеей ))
wlesavo: ну я не ищу до упора, делаю как и раньше делал, дохожу до глубины какой-то и добавляю часть в решение, применяю все изменения и заново ищу
wlesavo: то есть после выхода из лупы уже почти ничего не происходит
wlesavo: ща еще дубликаты надо убрать, может даст немного прироста
wlesavo: не собирается таки 131, глубины не хватает похоже
wlesavo: http://chat.codingame.com/pastebin/42ac6e06-667f-4c5a-a918-827732e8ecb9
wlesavo: о без дубликатов собрался 131к
wlesavo: ща глянем на сабмит
wlesavo: о, изи 50r
magaiti: 55 изи, дальше надо как-то придумывать, как заставить бим найти 131 во всех тестах где это возможно
magaiti: у меня в 3-х находит сам, в одном я заставил через отзеркаливание доски
magaiti: а в остальных 10-и не хочет
magaiti: даже когда я на ширину луча 1024 выхожу ближе к делу
magaiti: во всех вариантах отзеркаливания и поворотов доски
magaiti: нужно что-то другое
wlesavo: по логике нужна хорошая глубина очень
magaiti: я первый ход делаю буфер вывода, а потом из него отдаю, а сам иду по лучу пока не кончатся решения. но так даже хуже получается, чем отступать каждый ход
magaiti: я думаю брутфорс сделать в оффлайне, потестить есть ли решения в принципе
magaiti: но кто-то же смог 62 набрать
magaiti: он явно просек как
wlesavo: я думаю можжно взять н фиксированных метрик, и в офлайне найти на какой тест какая дает 131к, для тех тестов где это возможно разумеется, и дальше от сида фиксировать метрику
magaiti: да, но надо еще найти такую метрику чтоб давала 131
wlesavo: ну это перебором по захардкоженным метрикам можно попробовать
magaiti: я вот перепробовал по 8 на каждый тест уже, не подошли
wlesavo: а ты выяснял уже тесты в которых возможно набрать?
magaiti: это просто
magaiti: считаешь сумму чисел - по 2 и 4
magaiti: если набирается ровно 131 072, знасчит в последней клетке выпадает двойка
wlesavo: ну я понимаю что просто, мне пока лень, но интересно сколько таких тестов
magaiti: 14
magaiti: из ни в 4-х можно набрать 3.3
magaiti: то есть там можно собрать 131 и 65
magaiti: нужно чтоб еще раз 4-ка выпала
wlesavo: норм, спс
magaiti: но это теория, возможно там нет решений, то есть выпадают числа так что никак на 15 клеток правильных не выйти, даже если 4-ка в 16-й выпадает
magaiti: я думал как-то в обратном направлении подвигаться
wlesavo: не ну понятно, зато в остальных гарантировано нельзя
wlesavo: да, зареверсить интересно бы было
magaiti: прикинул как решать кстати
magaiti: но не кодл
magaiti: и*
magaiti: делаем сортированный массив по сумме очков на доске
magaiti: индекс - ход
wlesavo: ну да, учитывая что все сиды знаешь, знаешь конечное состояние доски
magaiti: и сиды там храним
magaiti: потом сид и сумму на предыдущий ход можно по таблице найти быстро
magaiti: а там придется все двойки и четверки тестить
wlesavo: ну да, это как раз понятно
magaiti: по сиду можно понять, в какую клетку должна попасть
magaiti: возможно будет 2 варианта
magaiti: а потом все варианты ходов и слияний клеток
magaiti: по пустым клеткам легко понять какие ходы могли быть
wlesavo: фактор ветвления конечно приличный будет, в идеале какаято реверсима нужна
magaiti: не, небольшой я думаю
magaiti: от глубины зависит
magaiti: подозреваю что если играть через 3 хода, то вариантов может не быть вообще
magaiti: в некоторых случаях
magaiti: я поэтому и замутил повороты и отражения доски, но помогло только в 1-м лучае
wlesavo: о, на одном тесте собралось 131+65
magaiti: в большинстве случаев ходы кончаются где-то на счете 1.6, хмм
wlesavo: лол, 70к мувов перевалило, а у меня пул для мувов 70к и таймаут
magaiti: 80 ставь
wlesavo: да, уже поставил
magaiti: у меня 76 с чем-то было
wlesavo: когда дедлал не думал что дойду до таких чисел, с хорошим запасом выставил
wlesavo: ну я не думал что до такого дойду, ставил типа с хорошим запасом еще оценивал что теоретический максимум где-то рядом с этим
wlesavo: да, 76344 вроде
magaiti: так чего ж ты взял меньше теормаксимума, а не больше
wlesavo: я не досчитал до теормаксимума, думал он меньше
wlesavo: во, почти 55. надо наверное и правда поиграться с метриками в оффлайне
amurushkin: меня чето совсем cg не взлюбил. 2 день капчи на каждый сабмит требует да еще и с рисунками
wlesavo: у меня норм все
magaiti: мне на слово верит, что я не бот
wlesavo: убирание дубликатов прямо неплохой буст дало
magaiti: конечно
magaiti: они же плодятся
magaiti: дают одинаковых потомков
wlesavo: я чето не думал что их много будет
wlesavo: но вообще да
magaiti: пробовал 2 варианта - хранить в куче, и каждый ход (50мс) убирать дубликаты
magaiti: или хранить в куче и в хеш-сете
magaiti: хеш-сет медленный, хотя при большой ширине луча сортировка начинает тормозить уже
wlesavo: я убираю дубликаты когда из pq добавляю в следующие поколение, это одна проверка считай, потому что отсортированы результыта, если равно предыдущему взятому то дубликат
magaiti: ну это то же самое
wlesavo: если скор равен всмысле
magaiti: просто ты сортируешь доставая из кучи по одному
wlesavo: ну да
magaiti: а я беру тело кучи и сортирую квиксортоом
magaiti: и потом следующее поколение
magaiti: скорость примерно одна должна быть
magaiti: сортировка кучей кстати более стабильная
magaiti: строго o(n log n)
magaiti: квик может на квадрат выйти, при плохих данных
amurushkin: а по дефолту плюсовый sort как сортирует? там у него зависит от количества данных вид сортировки?
magaiti: вроде квиксорт сначала, если видит что не сходится за нормальное время, переходит на другой алгоритм, не помню какой
magaiti: у которого константа больше, но гарантированно n log n
magaiti: может быть маленькие пулы сортирует отдельным алгоритмом
magaiti: insertion sort вроде
magaiti: сумма по змейке с дискаунтом кстати не уникальна для всех досок
magaiti: если с float перейти на double то практически уникальна
magaiti: зависит от дискаунта еще
magaiti: надо какой-нить иррациональный выбрать
amurushkin: да я тоже заметил. поэтому у меня одинаковость не через оченку проверяется
Uljahn: а зачем сортировать? топ-N можно наверное отбирать через std::nth_element, не?
magaiti: можно
magaiti: я сортирую чтоб дубликаты убрать
magaiti: пытаюсь в оффлайне брутить, но ожидал что так много позиций будет
magaiti: уже 80 млн позиций на каком-то там ходу, 20 или 30
magaiti: при том что всего 3 хода
magaiti: большинство плохие, без змейки
magaiti: но я пытаюсь оценить полное решение
magaiti: я думал там кол-во ходов должно стабилизироваться к какому-то ходу
magaiti: кол-во позиций на конкретном ходу
BorisZ: я тут подумал что можно же всю борду запихать в 128 бит long long
magaiti: можно
BorisZ: на 1 ячейку нужно 5 бит
BorisZ: от 0 до 17
BorisZ: хранить - только степени
BorisZ: а если хранить не слева направо таблицей а сразу змейкой то оно еще и сортироваться будет само
magaiti: 10 байт
BorisZ: 10 байт на что?
wlesavo: magaiti так надо тогда уж запускать брут с собранными двумя рядами от 65к
magaiti: ну тогда надо все варианты позиций считать
magaiti: я пока не дошел до этого
magaiti: хотя
magaiti: ну, можно просто посмотреть сколько это займет
magaiti: да, 130 миллионов позиций съели мою память. можно сжать доску до 14 байт конечно
magaiti: но лучше попробую с какой-ниь позиции где 1-2 ряда уже есть
magaiti: ого, набрутил быстро
wlesavo: до конца набрутил?
magaiti: взял одну позицию где было 2 строчки заполнено, со счетом поменьше
magaiti: набрутил за пару секунд
magaiti: решений нет
wlesavo: а
magaiti: но по идее в процессе я сделал хеш-таблицы проигрышнух позиций
magaiti: 8 клеток можно в uint64_t хранить
magaiti: то есть брут следующей позиции может уже их использовать
magaiti: но хз насчет процента совпадений
magaiti: и их как-то сливать придется
magaiti: для 3-го поиска итд
magaiti: самый широкиу у меня был ход где-то 26к позиций
magaiti: если начинать с 8 заполненными
magaiti: надо запилить обратную симу, гнать ее секунд 10, а потом пытаться состыковать с прямой
magaiti: разных столбцов примерно 100к, можно сделать таблицу возможных слияний
amurushkin: Uljahn: ты вроде плюсы не юзаешь а про nth_element знаешь :) я и не знал о таком. попробую сейчас заменить им сортировку перед выводом. может таймить перестанет
magaiti: да он не сильно быстрее
amurushkin: ага таймит все равно :)
amurushkin: надо на PQ попробовать переписать
Uljahn: amurushkin: это я когда numpy курил, наткнулся на такое
magaiti: чтоб делать быстрый код на питоне, нужно знать с++?
magaiti: или оно в нумпае есть
Uljahn: есть похожее
Uljahn: посидишь на CG несколько лет в чатах - много всего узнаешь, Automaton2000
Automaton2000: так я же не буду
magaiti: лол
magaiti: ты лалка, Automaton2000
Automaton2000: madknight, а ты что думаешь?
MadKnight: magaiti прав, Automaton2000
Automaton2000: вот о чем и речь
magaiti: научился стрелки переводить
KcalbCube: Привет
