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

Всем привет!

Сегодня состоится второй раунд Всероссийского Открытого Чемпионата по программированию "КРОК-2013". Раунд для вас готовили: sdya, Seyaua, Gerald и, как обычно, задачи на английский переводила Delinur.

Приятная новость для тех, кто не попал в лучшие 400 участников в предыдущем раунде — сегодня каждый может поучаствовать вне конкурса. При этом, раунд будет рейтинговым как для официальных участников чемпионата, так и для внеконкурсных.

Официальным участникам напоминаем, что:

  • Все участники чемпионата должны быть не моложе 18 лет на момент регистрации
  • Финал чемпионата состоится 16 и 17 мая в Москве в офисе компании КРОК (50 участников)
  • Проживание во время финала будет оплачено компанией КРОК
  • Для граждан Российской Федерации: организаторы покроют транспортные расходы по территории РФ, транспортные расходы не по территории РФ — по согласованию (возможно, частично)
  • Финалисты должны подтвердить свое участие до 2 мая

И небольшой бонус: лучшие 200 официальных участников чемпионата получат футболки!

Желаем всем получить удовольствие от решения задач ну и, конечно, удачи!

UPD: Разбалловка по задачам сегодня будет немножко отличаться от стандартной: 500-1500-1500-2000-2500 для первого дивизиона и 500-1000-1500-2500-2500 для второго.

UPD2: Мы приносим свои извинения за технические неполадки во время раунда. Посовещавшись, мы решили, что соревнование должно быть рейтинговым. А результаты соревнования будут учитываться в отборе на финал чемпионата КРОК.

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

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

А на какой раунд регистрироваться официальным участникам чемпионата из Div. 2?

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

    Очевидно, на официальный.

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

      Очевидно, вопрос задан не просто так. "Рейтинг должен быть от 1,700 до 9,999 для возможности регистрации на это соревнование"

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

    В официальный. Сейчас регистрация на него открыта для всех прошедших.

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

А на аватарках у sdya и Seyaua кто — sdya или Seyaua?

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

I'm assuming div2 people who qualified to Round 2 should participate in the non-Div2 round?

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

In last 3 raunds I've lost 204 points of rating, may I find some luck in this contest ))))

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

It's good that there is division 2 too

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

It's good news that participants from div 2 can participate in this contest ))))

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

I pray for irakli_p to increase his rating this time.

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

"A little bonus: top 200 official Championship contestants will receive t-shirts!" why only official ? give top 200 contestants from both official and unofficial.

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

Я зарегистрировался на контест. Но в разделе соревнование вместо зелёной надписи "зарегистрирован", красная надпись предлагает "зарегистрироваться". Видимо это ненормально.

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

В див2 будут такие же задачи?

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

    Скорее первые 3 задачи с Div.1 будут совпадать с последними тремя задачами Div.2, по крайней мере в прошлом году было так :)

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

    Думаю задачи будут одинаковые, но ограничения разные.

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

Баг: я зарегистрировался на контест вне конкурса, но красная кнопка "Зарегистрироваться" у меня не пропала.

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

Почему по ссылке "КРОК-2013" открывается блог из двух постов? Почему туда не добавили посты о первом и втором отборочных раундах?

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

Ну я как всегда опоздал на регистрацию на целую минуту.

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

У меня одного КФ глючил?))))

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

КРУТОЙ РАУНД. Спасибо авторам!

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

Спасибо за красивые задачи, очень понравились. К сожалению, они мне оказались не под силу :'(

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

Как решать B, C?

Upd: у меня в B работал перебор за 3 секунды для теста

5 6 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Насколько я понимаю, это макс. тест. Мне это должно намекать на то, что я его чуть-чуть недооптимизировал или то, что ограничения подобраны настолько хорошо, что перебор не проходит? :)

