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

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

Сегодня, 12 января, в 21:00 по Московскому времени состоится TopCoder Single Round Match 566
Посмотреть время в вашем регионе
Всем удачи и успешных взломов! ^__^

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

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

У меня одного арена не грузится?

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

    У меня все отлично работает.

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

    У меня нормально. Возможно тебе надо ее перекачать, если ты давно не писал (они ее обновляли).

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

      Я прямо с сайта запускал... Уже залогинился, вопрос снят.

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

Похоже RAD стал первым таргетом из Саратова. Congratulations!!!

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

Пришло письмо об очередном SRMе... Остались двойственные впечатления от прикрепленного видео:)

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

Random факт: предыдущий SRM, где никем не была решена 3я задача в обоих дивизионах сразу был SRM 406, прошедший 17 июня 2008 года.

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

    А ведь хард то совсем несложный. По модулю тупейшей ошибки (+= вместо |= в проверке цветов) у меня все было готово через 3 минуты после окончания кодинг фазы, а я сегодня очень сильно тупил

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

Как 500 решать-то?

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

    Там вроде симметричные матрицы получаются поэтому их можно за O(n^2) перемножать. Правда я не понимаю почему ограничения 350. Upd: симметричные в смысле каждая строка получается циклическим сдвигом предыдущей.

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

      Заметим, что от чисел нам важны лишь их остатки по модулю N. Поэтому, считаем сначала простую динамику D[i][j] — сколько способов добраться в состояние j (т.е. сдвинуться на j шагов из какой-либо позиции), используя числа 1, ..., i. С ее помощью мы знаем значения для полного периода из N шагов; теперь по целым периодам делаем возведение в степень (склеиваем две динамики за квадрат: C[i] — сумма по всем j A[j] * B[i - j]), а остаток набираем с помощью склеивания и той же простой динамики.

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

      По сути перемножаются не матрицы, а многочлены.

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

      С такими ограничениями люди могли пытаться оптимизировать O(N3) * log(d). А если поставить 1000, то там уже без шансов и никто бы не сабмитил ТЛ-ящие решения.

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

        Надо сказать что и при 350 (N^2)*log(d) работает довольно долго, у меня 0,7s, конечно, можно было писать намного аккуратнее и работало бы раз в 10 быстрее, но это все же не стиль TC.

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

      А как перемножать симметричные матрицы за O(N^2)?

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

        Там важно не то, что они симметричные, а то то что циклические (следующая строка — сдвиг на 1 вправо предыдущей тут ) и произведение двух таких матриц — снова циклическая матрица

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

          А, понятно. Я раунд-то не писал, а как перемножать именно симметричные, без всяких дополнительных свойств, матрицы, я не знаю (и мне кажется, что это нельзя сделать быстро)

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

        Дело не в симметричности, а в том, что на всех диагоналях там стояло одно значение. Типа a[i][j] = a[i + t][j + t]. Такие матрицы правда можно перемножать за квадрат. Достаточно вычислить первую строку результата и записать ее в другие строки результата, циклически проворачивая.

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

      У меня O(N^3) чистый на Java не заходил. Чтобы он зашел, нужно было похачить константу, например в перемножении матриц, модуль брать не каждый раз, а накапливать long до предела и только тогда брать модуль. Дело было уже в самом конце, и я до этого не дошел.

      Это мне скрасило впечатление от всего SRMa.

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

        А как тут O(N^3) сделать?

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

          Можно остаток считать не за квадрат, а за куб, перемножив O(N) матриц, при этом делая каждое умножение за квадрат.

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

            Можно поподробней? Если у нас уже есть матрица для блока длины n, как учесть, что этот блок входит раз?

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

              У меня было следующее. Одномерный массив показывал сколько есть способов добраться из 0 города в x-ый. И была одна функция (N^2), которая к одному массиву, применяла другой, по сути складывая длину маршрута. С помощью этой функции я и делал с помощью них период, но поскольку мне было лень писать новые функции, я и начальный массив для длины n считал прибавляя по очереди n массивов вида (a[i] = 1, a[N-i] = 1, a[всё остальное] = 0). Отсюда и N^3, но почти ничего не писать дополнительно и до кучи, после одной из таких итераций мы автоматом получим и массив остатка.

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

                т. е. вы эту задачу умеете решать для d = 10100 ?

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

                  Нет, извиняюсь, конечно имеется ввиду разница между O(N^2 + log D * N^2) и O(N^3 + log D * N^2). То есть логарифм никуда не девается, но доминирующей частью если пренебречь эффективностью в первой части становится N^3 (при данных ограничениях).

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

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

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

Div1-500 is pretty much the same as problem C from NEERC 2006/2007:http://neerc.ifmo.ru/past/2006/problems/problems.pdf

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

Скринкаст: http://youtu.be/1lRsTXK2wbM?hd=1

Особенно удались последние 10 минут кодинга — тупое всматривание в код харда в поисках баги, потому что не проходит последний сэмпл, а баги в итоге не было. В итоге оказалось, что я не заметил в условии, что в каждом загоне должен быть хотя бы один пингвин.