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

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

Доброго времени суток, друзья)

Через несколько часов состоится очередной раунд Codeforces #166 для участников Div. 2. Как всегда, остальные могут поучаствовать в соревновании вне конкурса.

И вновь для вас старалась группа авторов: Павел Холкин (HolkinPV), Николай Кузнецов (NALP), Артем Рахов (RAD) и Геральд Агапов (Gerald). Традиционно хочется поблагодарить Михаила Мирзаянова (MikeMirzayanov) за системы Codeforces и Polygon, а также Марию Белову (Delinur) за перевод условий задач.

UPD: Распределение баллов будет немножко нестандартным — 500, 1000, 1500, 2000, 3000.

Надеемся, что соревнование окажется удачным для всех участников. Желаем высокого рейтинга, успешных взломов и хорошего настроения)

UPD2: соревнование завершилось, надеемся оно вам понравилось)

Поздравляем победителей:

1) xrvpud221
2) xyz111
3) nanoha
4) wyx528
5) GuyUpLion

UPD3: разбор задач уже опубликован, его можно найти здесь

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

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

This group always offers good problems...!!!

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

Сегодня по старинке, первые 300 мест получают те, кто быстро и безбажно закодят первые 2 задачи?

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

    прошлый раз первые 2 задачи мне хватило, чтобы получить 88-ое место и выйти в div1

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Легкие задачи не нравятся... Тяжелые тоже не нравятся... Что ж мы за люди такие =)

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

      Я в тот контест тоже получил 88-ое место и вышел в div-1 :D Надеюсь в этот раз такого не будет

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

        Ты не хочешь в div-1? :)

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

          Хочу конечно, но еще не чувствую себя достаточно сильным для него :)

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

    Сегодняшний контест был намного лучше.

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

Так долго ждали... И дождались! =)

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

Распределение баллов определим чуть позже)
В последнее время стало популярным хранить эту тайну до начала контеста)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    В последнее время стало попоулярным решать это незадолго до контеста, скорее

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Не вижу ничего плохого в этой практике. В любом случае влияние на окончательные результаты минимальное

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

MikeMirzayanov's contribution is +210 O_O

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

Учавствовал в контесте HolkinPV => стал специалистом. Учавствовал в контесте HolkinPV второй раз => стал экспертом. Участвую в контесте HolkinPV третий раз => ???

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

Нестандартное распределение баллов: 500, 1000, 1500, 2000, 3000

К чему бы это?

Всем удачи! (особенно новичкам)!

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +45 Проголосовать: не нравится

    Такие все шутники) но иногда приятно) ставлю плюс)

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

Пятую не трогать.

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

Надеюсь взять реванш за прошлый контест(больно уж плохо я сдал в тот раз).

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

I am sexy and i am no it.

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

Daite mne pou4astvovati

na 1 min opozdal :(

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

its time

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

Мда, одну задачу сделал... Лучше, чем ничего, и все равно, что другие не могу :)

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

    Напишу еще один пост, чтоб можно было и его минусовать. Но, собственно, за что минус? За то, что я одну задачу решил?

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

      Молчи пока -60 не получил:))

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Минусы — это эквивалент полезности донесенной тобой информации до людей. Зачем мне знать сколько задач ты решил?

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

        Да ладно! "Такие все шутники) но иногда приятно) ставлю плюс)" — 10 плюсов, но какая людям разница, что он тоже постаил +?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

          А почему вы так печетесь о своем вкладе. Как-будто от этого у вас что-то длиннее станет

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

Hi authors, Problem C div2 says that any alternative solution is accepted. So this answer for test: 11 3 11122233123 shouldn't be accepted?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    It should, but you should have printed the blank spaces between each number...

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

    if we divided in three group it will be:

    • 1 2 3 9
    • 4 5 6 10
    • 7 8 11

    all 3 of the sequence is not an arithmetic progression

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

