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

Автор NikitaMikhaylov, история, 7 лет назад, По-английски

Hello, codeforces!

Recently I came up with a task, but I couldn't solve it.

The task is:

You are given a two arrays a and b of size n (1 ≤ n ≤ 105). You should answer q (1 ≤ q ≤ 105) queries:

  • for given integer k (1 ≤ k ≤ n) you need to find maximal value ai + bk - i.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

Автор NikitaMikhaylov, история, 7 лет назад, По-русски

Всем привет!

Как вы, наверно, знаете доступ/добавление/удаление в хэш-таблице работает за O(1). Сегодня мы попытаемся улучшить эту оценку. Теперь рассмотрим реализацию хэш-таблицы с закрытой адресацией: пусть функция h равновероятно переводит каждый элемент множества A в множество B, те h: A → B, где A — множество возможных значений, а B — первые k натуральных чисел, для просты возьмем k = |A|. Если жи есть два элемента x, y для которых h(x) = h(y), то будем добавлять их в цепочку ячейки h(x) для разрешения коллизий. Вообще раз O оценка — это оценка сверху, то давайте далее полагать, что в каждую такую ячейку попадет t = 1 элементов. Тогда изменим способ хранения элементов со списка на set, но мы знаем, что время работы операций в set есть , но так как размер нашей ячейки t, то операции работают за , отсюда получаем, что n операции на нашей хэш-таблице отработают за O(n·0) = O(0).

Полный текст и комментарии »

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

Автор NikitaMikhaylov, история, 8 лет назад, По-русски

Отправляю код по задаче Е, который как говорит сайт для подсчета символов, содержит 65012 символов, но на кфе пишет, что "Поле должно содержать не более, чем 65535 символов".

Полный текст и комментарии »

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится