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

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

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

Осталось меньше 11 часов до начала Codeforces Beta Round #98 (Div. 2). Этот раунд для вас подготовил я, идеи задач мне подкинул MikeMirzayanov. По традиции RAD проследил за тем, чтобы я не посадил багов и написал нормальные условия, а Delinur перевела условия на английский язык. За что им всем спасибо!

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

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

Продолжу небольшое повествование о себе (начало в предыдущей записи в блоге). Кроме программирования я очень люблю спорт. В течении нескольких лет до того как я начал писать код, я достаточно серьёзно занимался академической греблей. А до этого я занимался практически всеми видами спорта :-): каратэ, футбол, хоккей, борьба самбо и ещё много всего интересного. Сейчас очень люблю (особенно на сборах) играть в волейбол и настольный теннис. Я решил подготовить этот раунд несмотря на то, что в течении последних двух недель Codeforces заметно менялся внутри и я принимал в этом участие.

Следуя модным тенденциям скоро поменяю аватарку.

Всем удачи на раунде и высокого рейтинга!

UPD:

Соревнование закончено, результаты окончательные, рейтинги пересчитаны.

Top 10 (Div. 2)

3. stx2

Поздравляем победителей!!!

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

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А я все ждал, когда CBR 98 появится на главной ;) Удачи всем! Надеюсь, задачки будут крайне увлекательными :)
»
12 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Спасибо за раунд!
Всем good luck!

Вопрос: а какая разбаловка?
»
12 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Рановато для Div2
»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Удачи, Эдик! Написать твой раунд в реальном времени не смогу - зачетная неделя на носу и все такое прочее - но постараюсь написать виртуально.
»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Всем удачи!=)
Было бы на час раньше - поучаствовал бы
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

неудачное время контеста

»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Видимо, буду писать контест с работы, и поэтому Коша не сможет мне помогать. Это проблематично, т.к. Anonymous установил что все задачи за меня обычно сдаёт она... ;-)

Да и посидеть наверное удастся недолго. Однако всё равно будет оч. приятно поучаствовать - надеюсь, и своих силёнок хоть на первую задачку мне хватит! Спасибо за организацию мероприятия!
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Даёш Anonymous - в группу антидоппингового контроля!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    значит надо взять Кошу на работу =D
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Предлагали - да она меньше чем на Yandex не соглашается... Амбиции, однако... :-o
»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Luckly,there will be not class for me in the afternoon,so I can take in the contest;thanks for your hard work!
»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Thanks for your work! I think this round will be fun.
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Учите матчасть, Иннокентий никакой не одноклассник, а ученый с мировым именем!
»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
И все же, 10 утра - не ок)
»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
I was going to watch Mission Impossible 4 !!! I had to change my plans because of the contest . :P 
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Если попытаться открыть страницы без логина, кидает на all your bugs. До начала со старыми контестами так не было

UPD: уже пофиксили

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

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если бы это были превентивные меры администрации - вряд ли бы кидало на all your bugs
      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Рядом сидят 4 залогиненых ученика - всё видят и решают - так что скорее всего это именно так, как я написал выше.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, но это скорее баг, чем фича. Уже разок случайно отключали эти страницы при логоффе
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну, помимо прочего, это ломает парсилку тестов, например
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я о парсилке тестов, например, из моего плагина
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не совсем понятно, в чем прогресс, если учитывать, что обсуждение задач во время контеста идет, в основном, теми, кто в нем участвует
            Кроме того, 2 недели назад позиция Миши была четкая - то, что не было видно задачи без регистрации - баг
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Как раз я уже успел ручками вбить тесты для всех задач :(

»
12 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится
Оо, "Все задачи" - это очень удобно! Спасибо :)
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I want to hack a code  but my test is too large. is there any other way??
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Generator is not determinate [the verification run produces different output, cmd =test].

