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

Автор yaro, 13 лет назад, По-русски
В этой задаче нужно было научиться отвечать на запрос количества красивых чисел от 1 до R.

Ясно, что чтобы проверить, делится ли число на все свои цифры, достаточно знать остаток числа при делении на наименьшее общее кратное (НОК) всевозможных цифр (обозначим M), то есть M = 8 * 9 * 5 * 7 = 2520. Стандартная динамика подразумевает следующие параметры состояния: длина уже построенного числа, флаг "строго меньше", текущий остаток по модулю M и маску набора цифр, которые уже встретились.

Первое замечание: можно хранить не маску набора цифр, а, опять же, НОК тех цифр, которые уже вошли в число. Это уменьшит количество возможных значений последнего параметра c 256 до 4 * 3 * 2 * 2 = 48 (4 - кол-во возможных степеней двойки и так далее).

Далее, переходы к новым параметрам при добавлении цифры стоит делать с предподсчетом (от остатка к новому остатку и от НОКа цифр к новому НОКу). Мы хотели и постарались поставить такие ограничения в задаче, чтобы и это решение не проходило (а это было непросто, так как разница между Java и C++ по времени выполнения была разительна; в итоге, к сожалению, часть решений обошла TL без нижеизложенной оптимизации).

Идея, которую хотелось увидеть в динамическом решении — числовая. Если добавлять цифры с конца, то можно заметить, что на остаток числа при делении на 5 влияет лишь последняя цифра. Таким образом, можно хранить флаг "последняя цифра = 5 или 0" и запрещать переходы по цифре 5, если флаг не выставлен. Эта идея уменьшает количество состояний в 5 * 2 / 2 = 5 раз. Такое решение без проблем проходило на любом языке, но есть и более сильные оптимизации, тоже основанные на идее делимости (например, можно провернуть этот же трюк с двойкой).
Разбор задач Codeforces Beta Round 51
  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I didn't use either of these optimizations but avoided the 'strictly less' flag (so, the number of states is only 2 times less, while with these optimizations it's 48*5 = 240 times less). Still got AC…
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Please translate it in English, when you get time.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    It has been already translated when you posted this request. You are just using russian interface. Press Great Britain flag in the top right corner of the page, or change "locale=ru" to "locale=en" in the address bar of your browser.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Please translate it in English, when you get time.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Please translate it in English, when you get time.
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Извиняюсь за глупый вопрос, но можно пояснить, что такое флаг "строго меньше" и как его использовать для проверки, что число не выходит за интервал?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Есть максимальное число N (верхняя граница интервала). Динамика идет по позициям десятичной записи слева направо. Если флаг "строго меньше" взведен, значит для перехода мы можем использовать любую цифру от 0 до 9. Иначе, не любую, а только от 0 до той, что в данной позиции числа N.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is the "strictly less" flag?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    We want to count the quantity of beautiful numbers that are not greater than some constant N. Dynamic goes by digits from left ro right. "Strictly less" flag is true means that current number is strictly less than correspoding part of N so we are able to add any new digit from '0' to '9'. "Strictly less" flag is false means that current number equals correspoding part of N so we are only able to add new digits from '0' to the corresponding digit of N.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
хмм ... а как, зная остаток от деления на текущий НОК, зная сам НОК, и зная новый НОК, после добавления нового числа узнать чему будет равен остаток после деления числа на новый НОК ? 
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Никак, поэтому мы поддерживаем остаток при делении на НОК вообще всех цифр (то есть, по сути, остатки при делении на все цифры), а не только цифр построенного в данный момент числа.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо Большое! 
как-то протупил я ...
 Теперь стало понятно - сдал. Правда у меня вместо "строго меньше" - три флага, больше,меньше, равно
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Не понятна оптимизация з 5 и 0, можете кто-то объяснить плз?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вместо хранения остатка от деления на 2520 можно хранить остаток от деления на 2520/5=504 и кроме этого флаг того что цифра из набора {0,5} была последней (только в таком случае 5 может встретиться в числе).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      спасибо, теперь понял, 
      Но я уже придумал другую, оптимизацию: каждый раз обнулять только некоторую часть масива ответов
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In your last paragraph,you say: The idea that will decrease the running time even more lies in number theory. Dost it means "decrease time" is main in number theory,or it can "decrease time" base on number theory? I think it's the first meanning ,but my teammate is the second.⊙﹏⊙b

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

In your last paragraph,you say: The idea that will decrease the running time even more lies in number theory. Dost it means "decrease time" is main in number theory,or it can "decrease time" base on number theory? I think it's the first meanning ,but my teammate is the second.⊙﹏⊙b