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: не пойму, в чем косяк
