Это не с литкода.

это айлендс 2? у мну подписки нет ... мну не пускает ;(

Пиздец одни наркомагы в чате

Есть относвязный список, надо определить он конечный или зацикливается

Есть относвязный список, надо определить он конечный или зацикливается

ой давай без классики ... это скучно не нужно меня ловить на понт

это айлендс 2? у мну подписки нет ... мну не пускает ;(

Нет, это реальная задача из ФААНГа. Не уверен, что она уже есть на литкоде.

у мну еще 1.5 литра что то не сильно сложное ;) топливо заканчивается ;)

Ты круче моей жены она 3 литра пьет

это айлендс 2? у мну подписки нет ... мну не пускает ;(

Потом прогоню на внутренних тестах, если хочешь.

Уехал.

ой давай без классики ... это скучно не нужно меня ловить на понт

это два указателя один идет с шагом 1 один с шагом 2.... если они встретяся то цикл

Нет, это реальная задача из ФААНГа. Не уверен, что она уже есть на литкоде.

хоть ограничения дай чтобы понимать о чем речь

как же тяжело не с олимпиадниками ;)

у олипиадников все просто ;) ... ограничения часть задачи ... тут че то брякнул и убежал ;)

ну кароч я вижу задачу тупо на реализацию ... найти острова потом сравнить разные по площади и ограничениям ... вопрос сложности ...

Ну моя краса тоже девушка не маленькая😁😁😁

Ну моя краса тоже девушка не маленькая😁😁😁

избу переодически поджигаете?

Нет, это реальная задача из ФААНГа. Не уверен, что она уже есть на литкоде.

Ну... Я её решал, когда определял форму глаз для сортировки ходов в задачах на жизнь и смерть. Но мне показалась достаточно технической: симметрий всего 16, в чем проблема перебрать их?

Ну... Я её решал, когда определял форму глаз для сортировки ходов в задачах на жизнь и смерть. Но мне показалась достаточно технической: симметрий всего 16, в чем проблема перебрать их?

вот и я вижу тупо перебрать симетрию и сопоставить равные по площади острова ... хз что интересного... мороки много ... удовольствия ноль

можно даже острова как строки захешировать ну чисто поржать ... вопрос в какие ограничения нужно уложиться ... А я потом проверю скучный вариант

избу переодически поджигаете?

Избу не😁😁😁

Избу не😁😁😁

только коней тормозите?

вот и я вижу тупо перебрать симетрию и сопоставить равные по площади острова ... хз что интересного... мороки много ... удовольствия ноль

https://www.codewars.com/kata/56a1c63f3bc6827e13000006 Ну тута, есть банальное н^2 решение, но как не считать заново посчитаное?

только коней тормозите?

Она у меня вообще королева. Отказать ей ну прям анриал😁

https://www.codewars.com/kata/56a1c63f3bc6827e13000006 Ну тута, есть банальное н^2 решение, но как не считать заново посчитаное?

во первых можно выбрать лексически минимальное положение острова ... и хранить только его

во первых можно выбрать лексически минимальное положение острова ... и хранить только его

Какого острова:)? Вы перебухали)

Какого острова:)? Вы перебухали)

я все еще острова решаю что Миша вбросил

я все еще острова решаю что Миша вбросил

Ты ж сказал что это скучно😁😁😁

Ты ж сказал что это скучно😁😁😁

я тоже жене отказать не могу ... мы играем в доминион

Мы под пиво в монополию до утра можем резаться😉

я тоже жене отказать не могу ... мы играем в доминион

Жены они такие😉👍😊

Жены они такие😉👍😊

Happy wife - Happy life!

Найди два ортогональных латинских квадрата 10x10.

По-моему в этой задаче ничего кроме невроза найти нельзя, у мну не выходит :(

слушаю песни про мертвых девочек и прям тянет на добрые дела ;)

что за группа?

Happy wife - Happy life!

