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

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

Сабж. Можно порешать с 11 до 16. http://www.rsatu.ru/acm/

Любителям Java: внешний класс будет переименован!

Тут же наверное можно будет и обсудить контест.

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

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

У жюри в этом году есть решения на Яве, Яве установлен стек в 64мб, GCC и VSC++ добавлен O2. Сказали, что задачи решаемые :-) Как всегда с нетерпением ждём поста Alex_KPR .

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

    Всем хорошо поиграть, кстати. :)

    P.S.: Глядишь твою разморозку на онсайте увидим. :)

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

    VSC++ добавлен O2

    ОМГ, раньше не было что ли?

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

      В том году в интернет-туре у тренеров один и тот же код тллился на студии и заходил на гцц и борланде. Видимо да.

      А может на гцц тллился...

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

        Интересно, там хоть кто-нибудь будет решения на Visual C++ отправлять?..

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

          Наши вроде будут. Хотя может и на гцц, как у вас обычно делали.

          А что?

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

            Какой-то он ущербный, ИМХО.

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

              Он на -O2 стабильней работает, например.

              Да и вообще писать в студии, а засылать под gcc грешновато.

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

    Свежо предание про стек на Java — рекурсия с 2 интовыми параметрами и 2 интовыми переменными с макс глубиной 10000 дает StackOverflow

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

    боюсь, что от меня поста не будет — я не присутствовал на турнире :(

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

Где я?

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

Кто решил X?

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

Составы: http://acm.math.spbu.ru/~snark/neercs/index.cgi?data=macros/regstat&year=2012&qf=central&class=central2012&text=Central%20QF
Любопытно, что за Липецк играют какие-то вьетнамцы :)

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

А после 15:00 заморозилась очередь? А то хотелось бы результат хотя бы своей посылки узнать...

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

А почему H за O(M*K) по TL не проходит, неужели там настолько медленный сервер? Это же всего 25500000 операций, на моем компе 200мс работает.

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

    У меня прошло.

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

      на GCC?

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

        Да, на GCC.

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

          я так думаю, что это из-за чтения или вывода. но я 6 посылок сделал, как только не пробовал читать. ты как читал? вот мой сол, вроде бы все верно: http://pastebin.com/n7CngiMC

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

            У меня был стандартный ввод/вывод через cin/cout. В остальном примерно то же самое. (Решение не сохранил)

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

            А можно увидеть условие и ограничения?

            По коду появилась версия, что проблема в том, как идёт итерирование по массиву s[][] в последнем цикле. Там, по идее, во вложенном цикле будут постоянные кэш-промахи, вызывающие пичальку, тормозя выполнение программы в разы.

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

              Дан массив из N элементов ( 1<=a[i]<=255). Нужно отвечать на запрос: сколько различных элементов на отрезке [l,r]. Всего K <= 100000 запросов.

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

              кстати это идея, может стоило порядок индексирования в массиве поменять. но теперь уже не проверить.

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

                Склоняюсь к тому, что в этом-то и проблема.

                Дано: статический массив размера 256 × 10005.

                А далее, в последнем цикле, в общей сложности может выполняться порядка 25500000 запросов к ячейкам массива, причём обращение к ячейкам в одной строке бывает не чаще, чем раз на примерно 255 раз (в худшем случае). Получается, на каждой итерации мы перескакиваем обращением на другой кусок из 10005.

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

Отчего-то там до сих пор нет результатов.
Зато они есть у снарка :)

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

-А скиньте кто-нибудь куда-нибудь условия, хочу тренировку на CF залить-

UPD. Уже раздобыл...

UPD2. Напишу сюда, чтобы не поднимать темы. Если кто-то очень ждет контестов, то там чекеры юзают странную библиотеку. Я написал в РГАТА, чтобы они мне ее прислали, как только пришлют, так сразу залью контест.

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

Написали виртуальный контест. Остался только один вопрос.

В F написали решение, для которого не умеем доказывать, что оно получит числа до 10^9. Забиваем на ограничение, что числа должны возрастать, решаем задачу независимо по каждому из простых. Получили какой-то ответ. Начинаем его лечить следующим образом: идём слева направо, и каждое число Ci, которое меньше предыдущего Ci - 1, домножаем на некоторое k так, чтобы все gcd-шки не поменялись. Это k перебираем от int(C[i-1] / C[i]) + 1 вверх, пока не найдём подходящее (каждый вариант проверяем за O(n), пересчитывая gcd-шки). Локально не смогли найти теста, на котором такое решение выдало бы числа, большие 10^9, но совершенно неясно, почему такого теста нет. Оно прошло на ОК.

Возникает вопрос: такое решение есть? Какое авторское решение? Или задача с дохлыми тестами?

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

    Да. Такое и было решение.

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

      Так ёлки-палки, как доказать корректность решения-то?

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

        Мы тоже интересовались, но автор утверждал, что тест такой не подобрать.

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

          "А у нас таких тестов не было!"

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

          Тест:


          10 1 4 1 1 1 1 1 2 1 9 1 1 1 1 1 1 9 1 1 1 1 1 2 9 1 1 1 1 1 1 1 1 71 1 1 1 2251 1 1 6257 1 1 1 1 1

          Он соответствует последовательности [4, 9, 36, 41, 71, 2251, 6257, 999999997, 999999998, 999999999].

          Автору а-та-та за такие задачи, где авторское решение не всегда находит ответ.

          Авторство теста принадлежит Fedyarer.

          UPD: А, sankear был быстрее. Но у нас тест меньше :-)