Ш
Мне рассказали)
Size: a a a
2020 March 26
KK
Угу, верно
KK
Но это не отменяет, что хэши за n * l^2 легче
Ш
Только я пока не знаю как делать одну вещь. Вот у нас получилось строка s1$s2$s3....$sn. Допустим мы хотим узнать ответ для s3. Мы получается пробегаемся по строке s3 и делаем такие запросы lcp(i, j) где j лежит правее сткроки s3 и среди таких берем минимум. Но я не знаю как рассматреть левее строки s3. Где знак $ берется таким образом что он больше не встретится в строке
Ш
Или же я не правильно понял?
Ш
Хотя вроде так же
KK
Только я пока не знаю как делать одну вещь. Вот у нас получилось строка s1$s2$s3....$sn. Допустим мы хотим узнать ответ для s3. Мы получается пробегаемся по строке s3 и делаем такие запросы lcp(i, j) где j лежит правее сткроки s3 и среди таких берем минимум. Но я не знаю как рассматреть левее строки s3. Где знак $ берется таким образом что он больше не встретится в строке
Вставляй не $, а сорть в виде чиселок и вставляй отрицательные чиселки
MB
Хотя человек спросил как решать суффмасом за O(N * L)
Там L log L выходит
KK
Там L log L выходит
nllogl
MB
nllogl
Там N неоткуда взяться.
За L log L строим суфмасс + LCP.
За L считаем ближайший чужой слева/справа
За L считаем ответ
За L log L строим суфмасс + LCP.
За L считаем ближайший чужой слева/справа
За L считаем ответ
MB
Где L - сумма длин всех строк
KK
Не, я про n - количество строк, l - длина одной
KK
Нам необязательно суф мас до конца достраивать
KK
(Да, таки экономлю на спичках)
2020 March 27
n
Господа, подскажите пожалуйста, в какую сторону копать, чтобы решить следующую задачу:
Есть сетка из квадратных ячеек
Есть список объектов разного размера (для простоты возьмём два типа - занимающие 1 ячейку и квадратные на 4 ячейки)
Надо рандомно заполнить все ячейки сетки, чтобы не осталось пустых ячеек и чтобы объекты не пересекались друг с другом
Есть сетка из квадратных ячеек
Есть список объектов разного размера (для простоты возьмём два типа - занимающие 1 ячейку и квадратные на 4 ячейки)
Надо рандомно заполнить все ячейки сетки, чтобы не осталось пустых ячеек и чтобы объекты не пересекались друг с другом
Д🍋
Господа, подскажите пожалуйста, в какую сторону копать, чтобы решить следующую задачу:
Есть сетка из квадратных ячеек
Есть список объектов разного размера (для простоты возьмём два типа - занимающие 1 ячейку и квадратные на 4 ячейки)
Надо рандомно заполнить все ячейки сетки, чтобы не осталось пустых ячеек и чтобы объекты не пересекались друг с другом
Есть сетка из квадратных ячеек
Есть список объектов разного размера (для простоты возьмём два типа - занимающие 1 ячейку и квадратные на 4 ячейки)
Надо рандомно заполнить все ячейки сетки, чтобы не осталось пустых ячеек и чтобы объекты не пересекались друг с другом
а что значит рандомно заполнить?
я как понимаю
у вас есть список объектов (ячеек) которыми нужно насколько это возможно замостить сетку
я как понимаю
у вас есть список объектов (ячеек) которыми нужно насколько это возможно замостить сетку
Д🍋
без пересечения
n
а что значит рандомно заполнить?
я как понимаю
у вас есть список объектов (ячеек) которыми нужно насколько это возможно замостить сетку
я как понимаю
у вас есть список объектов (ячеек) которыми нужно насколько это возможно замостить сетку
рандомно - объекты должны располагаться на случайных местах в сетке, при этом без пересечения.
Т.е. нельзя сначала сортировать по размеру и поставить все большие объекты подряд
Т.е. нельзя сначала сортировать по размеру и поставить все большие объекты подряд
q
Господа, подскажите пожалуйста, в какую сторону копать, чтобы решить следующую задачу:
Есть сетка из квадратных ячеек
Есть список объектов разного размера (для простоты возьмём два типа - занимающие 1 ячейку и квадратные на 4 ячейки)
Надо рандомно заполнить все ячейки сетки, чтобы не осталось пустых ячеек и чтобы объекты не пересекались друг с другом
Есть сетка из квадратных ячеек
Есть список объектов разного размера (для простоты возьмём два типа - занимающие 1 ячейку и квадратные на 4 ячейки)
Надо рандомно заполнить все ячейки сетки, чтобы не осталось пустых ячеек и чтобы объекты не пересекались друг с другом
инициализируй сетку 1-ячеечными и натыкай рандомно 4х-ячеечных
Д🍋
рандомно - объекты должны располагаться на случайных местах в сетке, при этом без пересечения.
Т.е. нельзя сначала сортировать по размеру и поставить все большие объекты подряд
Т.е. нельзя сначала сортировать по размеру и поставить все большие объекты подряд
те следующий объект — рандомный из сета