Будем идти по строке слева направо. Если мы прошли всю строку, либо в руках у нас уже 5 предметов, либо очередной предмет отличается от тех, что мы держим в руках, то относим все предметы в кладовку. Ответом на задачу будет количество посещений кладовки.
Сложность решения O(n).
Посчитаем количество чисел от 1 до n, которые встречаются в последовательности хотя бы один раз. Тогда ответ есть n минус это количество.
Сложность решения в зависимости от реализации O(n) или O(n logn).
Отсортируем пары, заданные в условии по году начала события. Будем идти по массиву этих пар и поддерживать значение rg - самый поздний год окончания какого-либо из уже обработанных событий. Тогда если для текущего года окончания события - year, верно что year < rg, то нужно прибавить к ответу единицу, поскольку данное событие покрыто каким-то из ранее обработанных (поскольку все обработанные события имеют левую границу меньше нашей и какое-то из них имеет правую границу rg большую year). После этого пересчитываем rg следующим образом: rg = max(rg, year).
Сложность решения: O(n logn) - на сортировку и O(n) - на решение.
Сначала сделаем небольшой предподсчёт: cnt[lf][rg] - наименьшее количество символов, которое мы должны изменить, чтобы подстрока [lf, rg] стала палиндромом. Это легко сделать за O(n^3) времени и O(n^2) памяти. Теперь будем считать динамику z[i][j] - наименьшее число изменений, которое мы должны сделать, чтобы разбить префикс длины i на ровно j палиндромов. Сначала весь массив заполним бесконечностями, а z[0][0] присвоим 0. Теперь будем делать переходы вперёд: переберём длину len очередного (j-го) палиндрома и сделаем обновление состояния z[i + len][j + 1] значением z[i][j] + cnt[i][i + len - 1]. Ответ есть минимум z[n][i], где n - длина строки из входного файла, а i отрезка [1, k]. Чтобы вывести ответ необходимо в дополнительном массиве сохранить предка для каждого состояния.
Сложность решения: O(n^3) по времени и O(n^2) по памяти.
В этой задаче можно было подумать, что при фиксированном начале строки функция "хорошести" от конца строки монотонная, но это не так (хотя бы на примере строки baaab). Заменим все гласные из строки на число -1, а все согласные на число 2. Теперь легко понять, что подстрока [i, j] будет хорошей, если сумма в подотрезке [i, j] неотрицательна. Обозначим эту сумму sum[i][j]. Очевидно sum[i][j] = p[j + 1] - p[i]. Где p[i] - сумма первых i элементов. Теперь решение становится достаточно понятным. Одним из решений было следующее: отсортируем все частичные суммы вместе с индексом частичной суммы и заведём структуру данных над массивом индесов частичных сумм, позволяющую извлекать максимум на суффиксе, а также изменять значение в точке (в качестве такой структуры подойдёт дерево отрезков). Теперь будем пробегаться по массиву частичных сумм (отсортированных) и для текущего индекса частичной суммы (начала хорошей строки) найдём самую правую частичную сумму больше либо равную нашей. Пусть величина текущей частичной суммы равна s, а её номер - i. Найдём в массиве частичных сумм первую частичную сумму с величиной больше либо равной s. Найдём максимум на суффиксе найденной частичной суммы - это и будет позиция самой правой хорошей границы для i (если эта граница больше i). Для удаления нашей суммы из массива обновим значение в ней величиной отрицательной бесконечности. Таким образом легко найти не только максимальную длину хорошей подстроки, но и количество таких подстрок.
Сложность решения: O(n logn) по времени и O(n) по памяти.
That is very cool. Is computing the
s[]array a common trick? Thanks!Сначала сделаем небольшой предподсчёт: для каждой пары lf, rg проверим какое кол-во символов нужно изменить, чтобы подотрезок [lf, rg] стал палиндромом и сохраним это в массиве change[][]. Это легко сделать за O(n^3) времени и O(n^2) памяти. Теперь будем считать динамику z[i][j] - наименьшее число изменений, которое мы должны сделать, чтобы разбить префикс длины i на ровно j палиндромов. Сначала весь массив заполним бесконечностями, а z[0][0] присвоим 0. Теперь будем делать переходы вперёд: переберём длину len очередного (j-го) палиндрома, change[i][i + len - 1] равен кол-ву изменений, чтобы сделать подстроку с позиции i длины len палиндромом, а перейдем мы в состояние z[i + len][j + 1] и сделаем следующее обновление: z[i + len][j + 1] = min(z[i + len][j + 1], z[i][j] + change[i][i + len - 1]). Ответ есть минимум z[n][i], где n - длина строки из входного файла, а i отрезка [1, k]. Чтобы вывести ответ необходимо в дополнительном массиве сохранить предка для каждого состояния.
Сложность решения: O(n^3) по времени и O(n^2) по памяти.
Поправил. Мало спать - плохо(( Самое интересное, что по английски я сразу написал правильно :-)
Add this in method:
if (this.start > arg0.start)
return 1;
Посчитаем суммы на всех префиксах. Разобьем все эти суммы последовательность на Sqrt(n) блоков (block). В каждом блоке найдем максимум. Далее бежим по последовательности (счетчик - i), храним текущую накопленную сумму изменений (sum), проверяем блоки с конца, и если в каком-то блоке block[blockno] - sum >= 0, то заходим в этот блок находим самую правую позицию где выполняется данное условие (втупую), обновляем ответ и собственно заканчиваем обход блоков, т.к. это лучший ответ для текущего i. Блок, в котором находимся в данный момент (где находится счетчик i) обрабатываем отдельно (т.к. оттуда уже были выкинуты некоторые элементы и информация там не актуальна).
Итого сложность O (n * sqrt(n)), зашло за 280 мс на Java.
По Е прошло такое решение, не доказанное:
Не мог понять решение С, потом перечитал условие:
"Никакие два события не начинаются и не заканчиваются в один и тот же год"
А я-то сидел, мудрил (или тупил) с обработкой после сортировки... Ну да ладно, когда-нибудь всё же научусь читать условия... :D
UPD: по зрелом размышлении, этим мой тупёж не ограничился - ну да ладно. Впредь будет наука... ;-)
Хм. У меня еще во время контеста родилось подозрение, что авторы не заметили сравнительно простого решения. На самом деле ее надо решать так. Для начала, чтобы не париться, заменим все гласные буквы, например на 1, согласные на два 0. Легко сообразить, что хорошая подстрока это либо вся строка, либо некоторая подстрока в которой v=2c, а после такой замены v=c. Поэтому в процессе замены заодно проверяем и выводим решения для случая, когда ответ это вся строка и случая с=0.
I am Trying To solve Problem E Last Chance I am using Binary Search on length to find maximum Length which satisfy the criteria. But WA in Case 39
My code: Code
Binary search on length is just wrong.
Here's a case where your code fails.
Test: "baaab"
Your code's output: "3 2"
Correct answer should be: "5 1"
Why the binary search property does not hold should be evident from this example. Basically, if you can form a good substring of length X, there's no guarantee that you can form good substrings of length < X.
THANKS , I UNDERSTOOD. MY NEW CODE GETS WRONG IN 53 TEST. CODE
problem E can be solved using a single map 69492668