Объясните, пожалуйста, в чём проблема

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В генераторе нельзя использовать рандом, то есть то, что он выводит, должно быть однозначно.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      random использовать можно. Но нельзя писать что-то вроде randomize; или srand(time(NULL))
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    How can I use generator??

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      This generator output first sample:
      #include <iostream>
      #include <string>
      #include <cstdio>

      using namespace std;

      int main()
      {
      puts("CPCPCPC");
      return 0;
      }

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    У вас генератор использует недетерминированную псевдослучайную последовательность. Надо, чтобы он выводил одинаковые значения при запусках.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится
      Мне кажется, или надо добавить в ЧАВО правила написания взломов, а также их примеры на разных языках(минимум 3).
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Извините, я новенький на CF, сдаю задачи на C#, и вот только что столкнулся с неприятным фактом:
сделав задачу, отправил ее, вердикт - "решение зависло на тесте 4". Отправил еще раз - "решение зависло на тесте 1", отправил еще пару раз - уже на тесте №8, отправил еще раз - претесты пройдены. При этом менял я в исходнике только комментарии, ибо не позволяет отправлять один и тот же файл более 1 раза.

Так вот, это я что-то дико делаю не так или это распространенная проблема?
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Все "зависшие" решения перетестированы.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо, правда баллы за лишние попытки утеряны в любом случае, но это такое дело, не беда.
      А если в последующем будут подобные "зависшие" решения - то как поступать? Ждать пока перетестируют? Но ведь надо быть уверенным, что решение прошло все тесты, а время идет...
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Мы сделаем проверку на "зависшесть" более лояльной. Дело в том, что .NET впервые довольно долго стартует.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          .NET или Mono?
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Mono, но я не уверен, что она установленный .NET никак не использует.
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Mono вполне себе работает и без установленного .NET-а, то есть никак оно его не использует
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
after contest finishes check out organofjohannbach's solution to problem C. This guy must be real pro
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Liked the problem set, but I cant understand how to prove binsearch in E, can anyone help?


    Binary search is incorrect, can anyone explain right sol?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      It is not correct as function is not monotonic. baaab has good string of length 5, but not of length 4
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Binsearch is incorrect solution for E.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Well my solution for E works like this,
      1. Convert the string into an integer array A. convert a vowel to -1 and a consonant to +2.
      2. Calculate a sum array, where sum[i] is the summation of A[0] to A[i].
      3. Now for each i, we need to find the minimum index j<=i, such that sum[j]<=sum[i]. For this I used a binary indexed tree. So for i we found the longest good substring which starts at j.
      4. Thus longest good substring can be easily calculated in O(nlogn).
      5. The number of times can be easily calculated in O(n).
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

