Chat:Ru/2020-10-03

From CG community
Revision as of 11:29, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/23956705948685> Uljahn: прогресс <img src=/a/4405751597540> BorisZ: на яндекс кап решал задачи кто-нибудь? <img src=/a/440...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Uljahn: прогресс

BorisZ: на яндекс кап решал задачи кто-нибудь?

BorisZ: предварительные, в секции алгоритмы

BorisZ: пятая задачка - топология сети прикольная, похожа на какоую-то из местных, не помню уже какую

BorisZ: там где надо было найти диаметр графа

BorisZ: блин так много задачек что хрен найдешь теперь ее, ни названия не помню, ни деталей, помню только решение

magaiti: расскажи решение ?)

Uljahn: её вроде удалили, Teads sponsored

magaiti: аа, может быть

Uljahn: я решал через удаление крайних вершин, число итераций равно радиусу графа

magaiti: да, я не сразу нашел такое решение

magaiti: какого размера лукап таблица нормально лезет в кэш?

magaiti: 2кб хватит? :)

BorisZ: я ту задачу решал так - брал первую вершину, находил самую далекую от нее вершину, потом уже от этой дальней - опять самую дальнюю

magaiti: это долго

BorisZ: тогда путь между этими дальними и есть диаметр, серединка - центр

magaiti: а, 2 рпаза всего?

BorisZ: почему долго - 2 раза дфс

BorisZ: O(N) сложность

magaiti: не дфс, полный обход дерева

BorisZ: а в яндекс задачке надо как бы два найти центра 0

BorisZ: ну или бфс, путаюсь 9

magaiti: ни то ни другое

magaiti: а хотя дфс, дп

magaiti: да*

magaiti: термин используется при обходе графа, не обязатеьно поиске

BorisZ: обкусывать крайние тоже прикольно но думаю что медленнее - квадратичная сложность получается

magaiti: почему, там о(N)

magaiti: находим листья - о(N)

BorisZ: за один обход этого не сделать ведь

magaiti: надо по листьям ходить

magaiti: а не по графу

BorisZ: не-лист может сать листом а может не стать после того как что-то другое откусили

magaiti: это проверяется

magaiti: за о(1)

magaiti: ты запихиваешь личтья в очередь и работаешь с ней

BorisZ: ну, храним список листов или признак у вершины что она лист, при каждом удалении - обновляем у соседей откусанной

magaiti: нет

BorisZ: по этому списку придется много раз проходить

magaiti: храним ссылки на листы в очереди

magaiti: берем лист из очереди, добавляем все новые листья в очередь

magaiti: а их может быть максимум 1

BorisZ: ну а если после откусывания не образовалось новых листов

magaiti: значит в тот элемент, котрый не лист, заносим длину листа

magaiti: последнего откушенного

magaiti: а при откусывании берем максимум нашегно или того который запомнен в откусываемом

BorisZ: брр, запутался ) ладно фиг с ним, идея то понятная

BorisZ: наверное да O(N), согласен

BorisZ: дак вот, у яндекса в задаче надо найти 2 таких центра

magaiti: а как их может быть 2?

BorisZ: https://contest.yandex.ru/yacup/contest/19811/problems/E/

BorisZ: не уверен что откроется без регистрации ссылка

BorisZ: там по другому сформулировано

TimeIsOut: Ты угадал.

TimeIsOut: Не открылась.

BorisZ: http://chat.codingame.com/pastebin/74554288-d54c-4394-8db8-3fb242488d0c

BorisZ: тоже не работает чет (

BorisZ: https://pastebin.com/jxjFCrba

BorisZ: это предварительный раунд если что, ни на что не влияют результаты, и куча времени дают, чито чтобы освоиться

magaiti: за о(N^3) решается легко, надо бытрее наверное?

magaiti: мне кажется, центры должны на диаметре лежать

magaiti: вроде за о(N) можно

BorisZ: за эн куб стопудово не успеет, к бабке не ходи

BorisZ: центры на диаметре согласен, я почеркался немного на бумажке, всегда так и получается

magaiti: ну я в общих чертах вроде понял как за о(N) делать, ноне детализировал

BorisZ: никому не говори)

BorisZ: у меня тоже есть идея но она сильно некрасивая

wlesavo: тоже решал пробник яндекса, но эту так и не дорешал

BorisZ: а последнюю решил?

BorisZ: я условие только посмотрел - нифига не понял )

BorisZ: в этой с графами как-то можно наверное использовать ограничение что граф минимально связный