UpdUpd: уже объяснили, что я не прав.

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

    В C задача сводится к решению уравнения 3(a + b)(a + c)(b + c) = n в целых числах. Можно решить перебрав первый множитель за

    UPD: Ну если n не делится на 3, то решения сразу нет)

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

      Вот как это можно было заметить, не прибегая к wolframalpha и прочим читерствам? Я минут 30 на бумаге думал, пока наконец не сдался и не пошёл в wolframaplha...

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

        Ну я, например, на бумажке раскладывал. Применяешь формулу суммы кубов к a3 + b3 и разности кубов к (a + b + c)3 - c3, а дальше (a + b) выносится и там уже просто.

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

        Участвовать в школе в олимпиадах по математике :P
        Там это заучивается на уровне подкорки, что и через 10 лет на автомате раскладываешь такое на множители в уме.

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

          Я участвовал в школьных олимпиадах по математике :) Значит, либо фигово участвовал, либо в России олимпиады какие-то другие, либо моя подкорка умеет забывать за 7 лет.

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

          Я участвовал, но на контесте пришлось заново придумать =)

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

        Ну, я, судя по-всему, уже видел это разложение, потому что оно у меня сразу написалось на бумажке. А так — ну, скорее всего надо на множители разложить. Так, у нас общий делитель 3 — выносим. Так, у нас сумма коэфициентов 8 — значит, 2 * 2 * 2. Ну а симметричных 2 * 2 * 2 не очень много

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

        Я вот как-то заметил. С помощью простого текстового редактора. Без WolframAlpha и даже без бумажки.

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

          Ну я прекрасно понимаю, что есть полно людей, которым ещё и не такое очевидно :) Просто посдавали задачу на порядок больше, чем можно было бы ожидать, если бы её сдали только такие повелители.

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

            Ну в мат. центре спб такое детям в 8 классе объясняют (то есть чуть ли не самый боянистый симметрический полином). Например, на идею подставить a=-b и увидеть ноль (делимость на (a+b)).

            А еще есть хорошая (не самая простая) задачка: докажите, что (a + b + c)333 - a333 - b333 - c333 делится на 3(a + b)(b + c)(a + c) (для натуральных a, b, c).

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

              в кольцо многочленов по модулю простых множителей очевидно, по модулю 3 цэшки все поделятся

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

        удалила дубль.

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

        Можно в лоб раскрыть (a + b + c)3, после множества сокращений, вынося степени C, получаем 3 * (a + b) * (c2 + (a + b) * c + a * b) = n. Ещё один шаг и получаем искомую формулу. Хотя задачу я все равно сдать не успел.

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

        Если попробовать составить квадратное уравнение относительно a, это сразу получится.

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

        Я делал так (на бумажке). Если раскрыть скобки, у нас останется 24 слагаемых (27 минус a3, b3 и c3). Вынесем множитель 3, осталось 8 слагаемых. Теперь предположим, что многочлен третьей степени факторизуется, и при раскрытии скобок этой факторизации ничего не сокращается. Тогда сколько должно быть скобок и сколько слагаемых в каждой скобке? Довольно логично попробовать 8 = 2·2·2, то есть три скобки по два слагаемых. В силу симметрии остаётся проверить один вариант, он подходит.

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

          Да, под восемью слагаемыми я имею в виду a2b + ab2 + b2c + bc2 + c2a + ca2 + 2abc: последнее, естественно, с учётом кратности.

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

    По С превращаем Вот так, далее вроде бы должен работать перебор, если достаточно хорошо его пообрезать со всех сторон. Я перебирал значение первой скобки (понятно, что это делитель n/3, и не больше корня кубического из n/3), и внутри — значение а и b. Если зафиксировать а и b, и перейти к t=n/(a+b)/3, то получим (a+c)*(b+c)=t;

    Тут делаем еще одну замену, x=a+c; получаем квадратное уравнение x*(x+b-a)=t;

    Дальше вроде бы очевидно.

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

    В задаче B динамика с использованием бит-масок, если я конечно не ошибаюсь.

    DP[номер текущей строки][номер текущего столбца][маска уже имеющихся цветов]

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

      А переходы откуда? В смысле, из каких состояний?

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

        Перебираем каждую маску и цвета(если текущая клетка не закрашена), если цвета в наборе нет:
        DP[i+1][j][curmask + 1<<color] += DP[i][j][curmask];
        DP[i][j+1][curmask + 1<<color] += DP[i][j][curmask];

        Ну и в конце надо перебрать все возможные маски и цвета клетки n,m и если цвета в маске нет — добавляем DP[n][m][mask] в ответ.

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

          Я это мгновенно закодил на контесте. К сожалению, такое решение неверно. Хотя бы на таком тесте:

          2 2 3
          1 2
          0 0
          

          Получается, что
          dp[0][1][{1,2}] == 1
          dp[1][0][{1,2}] == 1

          Но dp[1][1][{1,2,3}] не равно сумме тех двух значений.

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

          Так мы посчитаем число раскрашенных путей, а не раскрасок

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

      По ML и TL не пройдет

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

    У меня мгновенно работает на этом тесте что-то такое:

    поставим в первую строку и последний столбец числа 1, 2, ..., (n+m-1) Если у нас там были какие-то цвета, то переназначим их. Дальше будем перебирать отсекаясь, если табличка стала неправильной. Для финальной таблички посмотрим, сколько способов переставить цвета.

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

    Я написал такую динамику [x, y, mask] — где стоим и маска 610. Маска означает для каждого цвета минимальный номер строки где этот цвет присутствует. Но это медленно. Дальше я сделал хак, что все цвета не лежащие на поле одинаковы, поэтому можно перебирать только нормализованные наборы и потом домножать на коэффициент. На твоем тесте это даже с mapом работает очень быстро, но если в последнем столбце подобавлять числа, то опять медленно. Nerevar сказал, что он делал то же самое но каким-то образом смог нормализовывать не только числа которых нет в таблице но и все остальные. И это вроде уже быстро работает. Странная задача B, если это ее авторское решение.

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

      У меня очень похоже, только я в качестве оптимизации фиксировал цвета начальной и конечной точки

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

      Я написал такую же динамику, но работала она долго. После долгой медитации придумал такую оптимизацию: все цвета, которые уже не встретятся после текущей позиции, мы сортируем в нашей маске. А для всех цветов, которые встретятся, находим номер самого левого столбца и учитываем его, когда пытаемся поставить этот цвет. С этим отсечением динамика зашла за 15мс.

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

    в B у тебя решение быстрее чем за O(ответ)? для теста

    4 4 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

    ответ (если не брать по модулю, и я нигде не набагал) = 31391539200

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

      У меня на этом тесте вроде такой же ответ

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

      Интересно:) Нет не быстрее, просто я глупый и не подумал, что 5 6 — не макс. тест.

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

    В B отлично заходит перебор, надо только его в k! раз соптимизить. А именно, определим операцию "канонизации" раскраски так: возьмём все цвета, которых не было во входных данных, выпишем поле по строкам и посортим цвета в поряде появления там (т.е. например, если поле начинается как 3989, а неиспользованные цвета все, это превращается в 1232). Посчитаем количество таких полей перебором, для каждого прибавим к ответу количество полей в его классе эквивалентности. Если начальное поле относительно пусто, то это оптимизация в ! раз, а иначе даже тупой перебор быстро работает, т.к. ответ небольшой.

    Upd.: как пишут ниже, это убивается тестом с полем 5x6, у которого часть клеток снизу слева зафиксированы. Так что решение лажа, странно, что оно зашло.

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

      У меня похожий перебор: если пытаюсь раскрасить клетку в цвет, которого еще на поле не стоит — запускаю перебор дальше, и запоминаю ответ. Когда начинаю пытаться покрасить эту же клетку в другой цвет которого так же нет — перебор уже не запускаю, а просто вспоминаю уже подсчитанное значение.

      Эта оптимизация довольно легко прикручивается к самому тупому перебору.

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

      Эммм, не вводите народ в заблуждение недоказанными решениями: (в данном случае, опять слабые систесты). Ваш перебор на таком тесте, допустим, получает заслуженный Time Limit.

      5 6 10
      0 0 0 0 0 0
      0 0 0 0 0 0
      0 0 0 0 0 0
      0 0 0 0 0 0
      1 2 3 0 0 0
      

      На самом деле, я сначала тоже так написал, а потом пришлось ресабмитнуть нормальное решение. Нормальное следующее: нужно встречающиеся цвета, которые уже есть в табличке, сопоставлять цветам шаблона, который перебираем. Так уже очевидно, что дольше всего работает на пустых таблицах. Ну или еще глупее: генерировать цветовые шаблоны для пустой таблицы, а потом уже сопоставлять с исходной, частично заполненной.

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

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

        5 6 10
        0 0 0 0 0 0
        0 0 0 0 0 0
        0 0 0 0 0 0
        4 0 0 0 0 0
        1 2 3 0 0 0
        

        Эх, и люди пишут лажу, и авторы ее не отсекают.

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

          То, что люди пишут лажу это нормально. Обычно на контесте нет времени доказывать количество операций в переборе с отсечениями. А макс тест не очевиден.

          Но насчет слабых систестов согласен. Видимо у авторов не так много фантазии на разные неправильные решения. В отличие от 2к участников.

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

            Да, конечно. В переборе с отсечениями — это нормально (я и сам подобный перебор отправил, пока головой не подумал). Но что забавно: это именно та лажа, которая с большой долей вероятности может прийти в голову (что подтверждает как раз 3-4 TL из Top-50 на этом тесте). То есть я никого не виню, мне, скорее, наоборот интересно, было ли у авторов такое решение.

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

        Ага, верно, на этом тесте (и на указанном ниже) ТЛ (не успевает, правда, всего в константу раз ~2; учитывая, что это джава и bottleneck — обращение к 3хмерным массивам, такое решение на C++ этим уже не убьёшь). А вы пробовали на контесте кого-нибудь челленджить? Если бы авторы добавили такой челлендж к систестам — результаты бы сильно поменялись.

        Вспоминая пост про недоказанные решения — я видимо начал входить во вкус загона фигни. Второй день подряд заходит правдоподобная лажа по довольно сложной задаче =) < trololo > Так вот он, секрет успеха на контестах </ trololo >

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

          Илья, на плюсах — да, этот тест проходят, а вот второй уже нет (уверен, можно и еще убойнее придумать). А загон фигни — это, несомненно, весело и приятно, особенно на ACM-style контестах.

          Кстати, я ни разу на встречал обсуждений про неправильные решения на TC (подскажите, случалось ведь и там такое?)

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

            Ну моё java-решение на 2ом тесте локально работает 3.9с, а учитывая, что bottleneck в обращении can[x][y][z] (которое на джаве работает раза в 3-4 медленнее, чем на плюсах), — должно зайти; ну и понятно, что в константу раз там очень много что можно соптимизить, так что все такие решения не убьёшь.

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

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

          Мне с некоторых пор ссыкотно на cf челленджить по TL (если там конечно не n2 при n = 105). Смотришь, 10^9 операций. Ан нет, огребаешь -50. Сервера то реактивные.

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

            Да ладно, реактивные? Я часто сталкивался с проблемой, когда решение на CF-серверах работает раза в полтора дольше, чем локально. Впрочем, может там только процессор реактивный, но не память. Или кеш мелкий. Кстати, где-нибудь написана конфигурация тестирующих машинок?

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

              Я имел ввиду реактивные по сравнению с другими onlinejudge. Хотя может это просто субъективное ощущение.

              Насколько я помню на opencup обычно не заходят решения за 10^8 а тут это в порядке вещей.

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

                Субъективно на топкодере решения работают даже быстрее, чем локально. На OpenCup с некоторых пор обновили сервера, теперь там тоже всё быстро.

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

                  Очень странно, на ТС у меня обычно работает дольше (не считал на сколько) а на КФ почти в полтора раза быстрее))

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

