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

TopCoder SRM 484
Автор Egor, 14 лет назад, По-русски
6 октября в 5:00 MSD состоится очередной TopCoder SRM. Всем удачи!
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Скажите как RabbitNumber считается? (и причем тут DFS)
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Есть несколько вариантов.
    Можно заметить, что все цифры не более 3
    Можно заметить, что квадрат суммы цифр не более 18 * 9
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Первое я умею замечать и даже доказывать. А вот можно поподробнее про квадрат суммы цифр?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Ну, квадрат суммы цифр равен сумме цифр квадрата. Продолжать?
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        он же равен s(x*x), x*x<=10^18, откуда и получается оценка
        → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Бывают ещё решения, в которых просто ограничена сумма цифр.

      На самом деле она получается не больше девяти, но доказать это я так сразу не берусь.
      → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      что-то для меня не очевидно, почему все цифры меньше 4, можно намекнуть?)
      P.S. на раунд попасть не смог, но решение задачи возникло такое: за 5 минут процессорного времени генерится объявление массива (около 65 Кб) из "хороших чисел", а конечный ответ такой:
      const uint64_t ans = std::upper_bound(a, a + n, high) - std::upper_bound(a, a + n, low - 1);
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Потому, что нам на самом деле надо, чтобы при умножении столбиком не было нигде переполнения
        → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В SRM'е не участвовал, а в дорешивании сдал тупой перебор всех чисел с десятью цифрами от 0 до 3. Ну а то, что там цифры не больше 3 понял, просто перебрав первые несколько тысяч чисел.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я поинтересовался такими числами. В базе данных последовательностей они называются Skinny numbers. Явной формулы нету, поэтому перебор наверно является единственным решением.

    Однако есть некоторые свойства, в принципе, которые несложно доказать:

    1. Все цифры 0,1,2,3
    2. Не может содержать двух троек.
    3. Не могут присутствовать одновременно 2 и 3.

    Но это число для теоретического интереса.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Там в каждом RabbitNumber-e цифры от 0 до 3-х.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
спасибо.
→ Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Я чуток модифицировал своё ночное решение по 550 и получилось что по времени O(N2 / L) , по памяти O(N). Непонятно зачем тогда ограничение на L ≤ 10
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня такое решение было сразу. А как можно в принципе воспользоваться ограничениями на L?
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А можно по подробнее идею, если не трудно конечно. Просто что-то никак не могу придумать.
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Два параметра динамики: c и n. d[c][n] - количество последовательностей которые сокращаются и оставляют n%L шариков одного цвета, c это число возможных цветов первого шарика, 3 или 4.
      Пересчитывается просто: если n%L=1 то d[c][n] = d[c][n-1]*c; (ставим новый шарик какого-то из c цветов), иначе перебираем когда был последний шарик такого же цвета который мы сейчас поставим, пусть он был на позиции m , значит между позицией m и n все должно сократиться, то есть (n-m-1)%L=0, а вариантов заполнить этот промежуток d[3][n-m-1], значит d[c][n] надо увеличить на d[c][m] * d[3][n-m-1].
      → Ответить
14 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Пустой комментарий.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
"Я чуток модифицировал своё ночное решение по 550 и получилось что по времени O(N2 / L) , по памяти O(N). Непонятно зачем тогда ограничение на L ≤ 10"
При нажатии кнопки влево на правке комментария "Пустой комментарий.", первое сообщение превращается в
"Я чуток модифицировал своё ночное решение по 550 и получилось что по времени Вру. По времени O(N2 / L) , по памяти O(N). Непонятно зачем тогда ограничение на L ≤ 10"
Так случается в мозилле и хроме, по крайней мере.
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ответить
→ Ответить