Сложный контест для Div.2 :(

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

    Ну первые три задачи решались достаточно легко, а остальные уже веселее.

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

Как Е решается?

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

    Нужно посмотреть на разности между числами. Понять, что если изначально была разность k, то через несколько преобразований мы сможем получить такие и только такие числа: пусть k1 — это k поделенное на максимальную степень двойки, на которую делится k. тогда мы можем получить любую разность вида k1 * x (x > 0).

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

      Доделывается так: k1 делит (ai — 1) для любого i. То есть, k1 — нечетный делитель НОД(ai — 1). Перебираем k1 за корень. А дальше понимаем, что k = k1 * 2^l. Перебираем l, увеличиваем ответ на m — k.

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

      Как из x получить 2 * x я понял, но как получить остальные?

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

Как С решается?

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

    Если [n/k]<=2, то выводим -1. (Вроде очевидно — ведь хотя бы в одно множество попадает два числа — они и будут образовывать прогрессию).

    Пусть n mod k = 0. Тогда в каждое множество можно записать n/k чисел. Первые n-k чисел заполним числами 1,2,3,...,k (по n/k — 1 каждого). Остальные (с n-k+1 по n-ный) последовательностью 1,2,3,...,n. Получим что-то вроде 1,1,...,1,2,2,...,2,...,k,k,...,k,1,2,...,k.

    Очевидно, что если бы хотя бы одна из последовательностей образовывала бы прогрессию, то ее разность была бы равна 1 (Поскольку n/k>=3, то n/k — 1 >=2. Значит, в последовательности-ответе для каждого i=1,k всегда есть хотя бы два подряд идущих числа i). Но очевидно, что число i стоит и на i*(n/k — 1)й позиции, и на (n+1-i)й, из-за его разность не может равняться 1. Таким образом, эта последовательность является ответом.

    Если же n mod k!=0, то оставшиеся ячейки можно заполнить любыми числами.

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

      С-шку решали кто во что горазд (кто как придумает перемешать). Я выводил так: 1..k, k..1, 2, 1, 4, 3, 6, 5...k, остальное заполнял единицами)

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

      Если n / k < 3, то -1. Иначе, выводим k, 1, 2, 3, ..., k — 1. Потом выводим 1, 2, ..., k, 1, 2, ..., k пока длина не будет равна N. Мое решение тут.

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

Это чувство... Когда ты получил по D меньше, чем по B

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

for all who had WA #8 in problem D,I think the test case is

abaab 01 2

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    and what do you say abt TLE + memory limit exceeded for D.

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

Почему в C(div 2) на 1 тесте не проходит 12332112332 всё понял

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

    Вторая группа образует арифметическую прогрессию.

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

    У тебя 2-ой в арифметической прогрессии. Через три

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

    Двойки образуют арифметическую прогрессию

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

    Между всеми двойками стоит по две цифры.

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

    Числа 2 5 8 11 — арифметическая прогрессия с разностью 3

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

Как писать Д-шку без хэшей?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Можно было написать бор

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

      Я конечно туплю, но что потом?

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

        Находим подходящие подстроки, в бор добавляем все их суффиксы. Ответ — количество вершин в боре, которые являются концом какой-либо строки.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Переберем внешним циклом длину подстрок переменной len. внутри цикла заводим сет строк. далее перебираем все подстроки данной длины и складываем их в сет. после размер полученного сета плюсуем к итоговому ответу. со скрипом, но заходит..

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

    Можно префикс-функцией. Берем окончание начальной строки сначала длины 1, потом 2, ..., считаем каждый раз префикс-функцию, пробегаем по массиву-результату и смотрим наибольшее число — пусть m. Тогда все подстроки текущего окончания длины больше m будут новыми, осталось проверить их на хорошесть.

    UPD. код

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