Я правильно понимаю, что у всех периодически на некоторое время кф переставал работать? (в начале контеста особенно) Из-за этих проблем я получил где-то -20 баллов по A, тк вынужден был минут 5-10 ждать, когда система заработает, чтобы отправить решение...

А в условиях того, что B и C сдали немного человек, это дало мне +40 мест. Отлично

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

    Да, почти все логично с подсчетом потерянных 40 мест. За исключением того факта, что у других точно так же периодически не работал СF и они точно так же потеряли примерно те же очки.

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

      Прикол в том, что те, кто отправил решение на x минут раньше меня, получили отрыв не в 2x баллов, а в 2x+20 баллов(что в данном контесте существенно). И естественно, я не единственный участник с похожей проблемой

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

I think, this contest should not be rated, due to the network problem.

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

    When the contest first opened on my pc, many people had already submitted the first problem

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

      yeah... so i think this contest should not be rated...

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

        If they said it's going to be rated, it will be rated. End of story :)

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

          All contests are intended to be rated, but sometimes things go wrong and in these cases, the best to do is to not validate the contest.

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

      difference between over 160 contestants is for submission time for problem A and due to the network problem many contestants read the problem A after 10 minutes. so i think the contest should be unrated.

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

      The same happened here.

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

    I agree. For over 200 contestants the difference between them is set by the submission time for A, which today was related more to luck and F5ing skill rather than coding.

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

    The main argument for making round unrated are network problems and late submissions of problem A. But is it normal solving only the simplest problem A and making all the contest result depending on first few minutes in which one sends it? Something is wrong with competitors not solving anything else. Sorry that I write that, being myself far from a strong participant.

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

      No guys, the result of a soccer game is not changed after the game finished because the referee gave a wrong penalty to one of the teams. If they have said "it's going to be rated if and only if we won't have network problems", then fine, but in our case it should be rated :).

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

        Programming contest is not a soccer game. People watch soccer game mostly for fun then for competitive. But here we want a fair contest first. And the network problem is hard to realize during the contest about how serious it was.

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

          Why do you have to take it that serious? Come on guys, it is not even a Final round or something similar. Of course we all don't want these issues to happen, but when it does, just deal with it in a positive way. Make your life and others' easier.

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

        Indeed, but they don't start the match until everyone's on the field, do they? :)

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

