Тренировки по алгоритмам 3.0. Разбор ДЗ от 13.02

Домашние задания:
- для дивизиона А: contest.yandex.ru/contest/45469
- для дивизиона В: contest.yandex.ru/contest/45468
Подробнее о Тренировках по алгоритмам 3.0: yandex.ru/yaintern/algorithm-...
0:00 - Заставка
6:05 - Начало
6:56 - 1. Гистограмма
10:12 - 2. Красивая строка
22:48 - 3. Коллекционер Диего
30:05 - 4. Контрольная работа
32:30 - 5. Хорошая строка
35:36 - 6. Операционные системы (lite)
50:31 - 7. SNTP
55:17 - 8. Минимальный треугольник
56:26 - 9. Сумма в прямоугольнике
1:03:48 - 10. Скучная лекция

[@pas777777]

6:56 - 1. Гистограмма 10:12 - 2. Красивая строка 22:48 - 3. Коллекционер Диего 30:05 - 4. Контрольная работа 32:30 - 5. Хорошая строка 35:36 - 6. Операционные системы (lite) 50:31 - 7. SNTP 55:17 - 8. Минимальный треугольник 56:26 - 9. Сумма в прямоугольнике 1:03:48 - 10. Скучная лекция

[@it-interview]

Полезная лекция! Точно пригодится на любом собеседовании.

[@geri_freki]

6:06 Начало

[@ARTEMvorkhlik]

Смотрел ради решений лучше чем за квадрат 5 и 6 задач

[@__--_--_--_--__]

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

[@user-hr2ks4dc2f]

Задача 2 (красивая (в бога её душу мать) строка): если в настройках языка в контесте указать python 3.11.2 а не PyPy 7.3.11 то задача выдаёт TL при решении даже по методу двух указателей 😡из-за чего кто-нибудь может к примеру потратить на неё 2 недели!!! и так и не решить и всё это время этот кто-то будет думать шо толи лыжи не едут толи...

[@user-df3xv4uv5c]

со мной так и случилось :((( млин

[@mberdyshev]

Моё решение зашло на cpython по методу двух указателей. Просто я не делал лишний цикл по буквам алфавита, зато использовал доп. память. Я создал словарь-счётчик пройденных букв между указателями. При сдвиге указателя понятно, как изменить счётчик буквы в словаре. А дальше анализируя количество замен, длину между указателями и счётчик буквы, можно понять нужно ли для текущей буквы (левый указатель) пытаться двигать правый указатель. То есть, если промежуток между указателями мы могли бы заполнить текущей буквой с данным количеством замен, то будем пытаться двигать правый указатель дальше, а если это невозможно - то и смысла нет двигать правый указатель. Ну, и, конечно, сохраняем максимум каждый раз.

[@user-co1tk8vw8w]

Это самый полезный коммент за все время, что я их читаю на ютубе. несколько вечеров потратил на эту задачку, а дело было не во мне)

[@snow4dv]

Решил "операционные системы" через сортировку событий) Сортировать надо следующим образом: events.sortWith(compareBy({it.first}, {it.second}, {if (it.second == -1) it.third else (it.third * -1)})) где it.first - сектор события, it.second - тип события ("-1" - начало, "1" - конец, т.е. сначала рассматриваем начало сектора, а потом конец), а it.third - индекс строки, причем если события типа "-1" (то есть начало отрезка секторов ОС), то мы сначала рассматриваем самые ранние установки, а потом - более поздние, а если же сталкиваемся с событиями типа "1" (конец секторов устанавливаемой ОС), то тут уже сначала рассматриваются более поздние установки, а потом - более ранние Таким образом мы добиваемся того, что в отсортированном таким образом списке событий сталкиваясь с некоторым событием мы будем точно знать, был ли этот отрезок перебит другим отрезком секторов (то есть была ли запись поверх) или нет.

[@snow4dv]

з.ы. для незнакомых с компараторами в котлине: эта конструкция описывает сортировку по следующему правилу: 1) сортируем по сектору, если сектора совпадают, то переходим к п. 2 2) сортируем по типу события (сначала "начало" или "-1", потом "конец" или "1"), иначе переходим к п.3 3) если отличается только индекс строки ввода, то: в случае. если это начало отрезка, сортируем по возрастанию, иначе - по убыванию

[@user-nh8fk3lt6o]

Задача 2. Красивая строка, второе решение. для строки ccbbaaaa и k=2, у нас ответ должен быть 6, но получится 4 таким решением, разве не?)

[@TheRunnerSVO]

А первое решение для строки авва и к = 2 дает ответ 3. Или я что-то не понял

[@user-oq7ju6vp7j]

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

[@Odin3411]

4 задачу вообще не понял, видно надо быть участником группы

[@alexandersmirnov4274]

задачу на красоту строки можно решить за один проход по строке и не надо делать это для каждого символа можно посчитать это сразу за один проход зачем вы объясняете решения кот сложные и не эффективные