BorisZ: что ребер на 1 меньше чем вершин и он связный

magaiti: конечно

BorisZ: опять забыл как называется такая хрень

magaiti: дерево?

BorisZ: был же термин какой-то

BorisZ: угу какое-то там дерево

magaiti: Связный граф без циклов называется деревом

BorisZ: да, но тут в другом суть, из любого связного графа можно построить ххх дерево удаляя ребра

magaiti: между любыми вершинами путь существует и единственный

magaiti: а

magaiti: minimum span tree

BorisZ: точно!

BorisZ: может есть какая-нибудь там еще теоремка про это дерево, фиг знает

magaiti: https://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D0%BD%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE

magaiti: ой

magaiti: вы про псоледнюю задачу? а четама?

magaiti: а в конкурс этот любой может участвовать? нужно регаться где0то?

BorisZ: да, я регался, но сам конкурс еще не начался, это разминка

magaiti: а без реги не дадут размяться?

BorisZ: не знаю, я кидал ссылку, попробуй

BorisZ: https://contest.yandex.ru/yacup/

BorisZ: в последней задаче формулы какие-то, не вставляется нормально в пастебин

magaiti: чет я подозреваю, что последняя задача - на криптографию

magaiti: и там надо биты кранчить, а не по графам ходить

magaiti: хм, а может жадный алгоритм прокатит

735487: хехе 3 в крестиках :) хотя и запушили но достижение

magaiti: я на 11 в гоночках, не представляю что дальше делать, не хватает чего-то

magaiti: в основном набор ходов и фитнесы меняю

735487: а что у тебя в наборе ходов?

magaiti: разное

magaiti: ходы, повороты, щит, буст если не потрачен

magaiti: чем меньше ходов, тем больше шанс выбрать правильный. но правильного может не быть в наборе )

magaiti: повороты на неполный угол пробую

YurkovAS: может еще медленно работает. посравнивай кол-во сим у смится выводится. у меня на 50к меньше, чем у него

magaiti: у меня 100-140

magaiti: там же еще ход надо выбирать в дереве

YurkovAS: это кол-во симуляций? а роллаутов?

magaiti: роллаутов 15000-17000

magaiti: глубина 8 делаю

YurkovAS: у меня выводится тоже, s=симуляций, r=роллаутов у Алексея вроде тоже роллауты выводятся. посравнивай, вдруг большая разница

YurkovAS: ммм, 8 много

magaiti: у него до 19к роллаутов, если это те цифры

magaiti: 8 много? ща посмотрю

YurkovAS: да и у меня так же примерно

YurkovAS: да, ставь 7 + 8 только в пустую или т.п.

YurkovAS: с 8-м пустым лучше против нейронок - иногда выигрывает. а кроме этого разницы не замечал

magaiti: пустой - это без угла и траса?

magaiti: 1 вариант хода типа

YurkovAS: да, без всего

magaiti: хм ща намутим

YurkovAS: т.е. по инерции едет, как до этого было. можно и на весь газ проверить. у меня по инерции

YurkovAS: эх, скоро обгонишь нас

magaiti: я до 11 взлетаю, а потом головой в бетон

magaiti: выше тебя только нейронки же

YurkovAS: ну да, у тех уровень повыше уже

YurkovAS: там и разница в очках соответствующая

magaiti: собрали по 0.01 за 3 года :)

magaiti: а у мэда что за алгоритм? он выводит depth 8

magaiti: меня агитировал дерево пилить

YurkovAS: у него и микеича минимакс

magaiti: ясно

magaiti: а робостак?

magaiti: у него блокер очень злой

YurkovAS: у него смитси и у неймана. у игги не вкурсе что

magaiti: хз, а в плане целевой функции ничего нового не придумали за 2 года?

YurkovAS: оценочную?

magaiti: да

magaiti: я постмортемы читал

YurkovAS: про нее не вкурсе, юзаю как в постмортемах

magaiti: м, ясно

Uljahn: Automaton2000: мясно

Automaton2000: вот как раз в compete

magaiti: Automaton2000: чего мне не хватает в смитси боте?

Automaton2000: ну можно и на плюсах

Uljahn: в оценочной вроде придумали блочить задом, или оно само так получается, когда глубина достаточная

magaiti: само

magaiti: смитси такие ходы выдумывает иногда, удивляешься

magaiti: слабых ботов унижает с особым цинизмом

magaiti: но вот что-то у меня топ-10 не берется никак

magaiti: не пойму, в чем косяк