Я вот например сижу терплю не сплю потому что у нее терпелка не работает мне подарок вручить😉😁😁😁

что за группа?

Классика кинг даймонд эбигейл ;)

Классика кинг даймонд эбигейл ;)

никогда не слушал из, но вот включил и аж студенчеством пахнуло

По-моему в этой задаче ничего кроме невроза найти нельзя, у мну не выходит :(

Чет я даже просто латинские не могу придумать

Не говоря уж об ортогональных

Чет я даже просто латинские не могу придумать

1 2 3 2 3 1 3 1 2 Не?

1 2 3 2 3 1 3 1 2 Не?

10х10

10х10

Так схема та же

Так схема та же

Да)

Туплю

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 Не?

Чет я даже просто латинские не могу придумать

Ну .. Эйлер считал что его не существует, но ошибался, компьютеры нашли, но ручками построить нереально

Это про ортогональные

как же тяжело не с олимпиадниками ;)

Как же тяжело с теми, кто несёт хуйню и выебывается. В общем, иди нахер.

Существование трёх ортогональных латинских квадрата 10x10 открытый вопрос на сегодня

Как же тяжело с теми, кто несёт хуйню и выебывается. В общем, иди нахер.

я более чем серьезно спросил на каких размерах должен работать алгоритм

Ну... Я её решал, когда определял форму глаз для сортировки ходов в задачах на жизнь и смерть. Но мне показалась достаточно технической: симметрий всего 16, в чем проблема перебрать их?

Сложность обычно во времени, там минут 30-40 на реализацию.

Как же тяжело с теми, кто несёт хуйню и выебывается. В общем, иди нахер.

тесты у вас +- какие?

я более чем серьезно спросил на каких размерах должен работать алгоритм

А нахера тогда последующие сообщения? 1000x1000 грид, этого достаточно.

Сложность обычно во времени, там минут 30-40 на реализацию.

Я люблю подумать, пооптимизировать... 30-40 минут будет явно неоптимизировано

Я люблю подумать, пооптимизировать... 30-40 минут будет явно неоптимизировано

Это обычная задача с собеседования, без какого-то намёка на суперсложность и олимпиадность.

Это обычная задача с собеседования, без какого-то намёка на суперсложность и олимпиадность.

А как фигуры можно сравнивать, шоб понять какие уникальные?

если я мерджу девелоп в свою фиче ветку и кто-то до этого переместил файл, а я в своей фиче ветке изменил название этого файла, то что получается гит мне не покажет возможные конфликты кода внутри этого файла? допустим я изменил что-то в этом файле и кто-то в девелопе тоже и там могут быть конфликты, но гит то не знает что это одинаковый файл, тк в обоих ветках было изменение его названия, либо перемещение. так получается?

Дана карта с островами, найти количество уникальных. Уникальный - одинаковые по форме и размеру. Усложнение - острова можно вертеть. 00101 00101 11000 1 уникальный остров.

острова только поворачивать или зеркальные тоже считаются?

если я мерджу девелоп в свою фиче ветку и кто-то до этого переместил файл, а я в своей фиче ветке изменил название этого файла, то что получается гит мне не покажет возможные конфликты кода внутри этого файла? допустим я изменил что-то в этом файле и кто-то в девелопе тоже и там могут быть конфликты, но гит то не знает что это одинаковый файл, тк в обоих ветках было изменение его названия, либо перемещение. так получается?

Не могу подсказать, но я бы создал бы отдельный репозиторий и там всё это провернул бы

острова только поворачивать или зеркальные тоже считаются?

Только повороты, отражения - разные острова.

Это обычная задача с собеседования, без какого-то намёка на суперсложность и олимпиадность.

Ну понятно это, только мне не сильно нравится... Ибо по-хорошему надо озвучивать требования... Потому что за 30-40 минут надо будет чем-то жертвовать, где-то скоростью, где-то ещё чем-то...

Проще говоря, если я захочу хранить данные в виде битовых масок, то я выиграю по скорости чаще всего, но не уложусь в 30-40 минут.

