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

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

Всем привет!)

Сегодня состоится очередной раунд Codeforces #143 для участников второго дивизиона. Наверное, нет смысла напоминать, что ребята с рейтингом больше 1699 могут поучаствовать в нем вне конкурса.

Авторами задач для данного мероприятия являются Холкин Павел (HolkinPV) и Кузнецов Николай (NALP). В подготовке контеста также участвовали Кудряшов Игорь (Igor_Kudryashov) и Агапов Геральд (Gerald). Отдельную благодарность выражаем создателю прекрасного ресурса Codeforces Михаилу Мирзаянову (MikeMirzayanov) и нашей переводчице Марии Беловой (Delinur).

Распределение баллов по задачам будет определено через некоторое время, следите за изменениями).

Желаем всем получить удовольствие от соревнования и почерпнуть для себя что-то новое и полезное.

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

UPD2: Раунд окончен. Благодарим всех за участие. Шесть человек, занявшие первые места решили все 5 задач, поздравляем их с отличным выступлением.

1) teoy

2) gomineral02

3) mrNobody

4) Ryannnnnnn

5) marschenly

6) KuchumovIlya

Разбор задач будет опубликован через некоторое время.

UPD3: Разбор опубликован, его можно найти здесь

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

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

Одна только просьба — расположите задачи в порядке возрастания предполагаемой сложности. В прошлом вашем контесте задачу Е решили в два раза больше людей, чем задачу С.

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

    Возможно так и предполагалось?

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

      Хорошее предположение — чтобы задачи В и D были примерно одинаковыми по сложности, а баллы за D в 2 раза больше, чем за B. Нужно было делать динамическую разбалловку — тогда все было бы справедливо.

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

    Опять не вышло.

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

Надеюсь задачи будут интересными.

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

270 new user and keep growing.

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

Следим за изменениями с надеждой на привычную разбалловку.

upd. УРА!

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

First Codeforces round on Sunday since a long time!!! This should happen more frequently!! Thanks to authors!!! Good luck to new users!!

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

Задачи отличные!

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

У меня одного недоумение насчет D? Почему эта задача D?

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

    Постарайтесь прочесть условия всех задач! (с)

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

    потому что это должна быть А.

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

      А сегодня на своем месте.

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

        Согласен, текущая А соответствует уровню задач "А" 2 дива. Но и текущая Д попадает в эту же категорию сложности, хотя она чуть сложнее сегодняшней А.

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

Отличное соревнование! Первое, в котором 4 решения прошли претесты и, я надеюсь, пройдут и системное тестирование.

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

наконец-то отличный div 2. раунд

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

Was Problem D really that easy or have I done some mistake ??My code

If I am correct then I think the problems should have been aranged as A , RightShift( B,C,D ) ,E

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

    I agree with you. But I appreciate it as a test to come up with such an easy idea for a problem of 2000 points after writing harder solutions for 1000/1500 :-) [I am aware that those who open D first have got extra points ;-)]

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

    I´m totally agree with you problem D was really easy and problem B was a little bit tricky

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

Really nice competition, though it was kinda surprising that the 4-th task was solved by 6 IF-s, i mean at standart score distribution it's expected to be sorted by difficulty. :)

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

What an amazing Round. 5 Problems are very nice. Thank Authors very much :)

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

Отличный контест. Спасибо авторам. Но почему в последние минуты на задачу В давало "Неправильный ответ на претест 1"?

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

Классный раунд...!!! Большое спасибо авторам....!!!!!

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

А какой ответ в E на тест:

5 5
1 2
2 3
2 4
2 5
4 5
1
1 3

?

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

