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

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

271A - Красивый год

В задаче нужно написать то, что просят по условию: пока в номере года есть совпадающие цифры, прибавляем к номеру 1.

271B - Простая матрица

Предпосчитаем для каждого числа от 1 до 105 следующее простое. Это можно сделать абсолютно любым способом. Главное — не забыть при проверке числа на простоту перебирать делители до корня из числа.

Теперь для каждого элемента матрицы легко понять, сколько к нему нужно прибавить, чтобы получить простое число. После этого остается просто найти строку или столбец с наименьшей суммой.

271C - Секрет

Если 3k > n, решения нет (потому что каждое множество должно содержать хотя бы 3 элемента). Иначе подходит, например, любое разбиение, в котором первые 3k чисел розданы следующим образом:

1 1 2 2 3 3 ... k k 1 2 3 ... k

Для каждого из k множеств, разность между вторым и первым элементами будет 1. При этом ясно, что разность между третьим и вторым элементами будет не 1 (более точно: 2k - i - 1 для i-го множества). Поэтому каждое множество точно не образует арифметическую прогрессию.

При этом не важно, как раздавать оставшиеся n - 3k чисел.

271D - Хорошие подстрочки

Построим из всех суффиксов строки бор (он же — несжатое суффиксное дерево). Давайте перебирать подстроки в порядке возрастания индексов, то есть сначала [1...1],  затем [1...2], [1...3], ..., [1...n], [2...2], [2...3], ..., [2...n], ... Заметим, что переход от одной строки к следующей по сути означает добавление одного символа в конец. Поэтому несложно поддерживать количество плохих букв и "текущую" вершину в боре. Если количество плохих букв не превосходит k, то строка — хорошая. И соответствующую вершину в боре нужно пометить, если она не была помечена ранее. Итоговый ответ — количество помеченных вершин в боре.

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

271E - Три коня

Утверждается, что любую пару вида (x, y) (x < y) можно привести к виду (1, 1 + k·d), где d — максимальный нечетный делитель числа y - x, а k — любое положительное целое число. Значит, каждое из (ai - 1) должно делится на d, то есть d является делителем gcd(a1 - 1, ..., an - 1), и его можно перебрать. Давайте посмотрим, для каких исходных пар d является максимальным нечетным делителем разности — это все пары с разностью ровно d, 2d, 4d, 8d, 16d и так далее. Вспомним, что числа в исходной паре не должны превышать m, а значит количество пар с фиксированной разностью t — ровно m - t.

Итоговое решение: просуммировать (m - 2ld) по всем d — нечетным делителям gcd(a1 - 1, ..., an - 1), при условии, что 2ld ≤ m.

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

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

Быстро однако :)

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

    Комментарий заплюсовали больше, чем пост

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

Слава богу в 4 и хеши прошли

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

    А что за решение с хэшами?

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

      Переберем все хорошие подстроки, кол-во различных подстрок получим при помощи хэшей, это кол-во различных значений хэшей этих подстрок.

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

    А какой тип хеш-функции удобно использовать при работе с длинными строками?

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