What is the solution for E? (div1 C)

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

А почему не получается посмотреть чужие решения?

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

Hard Contest.... Very Hard Contest! :)

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

Три задачи в контестах 293 и 299 совпдают. Контест 299 начался на 5 минут раньше. Контест 293 был перенесен на 10 минут позднее (на 19:40 MSK), а потом на 5 минут ранее (на 19:35 MSK) (я опоздал на 2 минуты в итоге). Вопрос в следующем — что за абсурд, и будет ли отборочный раунд отменен?

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

    Да, к сожалению, сложности были. Честно говоря, какая-то магия — Codeforces существенно не менялся несколько последних раундов, и таких сложностей не бывало. Будем разбираться, что была за проблема. Мы считаем, что на таком проблемсете (довольно сложном) 3 минуты в доступе к задачам не нарушают существенным образом релевантность результатов. Приношу извинения за неудобства.

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

      Лагает и лагает, с кем не бывает, дело то не в этом. Я хотел обратить внимание на странные действия людей, которые переносили раунды. Почему был перенесен только один из двух связанных раундов (с пересекающимися задачами)? Почему раунд был перенесен сначала вперед, а потом назад? Это не сложности с сервером. :)

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

        Писал чуть ниже. Так как были проблемы со стартом, то решил перенести вперед раунд, чтобы все спокойно стартануть. Забыв про div 2, перенес только основной раунд на 10 минут. Потом увидели, что div 2 уже идет, а до начала основного довольно много времени. Что делать? Ждать было нельзя, так как кол-во людей в неравных условиях заметно бы возросло. Перенес основной раунд, чтобы он стартанул в 35 минут. В результате, к сожалению, около 3х минут могли получить преимущество те, кто зашел в div 2.

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

          Ух ты. Повод добавить в админку codeforces проверку на случай переноса связанных контестов. :)

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

      По-моему, релевантность очень неплохо была нарушена, особенно если учесть не три минуты разницы, а все 8 — некоторые успели увидеть таймер, который обещал начало соревнования в 19:40. Разница в 16 баллов между задачей A, сданной в 0:13 и 0:21, это разница в 93 места (между 154-м и 247-м). Ну и сверху таблицы тоже, наверно, задержка сильно повлияла, если учесть, что там эти 16 баллов надо еще помножить на количество сданных задач.

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