И это не говоря о том, что я мне повезёт и я уложусь, то его могут и не понять :)

идея не в этом... тут не нужна оптимальность идея проверить на умение в реализацию

написали рекурсией заполнение островов ... сохранили острова по площади и высоте ширине куда то ... сравнили острова с похожими параметрами равно профит ... все шаги максимально простые ... типа на умение в декомпозицию

написали рекурсией заполнение островов ... сохранили острова по площади и высоте ширине куда то ... сравнили острова с похожими параметрами равно профит ... все шаги максимально простые ... типа на умение в декомпозицию

Именно. Ну и по поводу оптимизации: таймлайн и время выполнения задачи - это такой же критерий, как и другие, проверяется умение в трейдофы между «оптимальным» решением и брутфорсом.

написали рекурсией заполнение островов ... сохранили острова по площади и высоте ширине куда то ... сравнили острова с похожими параметрами равно профит ... все шаги максимально простые ... типа на умение в декомпозицию

Ну... Битовые маски выглядят вкуснее, за раз мы растем от всех точек, а если не выросли, значит упёрлись в пределы. Тут цикл

while True: neithebor = (island >> 1) | (island << 1) | (island >> width) | (island << width) growing = neithebor & land island1 = island | growing if island == island1: break island = island1

Заливка острова

Именно. Ну и по поводу оптимизации: таймлайн и время выполнения задачи - это такой же критерий, как и другие, проверяется умение в трейдофы между «оптимальным» решением и брутфорсом.

Решил только чтобы со всей ответственностью заявить 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 цикла можно объединить в общий код ... но опять же ... скучно. ;) и еще куча нюансов которые можно оптимизировать в плане производительности ... но это имхо самое тупое решение в лоб.

Это задача для джун-мидл. Она тупо на реализацию.

Может даже по пьяни где то накосячил ;) но идея такая ;)

да считать island info всегда не оптимально нужно только если уже существует остров с такой же площадью и линейными размерами ... но это бы усложнило код. в данном случае area считается в холостую ;)

Только опыт поможет определить, каким методом можно решать ту или иную задачу?

Только опыт поможет определить, каким методом можно решать ту или иную задачу?

в смысле?

Ну с опытом приходят некоторые "паттерны" или хз как их назвать. Да решение задач это опыт который нужно нарабатывать это имхо не тот случай когда можно нагуглить

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

Я вот например сижу терплю не сплю потому что у нее терпелка не работает мне подарок вручить😉😁😁😁

Вот тебе кстати задача где можно применить битмаски ;) Чтобы не спрашивали нафига они нужны ;)

в моем случае тут правда не сами бит маски но идея island_info именно оттуда. биты ... двоичная система счисления и т.п.

Ну с опытом приходят некоторые "паттерны" или хз как их назвать. Да решение задач это опыт который нужно нарабатывать это имхо не тот случай когда можно нагуглить

Приму к сведению, спасибо

Приму к сведению, спасибо

просто в олимпиадном программировании есть понятие adhoc задачи (задача на реализацию). Это задача не на какие то классические алгоритмы а на идею часто применимую только к этой задаче. В данном случае как мне кажетсч задача про уникальные острова ближе именно к такой задаче .. она тупо про реализацию у нее не стоит искать "второе дно" по крайней мере в таких ограничениях.

изначальная задача может быть решена с помощью dsu в один проход по массиву ... вот интересно можно ли как то посчитать уникальные острова в один проход ;)

Это задача для джун-мидл. Она тупо на реализацию.

1. Алгозадачи нив одной из крупных компании не делят по уровню, что на сеньора, что на джуниора будут одинаковые задачи. 2. Данное решение (даже если считаем, что уложился во время) не было бы оценено максимально, есть edge cases, которые она не проходит. 3. В реальном собеседовании помимо тупо решил/не решил отдельно оценивается production-ready code, тут можно показать свою “сеньорность”.