Chat:Ru/2020-10-15

From CG community
Revision as of 11:29, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/23956705948685> Uljahn: Automaton2000: нагуглить выходит быстрее, чем от тебя помощи дождаться :( <img src=/a/40502...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Uljahn: Automaton2000: нагуглить выходит быстрее, чем от тебя помощи дождаться :(

Automaton2000: а то у меня с самого начала

Default avatar.png 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: научился стрелки переводить