in div2 problems I think there is no tricky cases , how could many contestants make successful hacking ???

I viewed all solutions in my room (room 3) but I couldn't find a wrong solution, even there was no successful hacking attempt in my room.

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

Может кто-нибудь ответить на мой вопрос по третьей задаче?

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

Я весь контест писал В. И задачу не написал, и над остальными не подумал, и раунд слил. День удался.

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

    Точно так же у меня, надо было на С подумать :(

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

    Плюс один. Еще я минут пять искал подвох в див2.А, потому что она показалась мне какой-то подозрительно простой. Потом написал ее, попробовал отослать и только тут понял, что решаю не то.

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

      Аналогично. А открыл я его по той причине, что до начала турнира Div2 показывался во второй строке, а после начала — на первой.

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

    Как я тебя понимаю :)

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

Жесть контест. Задачи гробы, сервак весь контест лежит, а вначале я ещё и не в тот див зашёл и задачи не те решал, ибо кликнул на первый контест по списку, а он магическим образом оказался див2, а не див1, как это было ещё до контеста.

P.S.1. У меня еле-еле сервак дал посмотреть задачи вначале, потом еле-еле дал отправить решение по А, итого из первых минут 40 мне удалось загрузить страниц 5, остальные так и не были загружены. Только потом тоже периодически сервак висел. Я думал после таких лагов контесты отменяют...

P.S.2. А задачи хороши. В C был близок к решению, но увы..

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

    Та же фигня с див2-див1. Открыл условие, удивился, что в pdf, написал задачу, хотел отправить, замечаю, что див2.

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

      А как их можно было открыть, если они только в div2 были? Когда codeforces стал хоть что-то вразумительное показывать, div1-контест был уже отложен на 10 минут, и смотреть условия задач в div2 в этом случае было несколько неспортивно :)

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

        Я кликнул "войти" у первого контеста. А это оказался div2.

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

Красные шутят :)

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

Забавно, первые десять-пятнадцать минут неофициальные участники не могли отсылать решения.

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

Imho, this contest was one of the worst-balanced contests i have ever seen. A is too easy(comparing to other problems), C is easier than B (but their costs are same), and both B and C are too difficult for >80% of participants...

I don't mind writing such a contest as usual round, but it's very bad idea to give it as qualification round

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

    I think the idea is that, if you want to qualify, you should be able to do some really hard problems..

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

Задачи контеста div. 2 были не особо сложными. Я ожидал на порядок выше по сложности задачи.

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

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

А в Б заходил перебор с тем, что мы заполним один из путей цифрами 1, 2, ..., (n+m-1)? А потом будем отсекаться по корректности поля.

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

Problem D,E is too difficult for Div.2...

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

I am happy, my C (div 2) solution passed the tricky 6th pretest!!!

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

when will system test begin ?

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

when will system test begin ?

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

what about system test ?

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

Why it's still pending system testing?

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

Всем добра!

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

Codeforces is really getting worse a contest after the other! The contest was a real pain! Every 5 minutes the site goes down, also the system test takes too much time to begin..

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

When is system test bigin ?I hope it bigin soon today!

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

Что за бред? Почему у людей которые сдавали задачу А на делфи не проходит 43 тест по времени?

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

    Потому что в дельфи хреново читаются строчки

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

    У меня TL43, и это нерандомизированный qsort (да, я знаю, что я извращенец, что там нет никакого qsort).

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

    это особая кодерная магия)

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

Осталось найти 7 читеров или не желающих ехать на онсайт — и день удался.

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

    Я в том году прошел на онсайт со 165 места среди официальных участников (в онсайте было так же 50 мест). Так что у вас все шансы. =)

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

      В прошлом году вроде не оплачивали проезд. И отношение к турниру у многих было наплевательское. Там с 200-какого-то места проходили.

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

классная С — не забудь о вольфраме.

