Viktor
а размер максимальный там 100x100
Viktor
т.е. просто перебрать все ячейки не выйдет
Philipp
Типа счет индексов с нуля начинается?
Viktor
ага
Philipp
Philipp
Чет интернет сегодня тупит жестко. Сообщения грузятся по две минуты
Viktor
Не. Я про другое
ну пишут на всякий случай ещё чтобы ты не пытался расковырять сам объект и пытаться как-то на реализации спекулировать.
Philipp
Я про это
Viktor
в этих --ваших-- наших джаваскриптах на раз два ж инкапсуляцию нарушить, при желании
Philipp
Viktor
что это по факту значит — хз
Viktor
удалят аккаунт 😂
Philipp
в этих --ваших-- наших джаваскриптах на раз два ж инкапсуляцию нарушить, при желании
Это не мой уровень) я могу только свой код сломать чтоб он не работал)
V
сегодняшняя задача напомнила мне задачу про луч из advent of code
Viktor
сегодняшняя задача напомнила мне задачу про луч из advent of code
ты его кстати прошёл до конца?
Viktor
задачки крутые. я первые дня два-три проходил, но потом забил.
Viktor
мне нравится, что они все связаны.
V
не, осталось пять дней, которые я так и не дорешал...
Viktor
5 из 30? это круто
Viktor
я видел какой-то типсон упоролся и решал всё в экселе
Viktor
другой типсон прорешал на всех языках, что знает, а-ля там штук 10
Viktor
я чувствую себя дном когда смотрю на это 😂
Порридж В Ко-ливинге
Also, any solutions that attempt to circumvent the judge will result in disqualification.
Порридж В Ко-ливинге
V
я читал реддит параллельно с решениями. на первых днях было много экхотических решений на экселе и майнкрафте, но потом сложность стала увеличиваться, и такие решеия стали пропадать )
Viktor
https://adventofcode.com/
Viktor
Viktor
вот я считаю охеренный язык
Viktor
https://github.com/betaveros/advent-of-code-golf-2019/blob/master/day1-2.prdc
Viktor
понятный код
Viktor
Иван
А как вам
Иван
это?)
Иван
https://ru.wikipedia.org/wiki/Shakespeare_(%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F)
Viktor
👍
Viktor
о как. сегодняшняя задача чуваку на онсайте в Facebook попалась.
Viktor
вспомнил че за задачка была на фб последняя на онсайте. есть матрица NxM. надо найти самую левую единичку. по условию строки в матрицах состоят из последовательности 0 и 1, причем последовательность не может быть типо такой 01010, а все нули слева если они есть и все единицы справа если они есть
Viktor
типо
000001
000111
Viktor
и тд
Viktor
прямо крутая подборка на LeetCode
V
уф, пришлось подебажить, в каком порядке binaryMatrix возвращает значение. сначала я думал, что (width, height), но оказалсь (height, width)
Viktor
блин, вот и я! они написали там (x, y), только я не понял, что x – это строка.
Viktor
вообще странно они сделали.
Viktor
типа y же строка, потому что вертикаль, а x — столбец, потому что горизонталь
Viktor
но нет 😄
V
да, я тоже так думал
Viktor
Errichto по-людски объяснил линейное решение для задачи с деревом — https://youtu.be/RyAGEb4VWo0?t=962
Иван
Кстати добавление в set элемента за nlogn делается?
Иван
Или за logn?
Viktor
За logN, по идее — вставка одного элемента в дерево ж.
Иван
Ну да, спасибо
Viktor
ну можно за O(n) создать из отсортированного массива
Viktor
т.е. каждая вставка амортизированно будет O(1)
Viktor
но не в общем случае
Evgeniy
По поводу сегодняшней задачи (но ещё не пробовал реализовать): использовать бинарный поиск по столбцам и линейный по строкам
Viktor
Да, это нормальная тема. Единственное там lower_bound нужно реализовать
Viktor
Не просто поиск
Evgeniy
Для максимального размера 100 на 100 мы не превысим 1000 вызовов
V
самое простое решение — О(n+m)
Evgeniy
Да, это нормальная тема. Единственное там lower_bound нужно реализовать
а проверять до конца просто, до упора
Viktor
самое простое решение — О(n+m)
Гениально просто я бы сказал. Но надо понять ещё почему это правда.
Evgeniy
проход по вершинам единиц что ли?
Evgeniy
как-то так
Evgeniy
А, ну да. Идем справа налево, пока до нуля не дойдем. Потом вниз, ищем снова единицу. Если нашли, опять идём левее до нуля.
Viktor
Всё так. Только почему это работает.
Evgeniy
И так найдем максимальное отдаление
Evgeniy
Таким проходом мы найдем самое большее количество единиц. Что нам как раз и нужно
Viktor
Я для себя объяснил так.
Допустим мы нашли крайнюю единицу в ряду. Далее мы двигаемся на следующий ряд и у нас есть выбор: если там ноль, то единица где-то справа и нет смысла её искать, т.к. она всё равно будет дальше чем та единица откуда мы пришли, соответственно идём на следующий ряд, а вот если там единица, то имеет смысл прогуляться налево и посмотреть самую крайнюю единицу уже в этом ряду, и так пока не дойдём до последнего ряда или первого столбца (меньше нуля ответа точно не может быть, значит нет смысла перебирать до последнего ряда).
Viktor
Если насыпать туда всяких индукционных переходов, то может даже получится нормальное доказательство корректности 😂
Evgeniy
Решение просто похоже на поиск максимума из последовательности чисел
Evgeniy
Только на новый максимум мы не резко скачем, а вальяжно гуляем по одному шагу)