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

TCO 2011: Qualification Round 2
Автор goryinyich, 14 лет назад, По-русски

Всем привет!


Кто писал, или просто смотрел задачи - у меня 2 вопроса:

(Кто хочет посмотреть - вот ссылки:

1. Какой самый плохой тест для второй? У меня 10000 шагов пересчета возможных позиций на всем поле улетели. Какой тест дает больше? (UPD: упал на тесте ".CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.", 50, 49 дает в ответе 29401, обидно)
2. Как просто решить третью? Я придумал алгоритм, но не очень простой. А там ее даже синие сдавали. Либо я недооцениваю синих, либо может быть есть относительно простое решение задачи?

Спасибо!
  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 3   Проголосовать: нравится +9 Проголосовать: не нравится

d(n) - это остаток от деления n на 9, если n не кратно 9, и 9 иначе.
Получаем систему соотношений вида j * (9 * k + j % 9) = x, j = 1...9.
То есть х  = bj  (mod aj) для некоторых  aj и bj .
Можно заметить, например, что все aj делят число m = 5 * 7 * 8 * 9 * 9.
Это значит, что по остатку от деления числа на m мы можем однозначно установить, подходят нам числа с таким остатком или нет. Осталось пробежаться от 0 до m - 1 и проверить каждый остаток на пригодность.

→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Спасибо, действительно проще, чем я придумал с включением-исключением
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а как Вы думали с включением-исключением ?
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Довольно стандартно. Классы чисел имеют вид (9i+1)*1, (9i+2)*2, ..., (9i+9)*9. Сначала складываем кол-во чисел в каждом классе (найти легко), потом вычитаем кол-ва, которые в двух классах, прибавляем - которые в трех и т.д. Можно заметить (по остаткам от деления на 9), что лишь немногие классы пересекаются (либо по 2, и только с остатком 0 - 3 класса), я вручную выписал формулы и начал их забивать. Немного не успел. Решение, которое описал awanim, конечно, намного изящнее.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          В принципе формула там не очень большая. У меня получилось 7 слагаемых на включение (для 1, 2, 3, 4, 5, 7, 9) и 2 на исключение (для 4x5 и 2x7). А конкретные коэффициенты у слагаемых можно было быстро вывести перебором.
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не очень понял, почему 7. 9 классов - 9 слагаемых на включение (класс 6, например, не является подклассом класса 3, как может показаться), у классов 1 и 8, 2 и 7, 4 и 5 есть пересечения, кроме того, пересекаются классы 3, 6 и 9 - нужно искать сразу пересечение трех
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              9 не пересекается с 3 и 6, т. к. все числа класса 9 делятся на 81, а 3 и 6 нет. Кроме того, класс 3 включает класс 6. Аналогично, класс 1 включает класс 8. Остается только то, что я написал в предыдущем посте.
              → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как подсказывают тесты, для такого примера

".CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC..", 50, 49

ответ 29402.

В принципе понятно, что можно оценить ответ сверху как N * lcm(K, C) <= 50 * 49 * 50, и это зашло бы по времени.

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

Во второй еще можно было Дейкстру за MlogN писать,где каждая вершина определяется номером ячейки и двумя остатками от деления  на K,C.
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится
    Достаточно обхода в ширину: ребра невзвешенные.
    → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Да, я тоже поставил 10000+ шагов и обломался с попаданием в десятку =(
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    А я чёта оборзел, просто поставил проверку в цикле - если уже > 1.9 секунд всё никак не родится ответ, то return -1.
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, с 10000 обидно (
    Перед отправкой добавил 0 и сразу убрал - зачем лишний раз программу гонять )
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    я тоже чуть было не поставил 10000, но потом подумал 5*10^6 проходит, почему бы не поставить 10^5 и хорошо что так и сделал
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Правильно, я уже тоже решил, что в следующий раз так и сделаю.
      → Ответить
      • 14 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        И всё равно ведь можете нарваться, потому что в другой раз задача может так не решаться. Здесь вот, например, проходил BFS по 503 состояний - 50 на размер массива, ещё квадрат - на время по модулю K * C (а значение - время без модуля). У меня, если что, тоже упало, но по другой причине - за каким-то лешим догадался брать время для параметра по модулю N * K * C, а увидев, что очередь такого объёма (504) в память не помещается, сделал отсечение, чтобы рассматривалось только порядка 503.
        P.S. Кстати, я одного свалил именно на том, что он решал итерациями, но поставил их мало.
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Гм, если делать память 504 то локально у меня не запускается, но если сабмитить в арену, там отлычно все проходит. Не подскажете почему так ? Как сделать чтобы локально все было хорошо ?
          → Ответить
          • 14 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

            Ну, строго говоря, у меня не проходило в "Арене" не 504, а 644. А как именно у Вас "не запускается", что конкретно происходит? А ещё сбросьте тогда на всякий случай код сюда и скажите, каким компилятором и с какими ключами Вы его локально собираете.

            P.S. И незачем так ОРАТЬ :)
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Программа просто вилетает. Такое впечетление что нехватает памяти.
              Пользуюсь gcc 4.4.1, ключи -s -O2
              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Вот я попробовал собрать под MSVS 2008 - вроде нормально работает. Насколько я знаю (гарантировать не могу, пусть подтвердят те, кто юзает gcc), стек под g++ растягивается не директивой прагме (она просто игнорируется), а как-то хитрее.
                → Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
off-top
у всех календарь на http://topcoder-calendar.appspot.com/ поломался?
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

я во время контеста тупил с 500, и даже не прочел 1000. 1000 оказалась для меня очень простой, заметим что d(n) = 1 + (n - 1) % 9 я это давно знаю, с какой-то задачки помню. f(x) = 1 если x представимо, f(x) = 0 иначе. последовательность f(1), f(2) .... f(n) циклична, это как-то интуитивно чувствуется, безо всяких вычислений. построим 100 000 первых членов в лоб, найдем длину цикла опять влоб. 100 000 в квадрате, но там обламывается почти сразу, если длину цикла неугадали поэтому все это работает 30 мс. ну а теперь зная длину цикла K и начальные K членов последовательности не сложно научиться считать количество еденичек на интервале [1..n]

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

    Такой интуиции можно позавидовать. Мне вот только очевидно, что циклично идут те n, которые представимы как yd(y) с каким-то одним d(y), соответственно там, казалось бы, должно быть несколько циклов, которые местами-временами ещё и пересекаются. Но Вы утверждаете, что цикл на самом деле один? И как это всё-таки доказать?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, если есть несколько циклов, то их LCM один цикл.
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну, это в некотором смысле да, но как это относится к вопросу? :)
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          У нас есть несколько циклических последовательностей, они все объединяются в одну, операцией "или". В худшем случае длина общего цикла равна произведению длин всех циклов. Это же тебе было очевидно в задаче 500? что K * C * n это общее число состояний, в которых чувак может находиться.

          Очевидно также что если сливать два цикла длин A и B и B % A = 0, то длина общего цикла будет B.

          Про LCM тоже понятно, это как китайская теорема об остатках. всего может быть не более LCM(m1, m2, .. mn) решений системы уравнений.

          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            а да, вообще говоря про LCM не так очевидно, но мне уже хватило того что цикл существует, чтобы попытаться найти его длину.
            → Ответить
          • 14 лет назад, # ^ |
            ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Мы, видимо, о разных "циклах" говорим. Вот смотри, для d(y) = 2 последовательность таких x, что yd(y) = x, выглядит так:
            4, 22, 40, 76, ...
            А для d(y) = 3 - так:
            9, 36, 63, 90, ...
            И как же эти две последовательности слить в одну с периодом? Или, может быть (такую возможность я тоже допускаю), в последовательность с одним периодом они сливаются не попарно, а только для (почти) всех возможных d(y) сразу?
            → Ответить
            • 14 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              рассмотрим последовательность f1, f1(x) равно 1, если существует y, такое что d(y) = 1 и d(y) * y = x
              рассмотрим последовательность f2, f2(x) равно 1, если существует y, такое что d(y) = 2 и d(y) * y = x
              рассмотрим последовательность f3, f2(x) равно 1, если существует y, такое что d(y) = 3 и d(y) * y = x
              ...
              все эти последовательности состоят из 0 и 1, и все цикличны.
              теперь объеденим их в общую последовательность f, f[x] = f1[x] or f2[x] or f3[x] ...
              она тоже циклична, смотри пояснения выше
              → Ответить
              • 14 лет назад, # ^ |
                ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                Ну замечательно, для d(y) = 1 последовательность выглядит так: 1, 10, 19, 28, .... Объединяем с двойкой и тройкой, получаем: 1, 4, 9, 10, 19, 22, 28, 36, ....
                Где цикличность, где??? В упор не вижу. Но, что самое страшное, ты говоришь, что сдал задачу, значит ты прав. Видимо, я в этой жизни чего-то очень сильно не понимаю :-X
                → Ответить
                • 14 лет назад, # ^ |
                  ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  http://www.everfall.com/paste/id.php?zsjlp85c5wbq
                  → Ответить
                  • 14 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Ну вооот, теперь понятно - как я и сказал, мы говорили о разных циклах. Ну а ты-то понял, что я имел в виду?
                    → Ответить
                    • 14 лет назад, # ^ |
                      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                      нет, в самом первом посте я определил последовательность как последовательность из 0 и 1, f(x) = 1 если x представимо
                      → Ответить
                  • 14 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    я посмотрел код и мне стало интересно другое: функция ASS(0) гарантированно крэшит программу в любой жизненной ситуации?
                    → Ответить
                    • 14 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      Должна бы, с таким-то названием...
                      → Ответить
                      • 14 лет назад, # ^ |
                          Проголосовать: нравится 0 Проголосовать: не нравится
                        ========================
                        не, ну я просто не очень осознаю, как именно она крэшит =)

                        очень полезная вещь на самом деле, я обычно оставляю "while(true);", но так можно перепутать ассерт с таймлимитом
                        → Ответить
                        • 14 лет назад, # ^ |
                            Проголосовать: нравится +5 Проголосовать: не нравится
                          обращение к элементу памяти с адресом ноль на чтение и на запись, конечно вылет будет. а вот ТЛ не имеет side effects по мнению оптимизирующего компайлера, и он его оптимиздит
                          → Ответить
                          • 14 лет назад, # ^ |
                              Проголосовать: нравится 0 Проголосовать: не нравится
                            "оптимиздит" - слово-то какое =)

                            спасибо за разъяснение :)
                            → Ответить
                    • 14 лет назад, # ^ |
                        Проголосовать: нравится +5 Проголосовать: не нравится
                      наверное да, хотя был тут случай бага компилятора оптимизирующего, обещали поправить. название от слова assert, а не то что вы подумали.
                      → Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

по первой задаче

одни делали 2 подсчётами ,

вторые сжиганием свечки с двух сторон(like while(l<r){while(f(l))l++;while(g(r))r--; dosome;})

кто нить делал за один проход ? (like for(i=0;i<somefunc;i++){dosome2})

→ Ответить