начать див2 на 5 минут раньше и спалить АБС див1 — вот это тру.

весь контест сервер лагал — не не, codeforces не бета.

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

Почему нельзя посмотреть решения других участников ?

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

Was in top20. My best result. But then my solution of C failed. And this is the reason.

if(F > S) cout << "First";
if(F + 1 < S) cout << "Second";
if(F == S) cout << "Draw";

Fail...

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

Дорешивания нет.

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

we i can't see other solution ?

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

Sorry, I mistakenly post the comment in russian.

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

I really don't think this contest should be rated.

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

    Yes, I'd like that too. But unfortunately, we all had the same chances. Some of us did really bad (I'm pretty sure Petr would like the contest to be unrated too :)).

    I'm surprised at how many red coders ranked really low. The contest difficult was high and strange. I tried problem A, got WA on Pretest 6, then moved on to problem B and got stuck there. With only 15 minutes remaining, I moved back to A, fixed a few things and got it accepted near the time limit.

    Horrible performance for me this time...

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

      I saw the problems 10 minutes after the contest begins.And then tried A and got WA,a few minutes later passed it.And then stuck on B for about one hour,then I move to C,and complete the code just after the end.I'm said.

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

      IMO decision on whether the contest should be rated or not must not be based on one's bad performance; let's stay objective.

      Arguments for the contest being unrated: lags for the first ~20 minutes (and therefore slightly increased variance in scores, because of additional time to refresh the page); statements for A, B, C available in div2 while div1 contest was not started (and therefore cheaters could start solving problems ~6 minutes earlier).

      Arguments for the contest being rated: variance in results because of lags is insignificant (and lags were fixed quickly), most of participants do not cheat, and if someone cheated, most likely it did not help him (at least I hope so).

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

        Sorry,_I really don't think this contest should be rated._ just means that I just don't hope this contest to be rated because my bad performance,not objectively.I agree with your point mostly.And anyway,the contest has been rated.

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

        Я, как и многие, открыл не тот раунд, думая, что это и есть контест, который надо писать.
        При этом мне сразу понравилась E, я ее прочитал и начал кодить.
        Это считается читерством?
        Или после этого я должен был благородно отказатся писать контест?

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

          Sorry for the Russian language in English thread, feel free to ignore it.

          Очевидно, не считается, это ведь не умышленно было сделано. Неужели действительно у большого количества народа была такая проблема? Я, например, всегда смотрю, в какой раунд захожу, т.к. div1/div2 контесты часто совмещены.

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

      Well, let's make the server available in random seconds during the contest. Yes, everyone has 'the same chanes'. But will it be fair if someone guess these seconds and get positive score and another don't? I don't think so.

      We all 'were in the same conditions' but these conditions were very random and made results valid +- 50-200 points only. That's up to +- 20 places (around 40th). I think it's enough for making this round unrated (however, it can remain eliminate round for the championship).

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

any chance to receive a shirt for ranking 205?

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

    I don't know about shirt but I surely know something about a little differently spelled xD

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

А давайте возьмем на онсайт первые 50 мест и проведем еще один отбор, с нормальной работой сервера и более сбалансированными задачами, чтобы отобрать еще 50 человек! Кто за?

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

    Уж точно не организаторы) А вообще я за, особенно если еще и оставшимся 200 футболки)

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

Why we can't practice now?

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

При этом, раунд будет рейтинговым как для официальных участников чемпионата, так и для внеконкурсных.

Почему обновился рейтинг только официальных участников?

UPD Обновили. +91 :D

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

    У некоторых неофициальных точно обновился, по себе могу судить=)

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

This Cheered me up during the contest.

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

Весь контест сервер работал хуже, чем какой-нибудь codechef в худшие времена.

Не лучше ли было бы после падения сервера на старте отменить div2 раунд совсем, а не начинать его, да еще и вовремя?

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

    Откуда произошел фейл на старте и лаги в процессе — загадка. Серьезных правок Codeforces не было несколько раундов подряд, последние раунды прошли отлично при большей нагрузке. Последний раунд был проведен 3 дня назад, а с тех пор code freeze. Остались логи, буду смотреть и думать. После первого фейла я сдвинул начало раунда, забыв о div 2. В результате произошел несинхронный старт. Причин решить отменять div 2 не было (тем более что я забыл о его существовании).

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

so now it is rated only for offical?

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

I participated in contest unofficially and my rating didn't update.

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

