Блог пользователя Edvard

Автор Edvard, 13 лет назад, По-русски

A. Открытки и фотографии

Будем идти по строке слева направо. Если мы прошли всю строку, либо в руках у нас уже 5 предметов, либо очередной предмет отличается от тех, что мы держим в руках, то относим все предметы в кладовку. Ответом на задачу будет количество посещений кладовки.

Сложность решения O(n).

B. Перестановка

Посчитаем количество чисел от 1 до n, которые встречаются в последовательности хотя бы один раз. Тогда ответ есть n минус это количество.

Сложность решения в зависимости от реализации O(n) или O(n logn).

C. История

Отсортируем пары, заданные в условии по году начала события. Будем идти по массиву этих пар и поддерживать значение rg - самый поздний год окончания какого-либо из уже обработанных событий. Тогда если для текущего года окончания события - year, верно что year < rg, то нужно прибавить к ответу единицу, поскольку данное событие покрыто каким-то из ранее обработанных (поскольку все обработанные события имеют левую границу меньше нашей и какое-то из них имеет правую границу rg большую year). После этого пересчитываем rg следующим образом: rg = max(rg, year).

Сложность решения: O(n logn) - на сортировку и O(n) - на решение.

D. Палиндромы

Сначала сделаем небольшой предподсчёт: 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) по памяти.

E. Последний шанс

В этой задаче можно было подумать, что при фиксированном начале строки функция "хорошести" от конца строки монотонная, но это не так (хотя бы на примере строки 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) по памяти.

Разбор задач Codeforces Beta Round 98 (Div. 2)
  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
In E, you can easily do O(n) without interval tree. Let s[k] = max{p[i] : i=k, k+1, ..., n}. The values of s[k] are non-increasing and can be computed in linear time. For every i, you want to find maximal j >= i such that p[j] >= p[i] - in other words, the last j such that s[j] >= p[i]. You can either binsearch it (an easier n log n solution), or observe that when you find a good interval (i0,j0) and want to find a better one (i1,j1) with i> i0, there must be p[i1] < p[i0] and j> j0. Therefore, you increase the value of i until you find smaller value of p[i], and then increase j until s[j+1] < p[i]. As the indices i, j only move right, the complexity is linear.
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Edvard, по-моему в D ты разобрал немного другую задачу :) Что-то похоже на задачу про разбиение строки на минимальное кол-во палиндромов, только второе состояние лишнее. Нужно чуток поменять, как-то так:

Сначала сделаем небольшой предподсчёт: для каждой пары 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) по памяти.

  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Поправил. Мало спать - плохо(( Самое интересное, что по английски я сразу написал правильно :-)

»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Could anybody have a quick look at my solution?
I tried to figure it out why I could not pass Test Case 15. However, hours passed without any good results.
Link: code.

Thanks so much.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Maybe mistake in compareTo ?
    Add this in method:
    if (this.start > arg0.start)
        return 1;
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I made the same mistake in my C++ code when implement my own comparison function %>_<%
»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
В E по причине банальной лени, написал свою любимую SQRT-декомпозицию. Решение тупое и простое:
Посчитаем суммы на всех префиксах. Разобьем все эти суммы последовательность на Sqrt(n) блоков (block). В каждом блоке найдем максимум. Далее бежим по последовательности (счетчик - i), храним текущую накопленную сумму изменений (sum), проверяем блоки с конца, и если в каком-то блоке block[blockno] - sum >= 0, то заходим в этот блок находим самую правую позицию где выполняется данное условие (втупую), обновляем ответ и собственно заканчиваем обход блоков, т.к. это лучший ответ для текущего i. Блок, в котором находимся в данный момент (где находится счетчик i) обрабатываем отдельно (т.к. оттуда уже были выкинуты некоторые элементы и информация там не актуальна).
Итого сложность O (n * sqrt(n)), зашло за 280 мс на Java.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    прикольно, O(nlog2n), что вроде бы меньше, зашло за 610 мс на gnu.
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

По Е прошло такое решение, не доказанное:


Изначально пусть len=длина строки. Посчитаем количество гласных в исходной строке (пусть это будет gl, до замены на -1/2 я не догадался). Если исходная строка подходит - все хорошо, иначе очевидно, что все строки, длина которых >3*(len-gl), нам не подходят. Теперь обновим len=3*(len-gl) и будем так же продолжать проверять все подстроки длиной len, пока не найдем подходящую подстроку. найдя ее длину, легко найдем количество нужных нам подстрок заданной длины.

Ассимптотику так и не посчитал. Зашло за 1780мс. http://codeforces.me/contest/137/submission/960183

UPD: на  MS C++ 1780мс, на  GNU C++  и GNU C++0x тл68. Кто посоветует, что обычно работает быстрее?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вообще бывает совсем по разному. У меня много раз было, что на GNU проходило а на MS нет, было и наоборот.
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Не мог понять решение С, потом перечитал условие:

"Никакие два события не начинаются и не заканчиваются в один и тот же год"

А я-то сидел, мудрил (или тупил) с обработкой после сортировки... Ну да ладно, когда-нибудь всё же научусь читать условия... :D

UPD: по зрелом размышлении, этим мой тупёж не ограничился - ну да ладно. Впредь будет наука... ;-)

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Хм. У меня еще во время контеста родилось подозрение, что авторы не заметили сравнительно простого решения. На самом деле ее надо решать так. Для начала, чтобы не париться, заменим все гласные буквы, например на 1, согласные на два 0. Легко сообразить, что хорошая подстрока это либо вся строка, либо некоторая подстрока в которой v=2c, а после такой замены v=c. Поэтому в процессе замены заодно проверяем и выводим решения для случая, когда ответ это вся строка и случая с=0.


Далее пишем примерно такой код
void solve(char c) {
int sp=0;
for (int i=0;i<n;i++)
if (s[i]==c)
stack[sp++]=i;
else if (sp>0)
--sp, L[stack[sp]]=1+i-stack[sp]
}

for (i=0;i<=n;i++) L[i]=0;
solve(0);
solve(1);
После этого в L[i] будет длина кратчайшей подпоследовальности у которой количество нулей равно количеству единиц.
Далее такой эзотерический код
for (int i=n-1;i>=0;--i)
L[i]+=L[i+L[i]];
Теперь осталось просто найти в L[i] максимумы и их количество. Это и будет ответ. Сложность линейная.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can someone please explain problem D Div 2 ? What are we supposed to do ? 
 Thank you ver much .
»
9 лет назад, # |
  Проголосовать: нравится 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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

problem E can be solved using a single map 69492668