any simple solutions of B?just some words about solution pls

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

    Well you can notice that the number that's resulted at the end is a1-a2+a3-a4+a5... where 'a' are the numbers from the initial array. And i suppose you can find em easily knowing that, didn't have enough time to realize that solution.

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

      yes had exactly the same idea,but somehow could not realize,my bad...

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

    S1=x1+x3+x5+... S2=x2+x4+x6+... n1=n div 2+(n mod 2) n2=n-n1 d=S1-S2 n1<=S1<=l*n1 n2<=S2<=l*n2

    Look over possible S1 and S2 values. If it is possible to take such S2 and S1 that d=S1-S2 then answer exists else it doesn`t. In case of its existance some efforts to output the sequence are required.

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

Почему-то если люди решили в контесте больше задач, чем обычно, то он становится классным. А если, ни дай бог, меньше, то все, контест — уг.

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

    Именно. Мне нравятся задачи, которые для меня интересны, то есть не на "побыстрее напиши" и "шесть ифов".

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

      E вполне нормальная была.

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

        Имеются в виду все задачи. Круто, конечно, что последняя является последней по сложности, в наше время это редкость.

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

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

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

Спасибо авторам, отличный раунд! Понравились задачи B и С, из разбора Е наверняка можно будет почерпнуть новую информацию.

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

D стоит 2000, ага. Задачка на ветвление.

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

Ребят, кто делал Б динамикой? Весь раунд ловил 4 тест..

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

    Извращенец.

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

      А как надо?

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

        Понять, что число d = k[0]-k[1]+k[2]-k[3]... И раскидать его по 1 на массив.

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

          Я это понял и решил писать динамику:)

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

          Что значит, раскидать по 1 на массив.

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

            Если еще не получен искомый массив — пытаемся на 1 приблизить его к ответу. Для этого ищем элемент массива и увеличиваем его на 1.

            Начинаем с массива 1 1 1 ... 1 1. +1 к элементу на нечетной позиции — ответ +1, на четной — -1.

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

    Решал так. Пусть d=**a**-**b**(из условия). В ответ сразу войдет a, поэтому подбираем его от 1 до L, причем так, чтобы |b| был минимален, этот b будет d для следующего шага. Повторяем n-1 раз. Причем на последнем шаге b должен быть еще натуральным. Минимум мы ищем для того, чтобы в случае большого первичного значения d у нас была возможность его уменьшить к (n-1)-ому шагу, в противном случае — разложения не существует.

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

Очень печально сдать А на 1 минуте и затем больше ничего не решить >_<.

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

    и ты не один такой((((

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

    А D? Она же почти как A, 6 if'ов

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

      Ну эти 6 ифов не так очевидны, да я честно говоря, не ожидал такой халявки на Д. Думал там какая-то фигня с реализацией окажется и забил(. А зря ведь

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

        Зачем думать? Писать надо.

        upd. /sarcasm/

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

          Писать не думая О_о. Я думал что мой друг выдает бред, когда говорит, что код это не главное, а главное что есть идея и пофиг, работает она или нет. Я жестоко ошибался...

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

          не согласен, думать надо!

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

            Думать надо над решением, а не о том, что возможно, скорее всего, в этой задаче все сложно и её будет очень трудно писать.

            Надо брать и писать. На листочек формулы.

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

        Достаточно лишь представить из каких точек мы "видим" плоскость. Сразу становится понятно, что подходит все полупространство, находящееся левее/правее (выше/ниже) данной плоскости.

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

      Я почему-то смотрел неравенства в системе, но не додумался рассаматривать их по-отдельности >_<

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

Сейчас просматривал решения людей, у которых упала 1 задача. Наткнулся на решение участника korvin42: 2313221. До сих пор в недоумении: почему это упало?

P.S. В задаче B есть опечатка: не "время", а "времени")

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

Бредовый раунд

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

Когда будет разбор? Сегодня дождусь?

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

the order should be A,D,B,C,E

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

Давно у нас 500=2000? Писать B было намного сложнее, чем D. По-моему, расстановка A-D-B-C-E чуть больше соответствует истине.

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

Возникает естественный вопрос — почему не используется динамическая разбалловка?

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

    Потому что она — недоделанная ***ня.

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

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

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

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

      Тогда другой естественный вопрос: зачем ставить задачу для 7 класса на 4 место? Впрочем, вряд ли тут кто-то знает ответ.

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

        Потому что это — геометрия. И не во всех школах(более того, почти ни в каких) преподают такую геометрию в 7 классе, ага.

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

          Не так давно в DivII была одна геометрия даже и поближе, чем D...

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

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

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

        Это скорее к авторам. По неведомым данной ветке форума причинам, они посчитали ее стоящей 2k баллов.

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

        Но чтобы так через две задачи — это оригинально. B даже кодилась сложнее D, та и идея вроде бы не проще.

        (Я, как полная идиотина, додумался прочитать условие D где-то на 1 30. Счастья-то...)

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

Расскажите как B и С решались, пожалуйста, подробно если можно.

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

    C-префикс суммы + дихотомия!

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

      А можно немного подробнее, если не сложно?

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

        С можно проще — двумя указателями.

        Сначала сортируем.
        Пока можем (стоимость не привысила k) — двигаем первый указатель x вправо, при этом иногда увеличивая стоимость: если a[x] != a[x-1] то s += (x-y-1) * (a[x] - a[x-1]). Пытаемся улучшить ответ.

        Затем пока стоимость больше k — двигаем второй указатель y вправо, уменьшая стоимость на a[x] - a[y].

        Линейное решение + время сортировки.

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

      Можно решать без префикс-сумм с помощью двух указателей.

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

    B в лоб. Очевидно, что d=a(1)-a(2)+a(3)-a(4)+..., ну или S1=a(1)+a(3)+..., S2=a(2)+a(4)+..., d=S1-S2. Можно легко посчитать макс. и мин. значения, которые можно получить: Заметим, что в S1 элементов q=[(n+1)/2], а в S2 — p=[n/2]. Тогда max=q*l-p, min=q-p*l. Для существования ответа необходимо и достаточно min<=d<=max.

    А дальше можно просто придумать, как построить s1 и s2 подходящим образом. Я, например (на примере положительного d) брал это d и поступал след. образом:

    пока d>l-1, ставлю на нечетное место l, а на четное 1, и из d вычитаю l-1 (ну, разность между этими элементами). После этого получаем d<l-1, что позволяет поставит необходимое число (d или d-1 в зависимости от честности n) в соотв. ячейку, а дальше дописать единицы.

    Явно существует путь проще, но я его не нашел.

    Сам не против послушать решение C.

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

    C:
    Отсортируем массив; понятно, что число из ответа изначально есть в массиве. Давайте для каждого числа узнаем ответ для него. Пусть это ai. Так как у нас есть только прибавления, нам интересны только числа меньшие ai, т.е. до него. Запустим бинпоиск, чтобы найти максимальное количество чисел, которые можно сделать равными ai. Можно доказать, что выгодно брать суффиксы из последовательности a1, a2, ..., ai. Осталось научиться проверять можно ли числа на подотрезке превратить в ai, это легко выяснить, зная сумму на этом подотрезке.
    Код в точности по этому описанию.

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

    Я решал так. Отсортируем массив за O(n * log2n) быстрой сортировкой. Далее, воспользуемся методом двух указателей. Сначала оба указателя на 1 элементе. Потом сдвигаем правый указатель на один элемент вправо и двигаем левый, пока k ≤ count, где count равен количеству действий для доведения всех чисел с l по r до a[r]. Все решение работает за O(n * log2n) + O(n) = O(n * log2n). Код с таким решением.

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

Для меня задачи показались не совсем очевидными (решил три, С и E не сделал), удивляюсь как много людей начало решать столько задач в див.2, неужели все стали такие крутые.

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

Nice problem set and competition, though, I believe System test was fast because of El Clasico :D

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

почему у меня здесь 2319144 ВА на первом тесте? upd: поставил r:=0; и оно почему-то прошло 2319298. почему?

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

    Числа должны быть в пределах от 1 до L.

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

    числа должны быть не больше l.У вас дано, что l=2,а вы выводите 456988, что явно больше 2

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

Hi! How can this submission get AC on problem C: http://www.codeforces.com/contest/231/submission/2319083 But it gets the wrong answer on this test:

10 0
1 2 3 4 5 6 7 8 9 10

Correct output must be: 1 1, but its result is 2 2. Is the test case weak ?

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

Контест получился хорошим.Но не менее важно дорешивание.

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

The problemset was good. Not very easy and not very hard. Liked it really much.

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

как в java сортить массив, и при этом быть уверенным, что она работает не n*n в худшем случае?

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

    писать сортировку руками

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

      я уверен это не лучшее решение

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

        шаффлить массив не?

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

        В java есть Arrays.sort и Collections.sort. Обе в худшем случаи работают за n*n

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

          Если у тебя с сортировкой проблемы, то дальше будет еще сложнее...

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

            Больше чем за год активного использования Arrays.sort не было ни одного TL-я. Использовать встроенную функцию — это благо, естественно при хорошем понимании, как реализовать это руками. (и до сегодняшнего контеста я верил, что в яве сортировка хорошая(в т.ч. если верить докам))

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

              В доках кстати и не написано, что она (для примитивных типов) в худшем случае за NlogN работает.

              Эти тесты — особенность Codeforces как игровой площадки. Надо быть к этому готовым. HashMap, например, тоже опасная штука.

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

    Массив примитивов — никак. Надо делать рандом шафл.

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

    Можно случайно перемешивать массив (см. мое решение).

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

      Хоть один конструктивный ответ. Спасибо!

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

      Главное следить, чтоб рандом временем инициализировался, а то ведь можно массив отшаффлить обратно :)

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

        javaзадроты

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

          Куда денешься, если не хочешь быть похаченным своим собственным антиквиксортом ? :)

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

        Как я и думал, следить ни за чем не надо (вот код дефолтного конструктора):

            public Random() { this(++seedUniquifier + System.nanoTime()); }
            private static volatile long seedUniquifier = 8682522807148012L;
        
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Напиши руками mergesort или heapsort и скопируй его к себе в шаблон

    Ого, сегодня на этом попался ivan.metelsky

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

C упала на тесте

1 0
0

:facepalm:

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

Has anybody here solved B using Dynamic Programming?

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

    yes.

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

      Great. I thought it was too slow to get Accepted. The time complexity is nearly O(10^8). However, I got AC.

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

        If time complexity is O(10^8) be sure you'll get AC. :D UPD: Of course on Codeforces

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

          I don't know, i've got a lot of TLE's with time complexity O(10^8). Before SPOJ gets a faster processor, it was a bit hard to get AC with this time complexity. Anyway, CodeForces has a fast judge.

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

контест -- СУПЕР Задачи легки на понимание А первая задача -- ХАЛЯВА

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

    Халява — это D. A хоть на 500, она и должна быть такой.

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

    Кому-нибудь халява, а кому-нибудь и дебры.

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

Great competition!

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

Хороший раунд, но разбалловка, конечно, странная... Я задачу B почти полтора часа кромсал, все варианты рассматривал, а D за 10 минут 6 ифами сделал. Может за нее 2000 баллов дают, потому что она для новичков страшновато выглядит, если не читать условия?

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

very nice problem set, thank you very much ^^

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

I think there were lots of WA's on problem C. Maybe reason is there were no alert about not using %lld specifier on C++. So lots of people didn't use 64-bit integer. and maybe 64-bit integer was not neccessary on authors solution.

UPD: The only thing different with this comment and mine is downvotes and upvotes :D

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

    Numbers that you need to find are fit in 32-bit type, so I think the warning about %lld was not necessary.

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

    I made 2 successful hacks on submissions which did not deal with overflow in multiplication. It seems to be the most common mistake I think.

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

Отличный контест. Только задача В мне показалась намного сложнее чем Д. Возможно это субъективное мнение.

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

……

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

Как получить кучу восторженных откликов за контест div 2? Предложить в нем 4 простые задачи и пятую с более-менее очевидным решением из нагромождения классических алгоритмов.

Нет, наверное, и вправду стоит хотя бы изредка делать такие контесты. Но все же С и D лучше было дать посложнее. Потому что для меня радость от решения задачи как-то коррелирует с временем, в течение которого я над ней думал.

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

    C — очень хорошая задача, а вот B я так и не понял, как делать, во время контеста)
    B и D, думаю, следовало поменять местами.

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

    C — довольно интересна, D слишком легкая как для D, но в целом контест довольно хороший. А у меня радость от решения задачи пропорциональна (сложности) / (время, которое я потратил на решение).

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

Куда спрятали разбор?

UPD: Спасибо, вернули. Не пугайте ;)

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

Читаю и ору с себя:/

Все пишут про халявную D и 6 ифов. Я умудрился написать в ней пересечение прямой с плоскостью и рассматривал варианты: если прямая из точки обзора до центра плоскости не пересекает другие — значит можно добавить к сумме. По-настоящему халявная А и довольно идейно простая С. А предположив, что надо было кодить в B, поплевался и начал решать другие задачи. Да и вроде бы это кодить и надо было. Странный раунд :/ Неудивительно что 195ый(долбанная Д — такая простая для всех).

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

I really got surprised when I saw problem B is dp, ...!

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

    Greedy is accepted too.

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

      How can we Dp problem B. Can you show me ???

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

        dp f[i][s]=true means that where are a[0]...a[i] left after some operations(a[i] is not the origional one), and a[i]=s(probably negative)... we can enumerate a[i] from 1 to l to check if condition f[i+1][s2] is true, here (s = a[i] — s2).finally check if f[n-1][i] is true for some i from 1 to l

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

The hyperlink of editorial is linked to russian editorial again:( hope you can fix it:)

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

Хороший контест, спасибо!) Правда, то, что кактус вершинный, я понял только что.))

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

I think that problem C was extremely harder than problem D!