Откройте дорешку пожалуйста

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

    Ты слишком быстро пишешь комментарий:( Я даже обновил и прочитал, но все равно твоего не было:(

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

А где дорешка?

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

I have software problems hacking solutions. Today I had time, locked my solutions, but just couldn't open the sources. I use chrome, have adblocks disabled and have the latest flash player. It's really frustrating. :( Can anyone suggest me what I should do?

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

Ratings have been updated. Interesting :)

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

@admin there is a bug in the ratings.

when i click tourist in the top rated column in the right side, then old rating is there in top rated column . same happens when i click on petr.

however it works fine for other participants.

EDIT : it is ok now.

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

Посмотрел решения на C++ по div1D у топ-20. Свалил штуки три тестом:

3
-1000000 1000000
-1000000 999999
-999999 1000000

Эх. =\

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

    А в чём подвох этого теста?

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

      Из тех, кого я смотрел, было два решения, выводящих nan и одно почему-то 0.3333... Не знаю, в чем там дело.

      А мое решение долго выводило 0.666**8**..., потому что я вычитал одно большое (порядка 1012) число из другого и мне не хватало точности. В итоге я поставил везде long double и понадеялся на слабые тесты, но там такого даже близко не было, заходило и с double.

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

what is test 33 in div 2 problem C. it's like 100000 9 .........................................................................

is it all contain '.'s ?

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

Though I am not sure, in Problem D, assertion fails on 13th case. Is the given polygon convex really?

Edit: So, convex polygon means they can have three collinear points on side? If so then the definition should have been provided properly. Why should one assume 3 points on side will be collinear?

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

    It's common definition, that some figure is convex if and only if for every two points A, B inside it, segment [AB] lies inside figure too. For the convex polygon, where three vertices lie on the same line that condition is satisfied, so it's correct to name that polygon convex.

    Common way is to name convex polygons, where any three points aren't collinear strictly convex.

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

    I asked if 3 points of polygon can be collinear during the contest, and got positive answer. Wikipedia agrees that there can be collinear points in convex polygon. Distinction between "convex" and "strictly convex" would be a good practice in statements, in my opinion.

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

Мне кажется, что раунд следует сделать, как минимум, нерейтинговым. Результаты очень плотные, даже среди тех, кто сдал больше одной задачи. Таким образом, очень многое решает время сдачи, а оно получено с относительно большой погрешностью.

Во-вторых, по-моему, следует изменить критерий отбора на финал КРОК. Либо провести другой раунд, либо расширить квоту. Простой расчет: будем считать, что из-за сбоев сервера, человек потерял до 10 минут (в частности, у меня между посылками, отличающимися 2 символами, прошло более 4 минут + кто-то мог прочитать задачи на 5 минут раньше старта). Организаторы правильно сделали, что продлили контест на 10 минут — так все, кто хотел что-то сдать без лагов за 2 часа, успешно сдали с лагами за 2 часа 10 минут. Однако, большинство участников в районе 50го места сдали задачи A + (B или C). За 10 минут их суммарная стоимость упала на 80 баллов. Мое предложение — пригласить на финал всех участников, кто отстал от 50го места не более, чем на 80 баллов (ну или какое-то другое адекватное число). Не знаю, конечно, есть ли у КРОК возможность провести "расширенный" финал.

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

    Учитывая наличие большого количества далекоживущих иностранцев в топ50 (а дорогу им оплачивать не будут) — с большой вероятностью те, кто немного отстал от 50го места смогут поучаствовать в финале

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

      Надеюсь, так и будет. В первой сотне иностранцев почти половина — если они откажутся, то так и все, кто 2 задачи сдал, на финал поедут :)

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

    Бюджет сформирован и даже всего +5 человек это уже 10%. Плюс с помещением в прошлом году было довольно плотно. На 5 минут раньше старта прочитать задачи никто не мог — максимум 3. 10 минут это все-таки оценка сверху, так как лаги составляли ровно 1.5 минуты (я их в самом деле замерял). Т.е. из твоих 4 минут примерно пара минут по делу. Да, к сожалению, еще пару минут мог потерять из-за лага. За минут 45 до конца все лаги были полечены. Кажется, не круто обижать тех, кто хорошо выступил и, решив задачи, занял высокое место. Это же как accepted отобрать. И, в самом деле, наверняка, многие иностранцы не смогут приехать — так что квота уползет вниз.

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

      Ну... Открыл хистори своего диалога с товарищем, в котором интересовался у него, действительно ли все так плохо, как я это вижу. В 7:33 я увидел названия всех задач div 2, в ту же минуту смог скачать условие задачи A (так же, как и многие, не заметил, что див. 2). Такие дела. Так что стартануть можно было раньше все же не на три минуты.

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

        Старт контеста в итоге был в 35 минут

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

      Да, тогда, действительно, будем надеяться, что откажутся многие иностранцы, чтобы никому обидно не было.

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

      У меня по сумме намного дольше 1.5 минуты приходила ошибка сервера. И просто намноооого дольше было сообщение о загруженности сервера.

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

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

      А москвичам разве нужна гостиница/покрытие расходов на проезд?

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

    just a show off, there is nothing to learn from this screencast

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

      It would be pretty poor show-off, considering my start. Actually I just capture everything I write from laptop (as oposed to 2 monitor configuration on desktop). I do not have enough willpower to rewatch my screencasts before I post them, hence at the time of publishing I do not know whether there were something interesing or not

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

        if you do not know whether there were something interesing or not, then dont post them, though i am getting negatives , but i know truth hurts

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

        i am trying to increase your contribution and wanna see you in first position

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

div 1 c:the problem ask you to calculate the number of solution of equation (a+b+c)^3-a^3-b^3-c^3=n and (a+b+c)^3-a^3-b^3-c^3=3(a+b)(a+c)(b+c) so the equation is n/3=(a+b)(b+c)(a+c) put x=a+b y=b+c z=a+c and x<=y<=z my solution is to enumerate all the x and all the y it seem as a o(n^1/3(n^1/2-n^1/3))=o(n^5/6) but it is really fast and I accept the system test.Is it a right way to do this problem?

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

    My solution: 1 <= x <= y <= z and x,y,z should be the lengths of the edges of a triangle, that is z < x + y. Also, we should have that x +y +z is even. Now: N = 3xyz. N >= 3*y^2 and N < 3xy(x+y) <= 6y^3. So we got the bounds for y: sqrt[3]{N/6} < y <= sqrt{N/3}

    The bounds for z : y <= z and z is such that N > 3yz(z-y).

    Iterate over all y and all z with the above conditions and compute x = N/(3yz) and see if the conditions stated above happen. If they do, increment the result with the total number of permutations of this triplet.

    My sol: submission/3606646

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

Имя Ксения в задаче D было выбрано случайно?

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

Change from IGM to GM to IGM to GM to IGM in last 4 contests :)

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