epic fail... проспал контест на час, за 10 минут решил Е и около получаса возился с В =)  и лучше бы спал дальше...

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Что надо было делать с D?
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    dynamic programming, dude

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

    Как минимум поменять ее с Е местами... Не, она на своем месте)

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

      I agree, E was much easier to code, D took me much time

      I was wrong, my sol. is wrong for E

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      как её решать за 10 минут? :)
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Мое решение упадет. На сонную голову показалось, что оно правильное =)
        Только сейчас заметил
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Бинарным поиском, но это неправильно.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          спасибо, а то я испугался, что совсем глупый =)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну вот у меня решение за 13 минут, я не ожидаю, что оно упадет. Было бы за 12, но пришлось ручками копировать 5 тестов
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            я не удивляюсь, что это смог сделать ты ;)

            но когда синие в голос кричат о том, что E - халява, впору почувствовать себя идиотом... =)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не, не надо себя никем чувствовать, синий просто писал всего полконтеста и дико сонный =)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Спокойнее... Надо держать себя в руках - мы, синие, очень часто ошибаемся не только решая задачи, но и оценивая их... И надо легче относиться к нашим заявлениям... ;-)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            не-не, я не могу действовать по принципу Василевского-Хаустова, который гласит: "если у твоего оппонента рейтинг меньше твоего, то он автоматически неправ"

            цвет только косвенно отражает интеллектуальные способности человека, поэтому и Egor может ошибаться, и толпа синих может глаголить истину
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, уже понял... Че-то кодил не думая. А по-честному как?
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            есть идея, но непроверенная: сделаем дерево отрезков по 2*c - v на отрезке от 1 до i. Теперь идем по строке слева направо и заносить букву в стек. Теперь нужно посмотреть, возможно некоторый префикс стека имеет смысл удалить. Для этого по дереву отрезков смотрим максимум, если он неотрицателен, то все хорошо, иначе нужно удалить букву из стека и сделать апдейт на дереве.
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Спасибо.
            Хм... даже ничего сверхестественного не нужно
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится -12 Проголосовать: не нравится
            О, баг ограничения уровня. Надо после коммента располагать ветки ответов на него, а потом уже комменты по факту того же уровня
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +12 Проголосовать: не нравится
            Это не баг. Мы именно так и хотели сделать
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится -9 Проголосовать: не нравится
            Извините, но наверное многим покажется что вы хотели чего-то странного :D
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Вы хотели отображать комменты в порядке бфса начиная с какой-то глубины вместо дфса? Ну-ну :)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

            Сообщения выводятся в порядке их появления. Это сделано именно для того, чтобы дискуссии сильно не углублялись.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не удвоенное число согласных минус число гласных?
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Это, уж извините, бред. Либо совсем запрещать, либо сделать нормально. Перечитайте на свежую голову подряд что написано в этом и выше комментах
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да, конечно, опечатался
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится -12 Проголосовать: не нравится
            Ничего хорошего в этом нововведении, ИМХО, нет. Лучше бы сделали не обрезание слишком глубоких веток, а сворачивание...
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Помесь лапши с телетайпом... Ничего не понимаю. %)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            я, кажется, придумал новую задачу к контесту ;)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            Она будет про блоги на CF?)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +6 Проголосовать: не нравится
            ;)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится
            Вот главное пока дискуссия идет - понятно, что к чему. А потом если кто-то прочитать решит - желаю удачи
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится -12 Проголосовать: не нравится
            Мне кажется, проблему нужно устранять уменьшением сдвига сообщений вправо. Каким образом? А хотя бы уменьшением аватарок и переносом имени автора поста в заголовок. Да и дефолтный шрифт можно было бы уменьшить.
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            После прочтения этой “ветки” фраза “это сделано именно для того, чтобы дискуссии сильно не углублялись” приобретает оттенок “не пользуйтесь обсуждениями на CF”.

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

            Но вот когда разработчики социального ресурса исходят из того, что технические возможности первичны, а желания пользователей вторичны — это, на мой взгляд, большая ошибка.
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            3 часа назад, # ^
               +6 
            Вот главное пока дискуссия идет - понятно, что к чему. А потом если кто-то прочитать решит - желаю удачи
            Прочитал. Еле вкурил.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        странно, если все ~10 минутные решения - это бин поиск, почему их никто не ломал?
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Вот, если не быть крабом, то можно накодячить такое решение минут за 5. Но я-краб, поэтому мне пришлось создавать свои пары, мучиться с компаратором и т.д, вместо того чтобы сразу добавить (0, 0). Придумывается это ровно 3 минуты.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +11 Проголосовать: не нравится
          "Придумывается это ровно 3 минуты."

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

            Эээ... А разве нет? По-моему, заменить гласные на -1, согласные на +2 - очевидно. Сумма на префиксах - очевидно. Единственное над чем стоило подумать - то что для каждой позиции можно итератором поддерживать последнюю позицию, где подстрока все еще не отрицательна. Значит, после сортировки будет тупо один проход. 

            Ну а дальше наступает "моя любимая" реализация...

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
i also tried to use binary search but i found out mistake soon...
»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Thanks to admins,codeforces was really fast today. I have participated in 36 contests but never seen cf working so fast,its great :).
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что-то мне во время контеста пришло в голову, что в третьей ограничения 1e6 и я пытался упорно ломать людей, которые массив на n в стеке заводят :(
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

my C is Denial of judgement

wtf?

It's ok now, sorry
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
a lot of C recv " Denial of judgement"
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
наблюдаю многочисленные отказы тестирования в задаче C ;)
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Nice problem set!
But I have a little question:
In a char tab[100], is the '\0' counted on the 100 ?
Because I have tried to hack a code who had a char tab[100] for the problem A, with a string "C....C" (containing 100 'C'), and it was unsuccessful...
Thanks you in advance
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    It is, but in C++ there are no range check, so trying to hack for being out of bounds for array/vector are very risky (expecially with off be one errors)
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    '\0' would never be counted in this 100 chars since it is just implementation detail of one of variants of holding string in one of programming languages.

    Anyway char tab[100] would not necessarily yield error with 100 Cs - it is possible that 101-th '\0' was placed in spare memory after the end of the array without error...
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I also mis-hacked one solution, in which he tried to access indexes of a vector which did not exist.
      To make sure that my hack is correct , I tested it on my computer, and it caused Seg. Fault.
      And unluckily enough, got -50 During hack. :(
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        It is very unstable thing. For examle suppose:

        char a[100];
        char b = 5;

        int func() {
            return;
        }

        Suppose, user made writing into a[100] - what then?

        If code is not optimized and data are not aligned, he will write actually into b.
        If code is aligned at 4 bytes border, he will writing between end of a and beginning of b - no problem at all.
        If code is optimized, b may become register variable and disappear, if code is not aligned, he will erase beginning of "return" instruction (this may lead to funny bugs).

        However this depends on actual placement of data and code, architecture etc.
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
a lot of people had solution in o(n*n) but i couldn't hack because you cant send test with more than 20k memory ...
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    You can send a generator
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      When I try to upload the input, why did it not say: "Your Input is more than 20kb limit. " in RED BOLD FONT.
      When I click on Hack, it did not do anything .
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        You should upload a generator, not an input
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          I know now. But I want to ask , why does the interface not show that "What you just uploaded is so much large in size that we cannot handle, plz use generators" in RED BIG FONT instead of just blinking once and keeping quite.
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yes, I don't like this too... I have seen a code who use a int tab[10000] for the problem C, and I didn't can hack his problem because my input was too large....
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      You can't hack not because input was large, but because you never tried sending generators, though it was discussed a lot of times.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      The reason you need generator is for large inputs,input file becomes to large,may be some megabytes and uploading them will create severe pressure on server. If you want to know how to write generators,here is my generator in div2C:
      int x=1;
          cout<<100000<<endl;
          for(int i=1;i<=100000;i++)
          {
              if(x+1>1000000000) break;
              printf("%d %d\n",x,x+1);
              x+=2;
          }
      I have hacked some n*n solutions with this today.
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Hey guys. I competed in codeforces for the first time today. would anyone mind telling me why my submission for problem B gets a run time error? thanks!
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Look at the constraints.  You can get values bigger than N for t-1 in this line
    V[t-1] = true;
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Извиняюсь, но я не могу понять.
Если у нас есть массив пар - pair <int, int > a[n];
И мы напишем sort (a, a + n);
То по какому приоритету он будет отсортирован?
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Y the system test didnt accept my problem A submission?
»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Very nice algorithmic problems! It gave me a lot of pleasure to solve them! Thanks! 
»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
I like this contest.I'm happy and learn a lot after doing this contest.Thanks the author!
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Could anyone please tell me why my solution got WRONG_ANSWER on this test?
Test: #22, time: 90 ms., memory: 42128 KB, exit code: 0, checker exit code: 2, verdict: WRONG_ANSWER
Input
WdYlPYGSNSGYPlYdWpIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhzVWOelUjtrMyIpZassaZBSohcqchoSBZKgKZlhMOXMoMXOMZGZvvRkqSOmHWZxSxZWHmOSrkRvvWPW
10
Output
3
WdYlPYGSNSGYPlYdW+pIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhiVWOelUjtrMyIp+ZassaZ+BSohcqchoSB+ZKgKZ+l+h+MOXMoMXOM+ZGZ+vvRkqSOmHWZxSxZWHmOSqkRvv+WPW
Answer
3
WdYlPYGSNSGYPlYdW+pIyMrtjUleOWVihRoZkUyXWuKuWXyUkZoRhiVWOelUjtrMyIp+ZassaZ+BSohcqchoSB+ZKgKZ+ll+MOXMoMXOM+ZGZ+vvRkqSOmHWZxSxZWHmOSqkRvv+WPW
Checker Log
wrong output format Expected string with length not greater than 139, but string length is 140.
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Because you split the string into 11 palindroms, not 10.
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You have split string into 11 palindromes, while k = 10.
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А объясните плиз, почему у меня рейтинг понизился? хотя если на прошлом контесте я 1069\2031 место с 1 задачей , а на этом  650\1324 с 2мя. потому что участников меньше ?
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да, в процентном соотношении у вас примерно одинаковое место на обоих раундах.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      А ещё количество зарегистрировавшихся не есть количество участников.
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I am new to code forces. can u tell me how to view others solution??
»
12 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
я давно хотел спросить у участников див2: зачем(!!!) сдавать решения, которые очевидно тлятся??? каждый раунд в див2 есть такие люди
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Капитан очевидность как бы намекает, что большинство из них, сдавая задачи, не знают, что они затлятся.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ну просто наверное надо хотя бы знать сколько итераций может сделать компьютер за 1сек, чтобы заниматься программированием
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Но это знать мало, нужно уметь оценить асимптотику. Вы сразу это умели?
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          ну когда я не умел это, я сдавал простецкие задачи на ифы, массивы и прочие стандартные вещи...

          ну и как бы, даже если не знаешь сколько итераций можно успеть сделать, после 1 взлома можно понять, что гнать 2 цикла по 105  не заходит по времени

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Ну до каждого по-разному доходит. Тем более, когда ничего рабочего придумать не можешь, можно и какое-то палево сдать - вдруг зайдет, хуже все равно не станет. Помню месяца полтора назад контест div-1, где на задачу Е заходил лоб(ну для Е действительно лоб: всего лишь сумматор, вместо авторского изврата), потому что тут на серваках за 2 секунды нормально зашел 1 млрд. не самых простых операций.
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    чтобы ломать другие такие же наивные решения? не?))
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Так оно и есть. Лично я так и делал, посылая решения в пять строк, которые проходят только претесты, за пять минут до конца, чтобы ломать "таких же как и я" во время контеста.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      да нет же, я бы в таком случае не спрашивал, именно сдают и потом не взламывают
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
My DP solution to problem E exceeds time limit, with O(n^2) complexity (n being length of the string). 

