Igor
Это не с литкода.
это айлендс 2? у мну подписки нет ... мну не пускает ;(
Andrii
Пиздец одни наркомагы в чате
Есть относвязный список, надо определить он конечный или зацикливается
Igor
Есть относвязный список, надо определить он конечный или зацикливается
ой давай без классики ... это скучно не нужно меня ловить на понт
Mikhail
это айлендс 2? у мну подписки нет ... мну не пускает ;(
Нет, это реальная задача из ФААНГа. Не уверен, что она уже есть на литкоде.
Mikhail
это айлендс 2? у мну подписки нет ... мну не пускает ;(
Потом прогоню на внутренних тестах, если хочешь.
Mikhail
Уехал.
Igor
ой давай без классики ... это скучно не нужно меня ловить на понт
это два указателя один идет с шагом 1 один с шагом 2.... если они встретяся то цикл
Igor
как же тяжело не с олимпиадниками ;)
Igor
у олипиадников все просто ;) ... ограничения часть задачи ... тут че то брякнул и убежал ;)
Igor
ну кароч я вижу задачу тупо на реализацию ... найти острова потом сравнить разные по площади и ограничениям ... вопрос сложности ...
Алексей
Ну моя краса тоже девушка не маленькая😁😁😁
Igor
Ну моя краса тоже девушка не маленькая😁😁😁
избу переодически поджигаете?
Andrii
Нет, это реальная задача из ФААНГа. Не уверен, что она уже есть на литкоде.
Ну... Я её решал, когда определял форму глаз для сортировки ходов в задачах на жизнь и смерть. Но мне показалась достаточно технической: симметрий всего 16, в чем проблема перебрать их?
Igor
Ну... Я её решал, когда определял форму глаз для сортировки ходов в задачах на жизнь и смерть. Но мне показалась достаточно технической: симметрий всего 16, в чем проблема перебрать их?
вот и я вижу тупо перебрать симетрию и сопоставить равные по площади острова ... хз что интересного... мороки много ... удовольствия ноль
Igor
можно даже острова как строки захешировать ну чисто поржать ... вопрос в какие ограничения нужно уложиться ... А я потом проверю скучный вариант
Igor
Избу не😁😁😁
только коней тормозите?
Виталик Голоенко
вот и я вижу тупо перебрать симетрию и сопоставить равные по площади острова ... хз что интересного... мороки много ... удовольствия ноль
https://www.codewars.com/kata/56a1c63f3bc6827e13000006 Ну тута, есть банальное н^2 решение, но как не считать заново посчитаное?
Алексей
только коней тормозите?
Она у меня вообще королева. Отказать ей ну прям анриал😁
Igor
https://www.codewars.com/kata/56a1c63f3bc6827e13000006 Ну тута, есть банальное н^2 решение, но как не считать заново посчитаное?
во первых можно выбрать лексически минимальное положение острова ... и хранить только его
Igor
Какого острова:)? Вы перебухали)
я все еще острова решаю что Миша вбросил
Алексей
я все еще острова решаю что Миша вбросил
Ты ж сказал что это скучно😁😁😁
Igor
Ты ж сказал что это скучно😁😁😁
я тоже жене отказать не могу ... мы играем в доминион
Алексей
Мы под пиво в монополию до утра можем резаться😉
Igor
Erik
Найди два ортогональных латинских квадрата 10x10.
По-моему в этой задаче ничего кроме невроза найти нельзя, у мну не выходит :(
Алексей
Happy wife - Happy life!
Я вот например сижу терплю не сплю потому что у нее терпелка не работает мне подарок вручить😉😁😁😁
Igor
что за группа?
Классика кинг даймонд эбигейл ;)
Шаман Каган
Классика кинг даймонд эбигейл ;)
никогда не слушал из, но вот включил и аж студенчеством пахнуло
Erik
Не говоря уж об ортогональных
Алексей
10х10
Так схема та же
Erik
Туплю
Виталик Голоенко
1 2 3 4 5 6 7 8 9 10 2 3 4 5 6 7 8 9 10 1 3 4 5 6 7 8 9 10 1 2 4 5 6 7 8 9 10 1 2 3 5 6 7 8 9 10 1 2 3 4 6 7 8 9 10 1 2 3 4 5 7 8 9 10 1 2 3 4 5 6 8 9 10 1 2 3 4 5 6 7 9 10 1 2 3 4 5 6 7 8 10 1 2 3 4 5 6 7 8 9 Не?
Andrii
Чет я даже просто латинские не могу придумать
Ну .. Эйлер считал что его не существует, но ошибался, компьютеры нашли, но ручками построить нереально
Andrii
Это про ортогональные
Mikhail
как же тяжело не с олимпиадниками ;)
Как же тяжело с теми, кто несёт хуйню и выебывается. В общем, иди нахер.
Andrii
Существование трёх ортогональных латинских квадрата 10x10 открытый вопрос на сегодня
Igor
Как же тяжело с теми, кто несёт хуйню и выебывается. В общем, иди нахер.
я более чем серьезно спросил на каких размерах должен работать алгоритм
Mikhail
я более чем серьезно спросил на каких размерах должен работать алгоритм
А нахера тогда последующие сообщения? 1000x1000 грид, этого достаточно.
Andrii
Сложность обычно во времени, там минут 30-40 на реализацию.
Я люблю подумать, пооптимизировать... 30-40 минут будет явно неоптимизировано
Mikhail
Я люблю подумать, пооптимизировать... 30-40 минут будет явно неоптимизировано
Это обычная задача с собеседования, без какого-то намёка на суперсложность и олимпиадность.
Виталик Голоенко
MarkosTh09
если я мерджу девелоп в свою фиче ветку и кто-то до этого переместил файл, а я в своей фиче ветке изменил название этого файла, то что получается гит мне не покажет возможные конфликты кода внутри этого файла? допустим я изменил что-то в этом файле и кто-то в девелопе тоже и там могут быть конфликты, но гит то не знает что это одинаковый файл, тк в обоих ветках было изменение его названия, либо перемещение. так получается?
Mikhail
острова только поворачивать или зеркальные тоже считаются?
Только повороты, отражения - разные острова.
Andrii
Это обычная задача с собеседования, без какого-то намёка на суперсложность и олимпиадность.
Ну понятно это, только мне не сильно нравится... Ибо по-хорошему надо озвучивать требования... Потому что за 30-40 минут надо будет чем-то жертвовать, где-то скоростью, где-то ещё чем-то...
Andrii
Проще говоря, если я захочу хранить данные в виде битовых масок, то я выиграю по скорости чаще всего, но не уложусь в 30-40 минут.
Andrii
И это не говоря о том, что я мне повезёт и я уложусь, то его могут и не понять :)
Igor
идея не в этом... тут не нужна оптимальность идея проверить на умение в реализацию
Igor
написали рекурсией заполнение островов ... сохранили острова по площади и высоте ширине куда то ... сравнили острова с похожими параметрами равно профит ... все шаги максимально простые ... типа на умение в декомпозицию
Mikhail
написали рекурсией заполнение островов ... сохранили острова по площади и высоте ширине куда то ... сравнили острова с похожими параметрами равно профит ... все шаги максимально простые ... типа на умение в декомпозицию
Именно. Ну и по поводу оптимизации: таймлайн и время выполнения задачи - это такой же критерий, как и другие, проверяется умение в трейдофы между «оптимальным» решением и брутфорсом.
Andrii
while True: neithebor = (island >> 1) | (island << 1) | (island >> width) | (island << width) growing = neithebor & land island1 = island | growing if island == island1: break island = island1
Andrii
Заливка острова
Igor
Именно. Ну и по поводу оптимизации: таймлайн и время выполнения задачи - это такой же критерий, как и другие, проверяется умение в трейдофы между «оптимальным» решением и брутфорсом.
Решил только чтобы со всей ответственностью заявить boring ;) def num_islands(grid): islands = set() h = len(grid) w = len(grid[0]) minx, maxx, miny, maxy, area = 0, 0, 0, 0, 0 def island_info(): maxval = (0,0,0) val = 0 for y in range(miny, maxy + 1): for x in range(minx, maxx + 1): if grid[y][x] == -cnt: val |= 1 val <<= 1 maxval = max(maxval, (val, maxy-miny, maxx-minx)) val = 0 for x in range(maxx, minx - 1, -1): for y in range(miny, maxy + 1): if grid[y][x] == -cnt: val |= 1 val <<= 1 maxval = max(maxval, (val, maxx - minx, maxy - miny)) val = 0 for y in range(maxy, miny - 1, -1): for x in range(maxx, minx -1, -1): if grid[y][x] == -cnt: val |= 1 val <<= 1 maxval = max(maxval, (val, maxy - miny, maxx - minx)) val = 0 for x in range(minx, maxx + 1): for y in range(maxy, miny - 1, -1): if grid[y][x] == -cnt: val |= 1 val <<= 1 maxval = max(maxval, (val, maxx - minx, maxy - miny)) return maxval def fill(y, x): nonlocal minx, maxx, miny, maxy, area if 0 <= y < h and 0 <= x < w and grid[y][x]>0: minx = min(minx, x) miny = min(miny, y) maxx = max(maxx, x) maxy = max(maxy, y) area += 1 grid[y][x] = -cnt fill(y + 1, x) fill(y - 1, x) fill(y, x + 1) fill(y, x - 1) cnt = 1 h = len(grid) for y in range(h): for x in range(w): if grid[y][x]>0: minx = maxx = x miny = maxy = y area = 0 fill(y, x) islands.add(island_info()) cnt += 1 return len(islands) и да с точки зрения оптимальности такая рекурсия хуже чем если перед уходом в рекурсию делать проверки, но заломало писать проверки и island_info по идее все 4 цикла можно объединить в общий код ... но опять же ... скучно. ;) и еще куча нюансов которые можно оптимизировать в плане производительности ... но это имхо самое тупое решение в лоб.
Igor
Это задача для джун-мидл. Она тупо на реализацию.
Igor
Может даже по пьяни где то накосячил ;) но идея такая ;)
Igor
да считать island info всегда не оптимально нужно только если уже существует остров с такой же площадью и линейными размерами ... но это бы усложнило код. в данном случае area считается в холостую ;)
Arutemu
Только опыт поможет определить, каким методом можно решать ту или иную задачу?
Igor
Ну с опытом приходят некоторые "паттерны" или хз как их назвать. Да решение задач это опыт который нужно нарабатывать это имхо не тот случай когда можно нагуглить
Igor
но опять же если у нас известна целевая сложность это часто ограничивает набор алгоритмов которые ты можешь применять ... поэтому в том же олимпиадном программировании часто ограничения задачи дают подсказку что стоит пробовать, а о чем не стоит даже думать.
Igor
Я вот например сижу терплю не сплю потому что у нее терпелка не работает мне подарок вручить😉😁😁😁
Вот тебе кстати задача где можно применить битмаски ;) Чтобы не спрашивали нафига они нужны ;)
Igor
в моем случае тут правда не сами бит маски но идея island_info именно оттуда. биты ... двоичная система счисления и т.п.
Igor
Приму к сведению, спасибо
просто в олимпиадном программировании есть понятие adhoc задачи (задача на реализацию). Это задача не на какие то классические алгоритмы а на идею часто применимую только к этой задаче. В данном случае как мне кажетсч задача про уникальные острова ближе именно к такой задаче .. она тупо про реализацию у нее не стоит искать "второе дно" по крайней мере в таких ограничениях.
Igor
изначальная задача может быть решена с помощью dsu в один проход по массиву ... вот интересно можно ли как то посчитать уникальные острова в один проход ;)
Mikhail
Это задача для джун-мидл. Она тупо на реализацию.
1. Алгозадачи нив одной из крупных компании не делят по уровню, что на сеньора, что на джуниора будут одинаковые задачи. 2. Данное решение (даже если считаем, что уложился во время) не было бы оценено максимально, есть edge cases, которые она не проходит. 3. В реальном собеседовании помимо тупо решил/не решил отдельно оценивается production-ready code, тут можно показать свою “сеньорность”.