Кто-нибудь взламывал B на тесте 500 500 97430 .... Вроде должен быть ТЛ, если от элемента матрицы искать в лоб ближайшее простое. У меня не получилось загрузить тест(

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

    Был подобный тест, загружал генератор

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

    А что должно произойти? У меня решение "В лоб", что называется, сейчас протестировал -- меньше секунды.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      O(500 * 500 * 1200) как бы

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

        Я рассчитал один раз массив с простыми числами. Дальше -- просто считаем "расстояние" от этого числа до ближайшего простого. Где тут 1200? Вот моё решение (ну там только не из файла считывал, а так): http://pastebin.com/Lu3jHYJb

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          В лоб, это когда если число не простое, каждый раз за корень делать проверку следующего числа.

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится -6 Проголосовать: не нравится

            В лоб — просчитать простые решетом, а затем от текущего идти до следующего. Можно бинпоиск было запихнуть

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

          Если взять число 97430, то следующее простое только через 1200 шагов. Всего чисел 500^2. Значит выше 250 миллионов операций. Почему прошло — без понятия

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

            Да, объяснили уже. У меня не совсем в лоб. Я простые заранее посчитал.

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

            300 млн 500 * 500 * (на макстесте порядка 100, а не 1200) операций вида "прибавь один, посмотри в массив" работают очень быстро — у меня на джаве чуть больше 200 мс.

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

            проверка за корень числа близкого к 100.000 — это 330 операций. следующее простое 97441,то есть 11 шагов и это 3500 операций. 25000 * 3500 < 100 лямов, откуда 250?

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

Понравилась задача С. Вроде не сложная, но думать пришлось =))

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

    да жалко что не успел сабмит сделать) считал своим долгом выводить 123321123321, не догнал что можно сразу сделать так 321123123, зато вот номерок счастливый отхватил

    кстати скажите кто-нибудь как можно быстро сделать это вот самое 123321123321 а то тормозил тормозил

    UPD оказалось проще всего 234112341234

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

      Не проще 112233123111?

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

      двойка образует прогрессию

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

        А за что минусы, там же правда для 2-ки прогрессия.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Оба варианта неправильные, ведь числа 2го будут образовывать последоваотельность с разницей 2.

      Можно сделать так

      если n < 3 * k ответ -1

      иначе выводим 1 2 ... k 2 3 .... k 1 1 2 ..... k

      в первом случае разница будет 2k, k — 1, k — 1 , ... k — 1

      во втором — 1, k + 1 , ... k + 1 оставшиеся числа пихаем рандомно, к примеру, все 1

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

        хмм, да действительно опять я налажал. Надо будет обязательно сдать. У человека в комнате была офигенная реализация 3096917

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

Блиииин, уверен на 90%, что Time limit на задаче D был бы взят, если б это был не Ruby...

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

    Так минусуете, будто у вас есть аргументы против, лол.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Какой смысл писать задачу, где важна производительность, на заведомо более медленном языке?

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится -6 Проголосовать: не нравится

        Какой смысл тогда в наличии интерпретаторов медленных языков на codeforces?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          Чтобы писать то, где не нужна производительность?

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

            Только если С для того, чтобы можно было пройти с плохим алгоритмом.

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          А никто вам не гарантирует, что решение должно существовать на всех возможных языках. Голова должна быть, чтобы решать, какой язык выбрать. Тем более, если знаете об особенностях конкретного языка.

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

    Ну вот, B свалилась ..( Обычно в Div.2 вторая задача не требует таких оптимизаций... а сейчас она валится даже у тех, у кого D прошла.

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

      И этот заминусуйте просто так, plz. Я люблю вами командовать.

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

        Может уже хватит плакаться? Если не нравятся контесты, либо ищите другую платформу, либо выдвигайте конкретные идеи по улучшению/создавайте свой контест.

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

          Может уже хватит юродствовать? Идея существует давно. На mipt-e. Множители на каждый язык http://acm.mipt.ru/judge/info.pl?show=faq

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится

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

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

Удалено по причине большого количества минусов.

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

    Какой именно предпосчет в B вы собрались делать?

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

      Преподсчёт простых чисел, ровно это же делают, кстати, в разборе. Моё топорное решение завалило 14 тест.

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

        Уточню: для каждого числа предподсчёт следующего простого числа.

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

          Есть очень много решений, не использующих предпосчет, получивших полный балл :) Например, lower_bound'ом по массиву простых чисел.

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