What is the correct solution supposed to look like?
  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    (c) Egor

    Let B[i] "Balance" of the position i - doubled amount of consostants minus amount of vowels in i-th prefix. Then the longest "good" substring, which begins at i'th position ends at the farest position j, such that B[j] >= B[i]. Count for each balance the farest poisition, where we can achieve it, then for each balance count the farest position, where we can achive equal or greater than it. Finally, iterate threw a string and for each position count the longest "good" string, which ends here.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    O(n^2) obviously will exceed time limit.
    Expected solution was O(nlogn) .
    One of the solution I saw, used Binary search . (Don't ask on what ;-) )
    Other used some kind of tree. Binary Indexed one. (I was never able to fully remember this thing. :( )
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    My solution. Of cource this code may looks better but I'm little stuped and can't realize short and obvious solution.
    First idea. Let's substitute vovels by -1, consonants by +2, and calculate the sum on a prefix. 
    Second idea. Let's find for any position the most length of correct string which started at this position. Of cource, it's the most distant element with a larger value of sum on the prefix.
    Third idea. Let's sort our array of pair <sum on prefix, position> (with element (0,0) - null element), and will support a pointer of last not used point in our array.
    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      we need to keep track of the first position in the string that has a cumulative sum less than the or equal to any given cumulative sum the first time it comes up. 

      Hmm, for non-negative sums, the first position is always zero. 

      Haha, the joke is on me:  I only needed to keep track of the first position of negative cumulative sums!  the array only needs to be 200,000 elements long; the length for any non-negative cumulative sum after N characters is always N.

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

        I said: for any position let's find the string with the most length which started at this position. What is it hard to understand? I can explain it in another variants, but I can't understand what's the trouble.


        UPD: I'm understand

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
after this contest Social Buttons disappered! Did admin forget to turn on all the stuff?
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как я понимаю в задаче Е решение бинпоиском по максимальной длине подстроки с последующим подсчетом количества таких подстрок падает на 32 тесте (WA)? Кто-нибудь может объяснить почему такое решение неверно?
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    baaab
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В этом то тесте хорошие строки есть вообще для всех длин от 1 до 5. А вот в тесте aabaaaabaa есть хорошая длины 6 (baaaab), 3,2,1, а длины 5 и 4 нету. То есть монотонности существования ответа как бы не наблюдается.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        baaa и aaab тоже "плохие" строки. Так что уже в примере baaab нет монотонности.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Точно, пардон ) Ну надеюсь тоже помогло автору вопроса.
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    если ты перебираешь длину, то очевидно, что у тебя функция не монотонна, то есть допустим у тебя сначала подстрока длины l хорошая, потом идет много много гласных, и она становится плохой, а потом идет несколько согласных, и она снова хорошая
»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Really nice contest......first three problems were really easy.....i should have solved them......got AC in only one.....misread one....got tle in other......it was a nice learning experience......

thank you for the contest... :)

waiting for the next contest and expecting a better performance next time..