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

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

Div.2 – A. Football

В этой задаче достаточно просто найти самую длинную подстроку из одинаковых цифр и проверить или ее длина является не менее 7.

Div.2 – B. Lucky Numbers - 2

Если длина входного числа является нечетным, то, очевидно, искомое число имеет длину на 1 большую и выглядит так: 4444 ... 7777, то есть сначала L / 2 четверок, затем L / 2 семерок, где L - длина входного числа + 1. Если число имеет четное количество цифр, то, возможно, число-результат будет иметь такое же количество цифр, или на 2 больше. То есть, длина результата будет не более чем на 2 длиннее, чем число N. Это означает, что мы можем легко рекурсивно сгенерировать все счастливые числа длиной до 10, выбрать из них очень счастливые числа, среди них найти наименьшее, не меньше N.

Div.1 – A, Div. 2 – C. Hockey

Заведем массив B. Для каждого слова из словаря найдем все вхождения в строке S, для кожного из них B [i] обозначим true, где i лежит в [Li, Ri], где Li - номер самого левого символа следующего вхождения, Ri - самого правого . Теперь для каждого i, для rоторого B[i] = true, сделаем следующее:

  •          Если S[i] = letter і letter = ‘a’, тогда S[i] = ‘b’
  •          Если S[i] = letter і letter != ‘a’, тогда S[i] = ‘a’
  •          Если S[i] != letter, тогда S[i] = letter.

Очевидно, что это удовлетворяет условию и гарантирует максимальное количество letter и ее лексикографическая минимальность. Также нужно аккуратно различать большие и маленькие латинские буквы.

Div.1  - B. Lucky Number

Сначала смотри Div.2 – B

Заметим, что ответ будет примерно таким: к какой-то позиции результат будет совпадать с N (эта часть будет счастливым число), следующая цифра увеличится, а затем будет идти как угодно. Переберем все такие возможные позиции. Чем больше номер такой позиции, тем меньше будет число. Возможные позиции будут в промежутке [0, lucky_prefix], где lucky_prefix - размер наибольшего префикса строки (числа N), который является счастливым. Пусть мы рассматриваем позицию i. Если цифра в ней меньше 4, мы можем установить ее 4, при этом можем как угодно менять все цифры правее. Так же, если цифра меньше 7 (только в случае если она больше или равна 4) - установим ее 7. При этом некоторые позиции могут нам не подойти. Для того чтобы позиция подошла, нужно чтобы абсолютная разница между количеством четверок и семерок к позиции i (включая i, включая замену) была меньше или равна размера части справа от i. Теперь пусть позиция i подошла нам (и она является самой правой возможной), тогда нужно заполнить правую часть. Ее следует заполнять следующим образом слева направо: если на какую позицию мы поставим 4 и дальше сможем заполнить число так, чтобы количество четверок и семерок была равной (т.е. abs (c4 + 1- c7) <= n-j-1, j - текущая позиция которую рассматриваем, c4, c7 - количество 4-ок и 7-ок в позиции j, включая заменены цифры), то поставим 4, иначе 7. Если позиции i не существует, то ответ - число в форме 4444 ... 7777, здесь количество четверок = количеству семерок = (n +2) / 2.

Div.1 - C, Div.2 - D. Volleyball

Сначала в этой задаче нужно найти минимальный путь между всеми парами вершин. Так как их количество до 1000, то обычные кубические алгоритмы по времени вкладываться не будут. Для этого нужно было написать алгоритм Дейкстры за O (N * (N + M) * logN), подробнее об этом можно прочитать здесь: http://e-maxx.ru/algo/dijkstra_sparse. Следующей частью решения задачи является составление новой матрицы, для которой G[i][j] = C[i], если D[i][j] <= T[i], иначе G[i][j] = INF. Здесь D[i][j] - минимальный путь между вершинами i и j, G[i][j] - стоимость такого пути. Теперь нужно просто найти минимальный путь между вершинами X и Y используя G, что можно выполнить используя простой алгоритм Дейкстры за O (N * N + M).

Div.1 – D, Div.2 – E. Horse Races

Традиционно напомню, что ответ будет Результат (0 .. R) - Результат (0 .. L-1).

Пусть у нас есть заполненный массив DP[x][y][z] - количество чисел длины x если последняя счастливая цифра в нем была на позиции y и boolean z (0 or 1) - была уже пара счастливых цифр на расстоянии не больше K. Ответ теперь будем строить так. Пусть s - строка, которая является числом N, F (x, y, z) - результат для префикса к позиции x, y - последняя счастливая цифра, z (0,1) - была пера счастливых цифр на расстоянии не более K. Очевидно, что если мы в какой позиции поставим меньшую цифру чем в строке, то все цифры справа мы можем выставлять как угодно (если только все цифры слева от этой позиции совпадают с лентой). Переберем возможные цифры, которые поставим в текущей позиции. Если эта цифра меньше чем s [x], тогда к результату для F (x, y, z) добавим DP [n-x-1] [yy] [zz]. Здесь y и z возможно изменится и перейдут в yy и zz, если цифра которую мы устанавливаем является счастливой. Если эта цифра равна s[x], тогда к результату прибавим F (x+1, yy, zz) - опять, y и z изменится, если s [x] является счастливой цифрой. DP заполняется тривиально. Пусть из состояния (x, y, z) мы ставим на позицию x какую цифру d. Из состояния (x, y, z) мы можем перейти в состояние (x+1, yy, zz). y перейдет в yy и z в zz при тех же условиях что и выше.

Сложность - O (T * |N|).

Div.1 – E. Lucky Country.

Пусть все A[i] - посортированы размеры различных компонент связанности, C[i] - количество компонент размером A[i]. Сумма по всем C[i]*A[i] равна N. Размер массива A будет O (sqrt (N)).