Был ли в D antiheshtest?

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

    У меня прошёл хэш

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

      Мое решение получало ВА 8 (наверное анти-хэш), пока я не поставил двойное хэширование -> AC.

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

        Я проходил ва 8 тупо за счет увеличения модуля

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

      У меня хэши получили WA41

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

        Многие хэши валились с WA 41.

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

          Потому что там abbabaabbaababbab... :)

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

          Что интересно, аккуратное решение в лоб через сэт и копии подстрок без всяких хэшей проходит, хотя теоретически асимптотика у него не очень: О(n^3), если вообще не О(n^3*ln(n)).

          3103424

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

            У меня не прошло — даже на претестах ТЛ 8.

            Upd. Дали бы сразу ссылку на код, теперь мой коммент лишний

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

              у вас МЛ, а чтоб его избежать, нужно во внешнем цикле перебирать длину подстроки, и на каждой его итерации очищать мэп, иначе ж у вас О(n^3) памяти кушается.

              Ссылку дал сразу: как можете видеть, то сообщение не редактировано=)

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

            во во, у меня такое же решение прошло... странно..

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

            а почему если я использую бор для проверки на копию, у меня тл? вроде должен быстрее работать чем сет? нет?

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

              Если я правильно понимаю, то это — 3101706 тот код и тут O(n^3) сложность.

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

                асимптотически да, но это же тоже самое, что и с сетом, только без логарифма? Разве сравнение строк не за О(legnth)?

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

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

                  С бором можно не каждую новую подстроку добавлять заново, а, добавляя к подстроке один символ, переходить в боре по одному ребру. Тогда будет O(N2) времени и O(N2 * |Σ|) памяти.

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

The problems were excellent! The problem-setters deserve a round of applause.

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

Nice problem set, the writers managed to come up with balanced problems, got 4 out 5.

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

waiting for rating update .....

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

In problem D, I use 2 hash value with int always get wrong answer on test 41, and my answer always is 241238 (the right is 398680), and I use long long with same hash numbers get accepted. Why there is so big difference between them ? Many helps !

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

    I just exchanjed power of prime number from 31 to 29 and 37, then got accept.

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

      You guys use hash without handling conflict, and still got ACCEPTED! How unfair... I found a nice c++ solution(3100030) in my room that use set<string>, and the worst time complexity is O(n^3 log(n)), still very nice, though.

      My first attempt was a Python solution using a Trie, which is O(n^2). It got TLE, saddly. Then I was forced to translate the Python script into C++.

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

        I used suffix array with time complexity O(nlog^2n) in building the array and O(nlogn) for the rest.3108063 This is totally unfair that even solution with time complexity O(n^3logn) can be accepted. The test case should be bigger, say string of length 1000,000.

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

          When the data scale is too large, we will lost some interesting solutions. It's also unfair for some dynamic languages since a loop with 1000000 times may cost about 1 sec. So I think 10^3 or 10^5 is fine.

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

