Блог пользователя ivan.popelyshev

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

Соревнование начнётся в 21 июля в 20:10 по саратовскому

Да пребудет с нами Сила!

[Ads mode on] Нечего делать перед матчем? Не забываем про бомбер [Ads mode off]

UPD. Поздравляю Петю и Гену! :)

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

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

После поста про коллизии хешей начали возникать коллизии среди анонсов про SRM >_< пусть остается этот пост, тут есть котэ)

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

По такому поводу будет три 550-ых задачи?

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

только у меня время в арене неверное?

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

    Они же уже разослали, что знают и фиксят.

    UPD. Отлично пофиксили!

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

      Спасибо.

      Ничего не приходило.

      UPD: Вижу теперь

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

      А что-таки произошло? На сайте ничего нет.

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

        Время топкодера стало на 5 часов меньше реального.
        Для фикса вместо того, чтобы поправить время, сделали старт контеста на 5 часов раньше.

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

          Э, то есть он уже прошел? o_O

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

            Нет. реально он будет в тоже время. Просто время на TC не совпадает с реальным.

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

            Ну из-за того, что время в арене всё ещё на 5 часов отстаёт -- всё будет как запланировано (в 20:10 Саратова)

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

Привет всем. Это будет мой первый контест на топкодере. И я, честно говоря, не совсем разобрался что там да как. Если кому не сложно, пожалуйста, опишите вкратце то, как проходят там контесты.

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

Я понял)

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

Как решать 850?

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

    Вычисляем мин. стоимость, проверяем что maxCost на неё хватает, смотрим сколько раз можно ещё сделать цикл a->b->c->a , пусть минимальное число ходов это moves, и можно сделать cycles циклов.

    От текущего слова нам нужно три параметра: сколько букв совпало, скольким нужна одна замена, скольким две. Итого состояний порядка N2т.к. их сумма это N.

    Когда мы делаем замену, состояние меняется линейно. Берём соответствующую матрицу, добавляем туда строчку куда будем писать сумму для состояния (N, 0, 0), возводим в степень moves+cycles+1 и смотрим в клеточку соотв переходу из начального состояния в сумму, там будет ответ.

    Осторожнее, сумма costi и минимальная стоимость может вылезти за int.

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

Жадность фраера сгубила.

Расскажите, как третью делать? Свёл к умножению многочленов длины 10^9 / 3, узнал, у какой функции ряд Тейлора , но так задачу и не решил. В решении чувака из моей комнаты, которое я не смог завалить, было какое-то двоичное масштабирование.

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

УГ раунд.

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

    А мне норм.

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

      Ну как, первая — ничем не примечательная реализация, вторая — "или ты увидишь C(n, k) и знаешь как его быстро считать по модулю два, или нет", а вот третья вызывает интерес.

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

        Эм, расскажи про цешку? Решал как-то кажется совсем по-другому

        Упс, допер идею, ок.

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

          У тебя получился красивенький фрактал. После некоторого афинного преобразования (кажется, прямую y=x надо перевести в прямую x = 0) получится треугольник серпинского, или, что то же самое, в точке (x, y). А дальше магия: C(n, k) чётно тогда и только тогда, когда (k | n) == n.

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

            Ага, спасибо. не заметил сходу Cшки, проверял шаманской рекурсией)

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

        Когда я решал вторую то я не заметил связь с Cnk). Просто понял что это фрактальчик. Хотя да, по формуле она сразу видна.

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

    Автор математик. 300 — реализация как реализация. Туповатая слегка, но вполне жизнеспособная. А дальше надо думать. Тут это почему-то не любят. Хотя давать 500-ку на "либо ты умеешь проверять Сшку на четность магическим выражением (n&k) == k либо убиваешься любым доступным тебе способом это действительно не очень хорошо.

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

      Вау, а я всегда делал это рекурсивно по треугольнику Серпинского за логарифм.

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

        Офигеть, эта штука еще как-то называется! Я когда вывел правильные формулы, время уже кончилось...

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

        Кстати, треугольник Серпинского за логарифм хорош тем, что обобщается на произвольный модуль вместо двойки. Вот даже задача об этом http://projecteuler.net/problem=148 .

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

          Я хоть и подозревал, что простая формула за О(1) должна следовать из теоремы Люка, но на контесте кодил за логарифм методом, который всегда использовал. Возможно, это и есть решение по треугольнику Серпинского.

          Идея состоит в том, чтобы найти степень вхождения в числитель и знаменатель формулы подсчета C(N, K). Если степени равны, то оно не делится на 2, иначе — делится. А проверить степень вхождения числа p в N! можно одним циклом:

          while (n /= p) ans += n;
          
    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      А можно, в таком случае, объяснить решение 500?

      UPD: Спасибо

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

        Можно.
        0. Клетки с нечетным (x+y) и x < y пустые. Это очевидно из формул.
        1. Оставвшиеся клетки представляют собой треугольник. У клетки есть две предыдущих — как раз описанные в условии.
        2. Клетка либо пустая, либо ее цвет зависит от чего-то вроде .
        3. Из формул в клетке записан ксор предков. Что тоже самое .
        4. По простому модулю цешка равна произведению цешек по разрядам в p-ичной системе счисления. Это проверяется явным вычислением. По модулю 2, это значит, что она 1, только когда все биты в k не больше чем соответствующие в n. Что тоже самое (n&k) == k.

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

          Спасибо!

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

          Не совсем понятен пункт 3. Почему ксор понятно, но откуда берётся переход к C((x+y)/2, y). Можете обьяснить?

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

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

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +9 Проголосовать: не нравится
            1. В момент t заполняются только клетки x+y = t*2 , доказывать индукцией.
            2. Приняв 1. за правило можно считать что все фишки одного цвета.
            3. если D[x][y] = 1 если в x,y есть фишка, то условие состоит в следующем: D[x][y] = (D[x-2][y] + D[x-1][y-1]) mod 2
            4. оно очень похоже на C[n][m] = C[n-1][m-1] + C[n-1][m]
            5. делаем очевидную замену, получаем эти C-шки.
            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Вот! То что надо. Теперь понятно, спасибо.

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

      Из комментариев, в общем, видно, что это далеко не единственное решение 500-й. Можно уметь узнавать и считать , можно просто по картинке рекурсию делать, можно, наверное, погуглить треугольник...

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

        Я это и назвал убиться любым доступным тебе способом. Это все представляет собой в той или иной форме проверку остатка цешки.

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

          Ну не знаю... я гораздо больше очков слил на ресабмит int -> int64 в одном месте, чем на придумывание этой рекурсии. А красивую формулу за O(1) только в этом обсуждении узнал.

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

            Я хотел на зимние сборы это дать. Мне сказали что баян :)

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

Не понравилось, что третья задача была 850 (первый раз вы жизни вижу на ТС, чтобы третья задача стоила меньше 900) — то есть, очень простая для третьей. А реально она по сложности была не проще обычных.

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

Сейчас это сообщение заминусуют. Я снова челленджил, перепечатывая код. Действительно очень удобно. Сегодня успел просмотреть 2 решения по первой задаче. Одно зачелленджил тестом {1,1,2,2,3}, второе упало на сэмплах, поэтому я начал еще раз проверять код, и время кончилось. В общем, это и вправду выгодная тактика.

Забавно, вчера было -12, сегодня уже +10...

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

И очередной слив: http://www.youtube.com/watch?v=6OagOnDW7F0&hd=1