Не надо перебирать все. Достаточно собрать в массив делители n/3. В две секунды влезает даже если собирать до sqrt(n), для решения достаточно собрать до sqrt(n/6).

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

Когда появится разбор задач?

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

Editorial please!

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

If there's no editorial, maybe someone can explain approach for problems D and E?

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

    PROBLEM E: we can solve it using divided and conquer algo. just consider the paths go through the root,the paths in the subtrees is sub problems,so we can solve them recursively. for every root , we can run a dfs to get tot pairs (depth_i,sumofw_i),now the problem transformed to this:give you n pairs (ai,bi) , find the number of pairs( ai,bi aj,bj ) so that (ai+bi <= L && bi+bj <= w) ,we can sort the pairs first ,and then use algorithm like two pointers to solve it (sort the pairs first)

    ps:the root can't choose arbitrarily,because the depth of divided and conquer shouldn't be very big,so every time we should find the center of the tree(when it was deleted from the tree,the maxsize of the components is the smallest) overall the complexity is n*logn*logn theres is another similar problem for practice http://poj.org/problem?id=1741

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

      Actually, if you just sort the pairs and iterate over them with two pointers, you'll end up counting some paths more than once, because you only need to consider pairs in different branches so that the path goes through the root (pairs in the same branch will be counted in the sub-problem of that branch).

      I'm still thinking how to solve that part...

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

        Yes , you are right ,I forgot to say that point... the way is simple , just use a function calc(u) to count the pairs of nodes
        under the root of u,and minus every calc(son_of_u) . you can see my code here the vector<pair<int,int> > ch[] stores the information of every son of u

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

What is the solution for problem B and C Div 1

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

    For C, notice that:

    (a+b+c)^3 - a^3 - b^3 - c^3 = 3*(a+b)*(b+c)*(c+a)
    

    Number of divisor of an integer less than 10^14 is small (I remember it's around 20,000), thus you can brute force (a+b), (b+c), and check if a, b, c are positive integers.

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

Maybe someone can explain approach for problems B(div.1) ?

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

Still no editorial?

In the meantime, could someone give me a hint for D? What I tried is to find y_low and y_high for every possible x such that segment formed by (x, y_low) and (x, y_high) lies inside the polygon. The rest parts are just some formulas. However, my implementation got a 2e-6 precision error for a large test and I am not sure which one is wrong, my approach or my code.

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

    My approach gives even more precision error. But with long double on GNU it get AC.

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

I wonder if there exists solution for problem D (expected square area) without limitation on lattice points.

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

can you give me some hints for problem E? my best solution is in N*(logN)^3 and i don't know if it is fast enough...

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

Про футболки какая-нибудь информация известна?

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

    Я передал все данные для рассылки в КРОК, их компания-партнер, как мне сказали, всё разослала.

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

    а теперь их кто-нибудь получил?

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

      Я до сих пор не получил. Есть ли те, кто получил, или те, кто обладает какой-либо информацией?

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

        Мне вот что интересно. Казалось бы, зачем компания проводит контест? Ну вроде бы, показать себя, заявить, что они вот такие клёвые есть, они ищут IT-шников, у них клёво в офисе, etc. Т.е прорекламировать себя, чтобы кто-то пошел работать. А в итоге они что показывают? Может они и зарплату так же "быстро" платят?