Немножко непонятно... Можно для Див2 разборы писать поразборчевее? С примерами что-ли.. Хотя бы так. Мы ведь для того читаем разборы, чтоб чему нибудь новому научится :)

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

    Что именно непонятно?

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

      C) Почему такое решение правильно? D) Ничего непонятно. Нету решения попроще?

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

        Кое-что дописал.

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

          По поводу хэшей зря так пренебрежительно. Мы всегда писали хэши по паре простых модулей, и еще ни разу не попадались коллизии. И писать в разы проще.

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

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

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

                Есть такая вещь, которая в народе ходит с названием "Метод Капуна(eatmore)".

                Вкратце. Будем генерировать две строки из букв a,b. Причем так, что bb не бывает, в одной паре символов. Тогда фактически бывает ( + 1,  - 1, 0) * pk к разности хешей. Надо набрать нетривиальный 0.

                Будем делать так. Отсортируем, возьмем разности двух соседних. Отсортируем, возьмем разности двух соседних...

                Вроде хорошо работает (эксперементально) для хеша с любыми известными параметрами.

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

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

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

              Я думаю , если добавить еще одну хеш-функцию , то не взламает , а если взламает , то можно сделать и третью )))

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

                Если не рандомизируешь хеши — обязательно взламаю три хеш-функции. Там написано, как.

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

              Прошел по ссылке , печаль =( Но мы сделаемь вторую и третью функции до 10^18 и все пройдет ... надеюсь )

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

                А по модулю 10^18 множить сложно без 128-битных чисел.

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

                  кстати, Вы не могли бы поподробнее описать как это можно эффективно сделать, без 128-битных чисел?

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

                  Умножать два 64-битных числа по модулю можно за log(min(a, b)) так же как и возводить в степень. Т.е. a*b = 2*(a/2)*b(если a нечетное) и b+(a-1)*b если a нечетное

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

                  Ну... в первый раз было сложно, потом как-то привыкли :-)

                  Умножение за O(1): mul(a,b,m)

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

                  А как нормально объяснить, что это работает правильно? Казалось бы, всё зависит только от масштабов погрешности при вычислении (a * b) / m, почему она не будет настолько большой, что a * b — r * m повторно переполнится?

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

                  До 263 можно вообще написать так (один if вместо двух while):


                  =========================================================== int64_t temp = (int64_t) ((long double) a * b / c + 0.5); int64_t res = a * b - temp * c; if (res < 0) res += c; assert (0 <= res && res < c); ===========================================================

                  Доказать можно, например, так. Заметим, что умножение и последующее деление в long double правильно вычисляют как минимум 63 знака результата, то есть значение выражения (long double) a * b / c отличается от точного не больше, чем на c / 263 < 1. Между тем, если бы погрешность ответа была больше c или вообще больше пределов int64_t, то погрешность temp была бы больше единицы.

                  А для чисел, больших 263, даже с модулем надо очень аккуратно писать.

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

                  Гасса, по-моему, ты не совсем прав.

                  Берем mingw g++ 4.7.3

                  Пускаем стресс твоего кода для

                  ll M = (1LL << 62) * 1.42;
                  ll c = M - Rand(0, 1e6);
                  ll a = Rand(0, c - 1);
                  ll b = Rand(0, c - 1);
                  

                  assert падает.

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

                  И правда не работает. Прошу прощения.

                  По тому, что настрессилось, похоже, что баг в утверждении умножение и последующее деление в long double правильно вычисляют как минимум 63 знака результата — правильных знаков всего 62?!

                  Для M = 262 - ε стресс-тест не падает. Ну и на том спасибо.

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

                  Больше того, если (1LL << 62) * 1.41, у меня уже не падает :-)

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

                  Ну да, а с 1.42 падает раз в четыре с небольшим миллиона тестов.

                  В общем, хорошо, что я в авторских решениях перестраховывался и писал за логарифм :) .

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

              А чем плохо такое решение с хэшами? Работает достаточно быстро. http://codeforces.com/contest/271/submission/3107201 Тут просто сохраняются границы подстроки в хэш-таблицу, и при совпадении хэша стоки полностью сравниваются.

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

Возможно многие посчитают мой вопрос не в тему, но всё же:

Как можно сжать бор , чтоб поменьше памяти использовал? Задача у меня такая , дана строка , длина , которой в худшем 4000. Надо сделать бор из каждого суффикса. Простой бор будет использовать много памяти. Скажите, если знаете как можно сжать бор. Спасибо.

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

    Можно хранить все переходы в большой хеш таблице.

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

      А можно чуть подробнее? я храню переходы для каждой вершины в структуре, как описывается в emaxx. По этой причине не могу сдатьантимат, получаю ML :(

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

Is there any background in problem E?

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

In 4rth q after so many TLE's I have drawn an inference that generally map is slower than set though both being dynamic memory allocation....

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

I'm quiet new in Java,I keep getting TLE and use trie data structure,any advises?(Though the same code written in C++ got AC) code

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

    It's not because you use Java, it's because you make a lot of substring() calls.

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

      Thanks,so is there a faster way to remove the first character from string?Or i should use array of chars instead of strings or something like that

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

А в Е почему нельзя получить (1,1+k*d+i)? Получили, например (1,1+k*d), i раз показали серому коню, получили (1+i,1+k*d+i), показали (1,1+k*d) и (1+i,1+k*d+i) серо-белому и получили (1,1+k*d+i). Где я ошибся?

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

    1+k*d != 1+i, а по условию серо-белому можно показывать только пары вида (a,b) и (b,c)

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

    Серо-белому мы показываем (a,b) (b, c), т.е. в вашем случае i = k*d

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

Слегка оффтоп. Подскажите, пожалуйста, в чем проблема этого кода 3109675? Я явно не знаю чего-то важного про свой язык. Примерно догадываюсь, ибо вот так 3109702 зашло, но точно не знаю.

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

    Как надо писать. Используй PrintWriter, а System.out.*, насколько я понимаю, после каждого вывода flush'ет все написанное, и соответственно работает долго. Ну и общее для всех языков — выводить по одному символу/числу всегда долго (т. е. порядка 10^5 скорее всего еще нормально, а 10^6 лучше не рисковать, хотя данная задача у меня на Java работает <500 мс и выводит все числа отдельно).

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

      Обычно и использую PrintWriter, в этот раз что-то перемкнуло. Тем не менее, не знал, что Syso так сильно тормозит и почему, спасибо.

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

i m not getting the problem E' editorial can any one explain ?

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

Может ли кто нибудь объяснить почему "Утверждается, что любую пару вида (x, y) (x < y) можно привести к виду (1, 1 + k·d), где d — максимальный нечетный делитель числа y - x, а k — любое положительное целое число." ?

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

    Пусть есть пара (a, a + d), где d — четное, мы ее можем привести к виду (2a, 2a + d), потом

    Теперь d нечетное. Получим из пары (a, a + d) пару (a + d, a + 2d). Из этих пар получим (a, a + 2d), если a нечетное, возьмем пару (a + 1, a + 1 + 2d), поделив получим . Будем повторять операцию пока не получим (1, 1 + d).

    Из пары (1, 1 + d) можно получить (1 + d, 1 + 2d), из них (1, 1 + 2d) потом (1 + d, 1 + 3d) -> (1, 1 + 3d) ...

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

Я тупой )

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

    Попробуй перебрать все числа x подряд до корня из d. Делителем будет либо x либо , других делителей нет.

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