After participating in some contests here, now, I confess that I'm not clever enough as I thought I am :( I'm not sure if continue to participate will make it better; I even can not get to 1700 :(

Any friend has an idea about why I'm not successful here as much as my successful in business software development (I am Microsoft Visual C# MVP 2011)?!

I just like to know if I should continue or break to study more and then come back.

Thanks in advance!

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    1. Being successful in X does not automatically mean being successful in Y.
    2. Why take a break? Theory is nothing without practice. Study more and compete in contests.

    Remember… practice makes perfect.

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

    It is a wonderful place to get knowledge and I don't have a great result but I am trying to be better day by day here.

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

Хм... Почему этот контест не отображается в списке моих соревнований. И не повлиял на рейтинг... Никто не знает, почему?

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

Anyone willing to share an idea for E problem?

Sorry accidently posted 'in russian'

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

Anyone willing to share an idea for problem E?

  • »
    »
    11 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +6 Проголосовать: не нравится

    My idea was based on this observation:

    Suppose that y=x+k

    What we really care for is the difference between a pair of numbers (the k).

    (because we can get (a+1,b+1) and (a-1,b-1) from (a,b) )

    The first horse does not change the difference

    The second horse divides the difference (k) by two

    The third horse gets two pairs with differences = k1,k2 and gives a pair with difference=k1+k2

    (The rest is simple NT -divisibility, gcd,etc.- )

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

      I thought with the same idea in the contest but actually first horse give (a+1,b+1) form (a,b) but don't give (a-1,b-1)

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

        (a, b) -> (b, 2 * b — a) -> (a, 2 * b — a) -> (2 * a — 2, 2 * b — 2) -> (a — 1, b — 1)

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

Thanks to the creators , for making the catching stuff in the questions BOLD, it really helped!!

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

Задачу C я делал так:

112233441234

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

Unfortunately I missed the contest.. Was celebrating my birthday

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

its showing me new color but old rating :( :( yyyyyy so ?

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

its showing me blue color but with old rating :( :( yyyyyyyyyy so ?

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

It's showing me blue but with older rating 1448 :( why ???

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

Подскажите, пожалуйста, почему это решение для B http://pastebin.com/pLx8hKxx валится уже на первом тесте (3102799) из условия (хотя у меня на машине всё ок):

Ввод 3 3 1 2 3 5 6 1 4 4 1

Вывод 0

Ответ 1

Комментарий чекера wrong answer 1st numbers differ — expected: '1', found: '0'

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

    Проблема в строке

    uint64 min = 1ul << 40;
    

    Суффик ul означает unsigned long, а не unsigned long long и при сдвиге на 40 битов 32-хбитного числа происходит undefined behavior.

    Правильно будет

    uint64 min = ((uint64)1) << 40;
    

    или

    uint64 min = 1LL << 40;
    
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone explain Div2.E problem body? As I understand:

  1. We start with singleton, S = {(x,y)}.
  2. Given some set S of cards, we pick one card (x,y) from S, perform 1 of 3 operations(in third operation we would take two cards), and get new card (x', y')
  3. S now contains both (x,y) and (x',y') We want S to include some subset P.

But it surely isn't correct understanding.

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

Anyone willing to share an idea for problem D without hash? Thanks a lot.

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

    prefixs + substrings + set = 3103424

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

      thankyou

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      please explain how could this pass?

      you have 2 "for" and inside them you have "substr" which has complexity O(j-i) so your total complexity is O(N^3)

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

        You are right, but it has a low constant, so 2 "for" and "substr" inside them take only 350 ms on a string with length=1500.

        Also working with set we have total complexity O(N^3*ln(n)), because comparing the string takes O(N). But it is also with low constant and is unattainable, because not all substrings are comparable in full length.

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

Four of the winners took part in Codeforces contest for the first time,the rest one only took part twice....

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

One question: the limit for the Div2 B were n,m <= 500, but what is the point to have such limits, when the max size of test file for hacking is just 256 KB? I mean there were a lot of solutions that could be hacked using a matrix of size 500 x 500, but it wasn't possible because the system won't accept files that big. Many solutions were done in O(n*m*nextPrime(x)) and I think this wasn't the complexity intended to solve this problem. An acceptable one would be done in O(n*m*log(closestprime(x)).

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    you have to write code to generate test-cases you want ,not the test-case itself

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

    nextPrime(x) factor is extremely small ~ O(log x), so it's just looking for 20 consecutive bytes of memory. Bad binary search could be slower.

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

Ждем не дождемся Codeforces Round #167