Решение # 4 (предложенное RAD-ом

Для каждого A[i] будем рассматривать отдельно классы по модулю A[i] (их будет A [i] - от 0 до A [i]-1). Переберем такие классы. Пусть это класс j. Дальнейшее будем рассматривать только те k, которые по модулю A[i] = j. Для каждого из них посчитаем DP[k] = min (DP[j - A [i] * C [l]]) по всем l от 1 до C[l]. Чтобы такой алгоритм вложился по времени нужно структуру, которая выполняет следующие операции за O (1) - минимум, добавлять элемент, удалять элемент, добавить ко всем элементам в структуре 1. Читай http://e-maxx.ru/algo/stacks_for_minima.

Сложность - O (sqrt (N) * N).

Решение # 7

Пусть все C [i] = (2^k) -1. Разложим его следующим образом 1 + 2 + 4 + 8 + ... + 2^(k-1). Очевидно, что если выбирать из такого множества какое-то подмножество (его стоимость будет равна ее размера), можно представить любое число от 0 до C[i]. То есть мы свели задачу к следующей. Для каждого A[i]  есть log (C [i]) вещей, каждая из которых имеет стоимость и может быть использована или не использована. Это уже стандартная задача о рюкзаке (почитай http://ru.wikipedia.org/wiki/Задача_о_рюкзаке). Сложность такого решения O (N * S), где S - сумма по всем log (C [i]). Если же C[i] не является степенью двойки, то нужно найти наибольшее k для которого (2 ^ k) -1 <= C[i] и добавить в множество C[i]-((2^k)-1).

 

 

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

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

Я в задаче про волейбол просто выбирал ближего по "стоимости достижения" таксиста из необработанных и BFS-ил от него на расстояние не дальше t[current], расставляя reach[i] = min(reach[i], reach[current] + c[current]). Среди всех текущих достигнутых и необработанных снова выбирал самого дешевого по достижимости reach[i] и снова цикл до упора пока выбранным для обработки не окажется конечный таксист (конечный перекресток). Только доотлаживать не успел, на дорешивании сдал.

UPD: reach[i] - это стоимость в деньгах за сколько мы на перекладных доберёмся до этого таксиста. Соответственно reach[x] = 0, reach[y] = ответ
13 лет назад, # |
Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

На задачу B можно написать рекурсивную функцию построения ответа (если перед этим проверить, что ответом является число такой же длины, что и исходное):

Пусть мы построили первые i-1 символов ответа и строим теперь i-тый, и нам нужно поставить ещё cnt4 четвёрок и cnt7 семёрок
Если cnt4!=0, то пытаемся поставить четвёрку: Если в i том находится число меньшее четырёх, то мы просто ставим все оставшиеся четвёрки, потом ставим все оставшиеся семёрки. Если же находилась четвёрка, то пытаемся достроить число. Если можем, то тогда выходим из рекурсии.
Если же 4-ку поставить не вышло, то делаем то же самое для 7-ки.
Если и 7-ку поставить не вышло, то сообщаем о провале и откатываемся.

В сумме откатимся мы не более одного раза. Пусть мы поставили 4-ку и не смогли построить число, тогда мы поставим 7-ку и число точно можно будет построить ( если семёрок нет, то собственно выбора у нас нет и мы продолжим откат). Если же мы не смогли построить ответ, когда в какую-то позицию поставили 7-ку, то значит нам нужно будет откатится до 4-ки раньше, а она точно будет, т.к. мы проверили, что мы можем построить ответ заданной длины.
Значит максимальное количество раз, которое будет вызываться функция построения ответа N + N/2(N/2 - максимальное количество семёрок, а значит и длина отката, ведь мы будем откатываться до первой четвёрки)

Update: Я вроде всё же ошибся с подсчётом максимального количества вызова функции... может быть мы поставили сначала одну четвёрку, все семёрки, а потом остальные четвёрки и последнюю поставить не смогли, то мы сначала откатимся до первой семёрки, ведь с четвёрками у нас не будет выбора, а потом только до первой четвёрки. Т.е. функция будет вызывана N раз, но мы можем откатится назад до первого шага и потом построить весь ответ
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Кто делал решение #7 для Div-1 E, там с MLE не было проблем?
Потому что мне удалось запихать только после замены массива на short[][] и еще одного шаманства
Двумерный массив не нужен
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Откуда проблемы с памятью? Там же её как раз O(N * S) используется, это довольно мало. Да и какие могут быть шорты с ограничением до 105? %)
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Да нифига это не мало, как оказалось. Вот это самое S слишком большим оказывается. Ну хотя может я слишком много объектов насоздавал, когда искал массивы компонент связности.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Были проблемы. Посмотрев решения других участников я увидел решения за O(n) памяти. В них был рюкзак но с хитрой релаксацией, больше похожей на жадину. Рекомендую посмотреть решения других участников или мое.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    зачем двумерный массив ? для рюкзака? так его же можно писать с линейной памятью
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
"Сумма по всем C [i] равна N"  думаю здесь ошибка, (сумма по всем i   A[i] * C[i] ) == N
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Where is the English version?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is T in the last sentence of Div1-D analysis?
"Complexity – O(T * |N})"
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Problem E div1 "For each A[i] is log(C[i]) things (cost of this thing is size of subset that create it)"

may u explain "size of subset" more clearly?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Look, if we have C[i] components of A[i] vertex, cost of each of this C[i] things (in standart knapsack algo)  is 1 (we need one new edge). In this case we decompose each C[i] in 1 + 2 + 4 + ... 2^k and costs are now 1, 2, 4 ... , respectively.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Are there any O(N*W) solution in http://codeforces.net/contest/95/status/E , Can you show me where it is ?