For problem 4, suffix array with lcp can also be used. We can first pre-compute the bad character count for all the substrings and store it in a table. Then, iterating through the suffix array and avoiding duplicate substrings using the lcp table, we can find the answer.

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

Hello. I am having trouble with the problem D (getting TLE). I am using the trie to solve the problem. When I build it, I already keep track of the current number of bad characters. If it is bigger than k, I leave the recursion. The final answer is the number of nodes of the tree.

Could anyone help me please? What am I doing wrong? Code

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

    Why do you have these 2 nested loops in main() function? You are not really using i anywhere.

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

      OMG, thanks RAD. It was something I was trying and forgot to remove.

      for (int i = 0; i < n; ++i)
      {
          put(t, s + i);
      }
      
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem C: in each set Ui, its elements ui, 1, ui, 2, ..., ui, |Ui| do not form an arithmetic progression (in particular, |Ui| ≥ 3 should hold). What's the meaning of it ? Does it means when Ui < 3 there is no necessary to hold this condition ?

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

Can you tell me what's wrong of my code ? Problem D: 3145554

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

    Complexity

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

    You can implement it using sets but I think you have to iterate for len =1 to len=n and index 0 to n-len; after every len you have to clear your set to prevent it from exceeding memory limit

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

В условии задачи "271B — Простая матрица" написано: "Все числа в исходной матрице не превосходят 10^5" На 16м тесте получил WRONG_ANSWER с тестсетом: Ввод 500 500 12049 94371 7867 74623 18885 10113 26774 47637 76701 73692 74195 4160 94333 37410 66541 1199 27239 52785 71905 47842 62308 10971 8560 63210 97819 50498 12505 42028 70200 28028 44579 62078 34406 89615 57617 98120 27861 12181 85291 45956 95828 85881 81979 7839 59479 27960 16236 90485 33265 46465 76333 62455 13691 245 38380 80872 39147 39046 5339 66203 20829 48219 58478 1047 31885 714 96603 71507 97242 58909 4664 76505 88837 51661 72415 35942 5871 96425 80236 18184 67358 80272 65725 36254 30072 50642...

Это ошибка в условии? Или "не превосходят 10^5" означает, что порядок = 5?

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

    Видимо, не превосходят 105 значит, что любое aij ≤ 100000.

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

Problem D 271D - Хорошие подстрочки : This is my code. I've used the concept of Rolling hash/Rabin Karp algorithm. But I guess there are some collisions happening and it's failing on test case number 8. Any help is greatly appreciated. Been trying this for a long time.

Code: 27820412

Update: Solved! I tried many different ways. Initially, I used two hash moduli instead of one, but this exceeded the Time Limit on test #8 (Which is weird!). I ended up using a really large prime (About the size of 2^50) which just passed the time limit for Testcase #8 and passed the cases as well. :)

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

    ya i was also getting wrong answer due to collisions so just used two different numbers 31 and 67 with modulo 1e9+7 and it got accepted

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

D can be solved using 2 pointer and little bit of a lcp array.This is my solution. https://codeforces.com/contest/271/submission/44768791

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

Не могу понять, почему в D во втором тесте ответ 8, там ведь все подстроки будут хорошими

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

Problem C is like using 2 hashes of 10^9 size-TLE Using 1hash of 10^9 size -WA and using a very big hash and multiplying recursive -TLE

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

Problem D is like using 2 hashes of 10^9 size-TLE Using 1hash of 10^9 size -WA and using a very big hash and multiplying recursive -TLE

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

    Hey. Please stop spamming on every tutorial blog with your solutions of Div2 A problems. There are already many solutions available in the submissions section. You're not helping anyone at all. You're just spamming and also unnecessarily bringing old posts in the Recent Actions section.

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

271D using Z algorithm: https://codeforces.com/contest/271/submission/68098565

prereq: distinct substring using Z ( read it from CP algo ).

Implementation: Now I am assuming you know distinct substr using Z, then: we start counting the answer for a prefix after the zmax of that prefix. ( because we'll have distinct substring only after zmax)

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

can enyone help me with D problem? I am tring to sove it with hash but it has wrong answer on testcase 8;

https://codeforces.com/contest/271/submission/243292259