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

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

Друзья, всем привет!


Буквально через пару часов состоится очередное соревнование - Codeforces Round 101 для участников Div. 2, но традиционно остальные могут поучаствовать вне конкурса.  Он был подготовлен небольшой командой авторов: я (NALP), Полина Бондаренко (Polichka) и Геральд Агапов (Gerald). Как всегда с нами были Артем Рахов (RAD), Мария Белова (Delinur) и Михаил Мирзаянов (MikeMirzayanov).

Немного об авторах: все мы учимся в Саратовском Государственном Университете на факультете Компьютерных Наук и Информационных Технологий на 4-ом курсе. Сейчас в свободное от соревнований и задач время сдаем зимнюю сессию :) Я составляю 1/3 от команды Saratov SU#2, а Гера с Полиной - 2/3 от Saratov SU#1. Мы бы хотели, чтобы наши раунды стали доброй традицией на Codeforces, и скоро вы вновь увидели нас в числе авторов.

Мы надеемся, что сегодняшние задачи понравятся всем участникам, и каждый займет заслуженное высокое место в итоговой таблице. Сегодня Вы будете помогать Деду Морозу, Снегурочке, Васе и другим персонажам. Все совпадения с реальными людьми случайны :)

Баллы по задачам сегодня распределены следующим образом: 500-1000-2000-2000-2500

UPD: Вы уже можете прочитать разбор задач

UPD: Спасибо всем за участие! Раунд выдался достаточно сложным, только один человек среди всех участников (включая Div. 1) решил все предложенные задачи - это akim239. С чем мы его и поздравляем!!

UPD: поздравляем Top-10 участников в конкурсе:
3. frp
6. hex539
7. not
10. ggbuaa
  • Проголосовать: нравится
  • +147
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
пусть этот раунд пройдет также хорошо, как CFR #100
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    Лучше как-нибудь по-другому =)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится
    Еще сделают задачу F на 3к  баллов что-то типа A+B и никакой длинной арифметики и прочих хитростей:-)
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Не пора ли опубликовать данный пост на главной странице?
UPD. Хотелось бы узнать разбалловку задач.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Видимо нет на главной, т.к нет англ. версии
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Чаще всего, когда сразу не пишут разбалловку задач, она стандартная. 500-1000-1500-2000-2500
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Good luck and have fun!)
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
У меня одного CF притормаживает?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо) Обязательно поучаствую. Успеха всем!
»
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Чёрт! Дед мороз всё-таки реальный человек??
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится


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

Почему я в Праге!? Опять я пропускаю контест! А во всем виноваты временные пояса...

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Потому что повезло. Меняю свой часовой пояс на твою Чехию.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Да. Действительно жалко таких людей как ты (тех кто живут в часовом поясе сильно отличном от России). Но, дело в том, что я вообще живу в Киеве, а сейчас попал в Чехию. Время соответственно чешское, выходит ждал контест только через час).
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Ты не понял. Я живу не в другом часовом поясе, а в другом дивизионе, потому и не пишу.

        Тебе же я хотел сказать, что Чехия за окном лучше участия в контесте.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Как бы вот.
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Понравилась задача D. Это должен был быть ответ на оригинальный пост.

»
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Three witches watch three Swatch watches. Which witch watch which Swatch watch!
»
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

я один как лох битый час в задаче B думал, что поле ограничено?

вечно не читаю условия нормально

»
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Господа, ну вот что это такое? Ну делать, что ли, нечего? Да еще и зарегистрировали прямо перед контестом. Смех смехом, а правила надо(хоть чуть-чуть) соблюдать. Не говоря уже об элементарном чувстве такта.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    какие конкретно правила нарушены?
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вероятнее всего, пункт 7(хотя не берусь утверждать), и - если формулировать пункт 8 более глобально - пункт 8.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      А почему они вне рейтинга стали?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Потому что у них одинаковые решения задач на контесте
  • »
    »
    13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    И пять человек из топ20 - серые (по крайней мере до системного тестирования). Я-то контест, конечно, слил, но все равно неприятно.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится
    А с каких это пор ЕдРу нужно соблюдать какие-то правила?
»
13 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится
Мне кажется что примеры к задаче 
В не правильные.А именно 3 и 4 примеры.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Третий пример:

    Камень летит параллельно оси Y, минует 3 строки, после чего успешно падает на квадрат с номером 5 (критерием успешности, как указано в задаче, считается нахождение камня строго внутри квадрата, не касаясь его рамок). Таким образом, ответ: 5.

    Четвёртый пример:

    Камень опять летит параллельно оси Y, минует 2 строки, падает ровно на границу квадратов 3 и 4, таким образом не давая нам разрешения утверждать, что попал в квадрат (по условию задачи). Следовательно, ответ: -1, как и во всех случаях, когда камень не попал в квадрат.
    Так где ошибка в примерах-то?

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

      можете еще раз объяснит 4 пример: A=3 X=0 Y=7.По условию классики представлены являются квадратами тогда должен быть, если камень  лежит на границе и X=0, остаток от деления Y на A равен 0.Объясните пожалуйста  в чем я не прав!)

      Я понял прошу прощения)

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Камень, упавший на границу квадрата, не считается попавшим.
        (именно так в условии написано)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Под границей подразумевается любая точка периметра, а не только углы.
»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Ну где, где он? Где же, когда он случится? Простор для взломщиков.
Зачем такие сильные претесты во второй задаче?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не такие уж они и сильные, например, не было претеста с точкой в середине первого квадрата.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А можно было ломать на целочисленном делении пополам? А то я так и побоялся проверить.
»
13 лет назад, # |
Rev. 3   Проголосовать: нравится +25 Проголосовать: не нравится

по ходу, результаты контеста были сфальсифицированы 

UPD ура, ЕдРо исключили из избирательных списков!


»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
В задаче D нужно разбегаться обязательно с точки x[i] - p[i], или можно начать разбег движением в обратную сторону, а потом развернуться в сторону трамплина? Хотя мне ответ на этот вопрос уже сильно не поможет - я задачу за 9 минут не решу.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    вроде клар был, что да, разбег нужно начать именно там
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Я клар в момент его появления прочитал бегло. Ту часть, что про направление, в условие задачи добавили, а ту, которая про точку начала разбега - нет...
»
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
10 тест задача С - я тебя запомнил!
»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Что за 7 претест в Е?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    После конца контеста можно смотреть тесты. 
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я знаю. Просто мало ли, не терпится узнать, как лечится WA 7 =)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Просто просмотр тестов был введен, чтобы избавить топик, посвященный контесту, от одинаковых вопросов "Дайте тест Х для задачи У".
»
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
как Е решать?
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

че то какой то сложный раунд

»
13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Я, конечно, понятия не имею что там не так в моем решении на задачу D. Я даже понятия не имею, правильно ли я понимаю условие. Но больше всего доставило то, что во время раунда CF сначала просто нагнулся, а потом в последние полторы минуты я не мог сделать посылку решения. Я нажимал "Отослать", и ничего не происходило. Я просто оставался на той же странице.
TopCoder 2 : 0 Codeforces
  • »
    »
    13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +90 Проголосовать: не нравится

    Ничего

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Петросян Петросяном. А я и сам так считаю. Против статистики не попрешь.
      Задачу понял правильно. Решил правильно, но когда удалял прыжки из отрицательных точек, не изменял нумерацию в одном месте. И так уже 20 раундов подряд. Мне действительно пора не пенсию.
      • »
        »
        »
        »
        13 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +14 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Не понимаю, если решение неправильное, то надо винить только себя.. при чем тут кодфорсес? То что ты не смог отправить из-за каких-то неполадок это конечно неприятно, но не стоит об этом кричать и тыкать пальцам в кф. Я уверен что команда кодфорсеса делает всё возможное и невозможно чтобы для участников каждый очередной раунд прошел как можно лушче, для всех участников в равной степени.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Если не говорить о проблемах, можно подумать что всё нормально...

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, абсолютно согласен, но есть разница между говорить и "упрекать". Думаю "...TopCoder 2 : 0 Codeforces..." звучит именно как упрек, подначка.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      тем более, див2 раунд
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я вроде не писал, что виню CF в том, что у меня не прошло решение. А вот то, что полторы минуты я просто не мог послать решение меня немного разозлило. Я даже вкладку в браузере закрывал и открывал новую. Я не перезапускал браузер, а решение нормально отправилось в дорешку.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +17 Проголосовать: не нравится
        Если у вас Windows, то возможным решением было бы перезагрузить ОС, или на крайний случай переустановить...
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +20 Проголосовать: не нравится
          А если у вас Linux... Срань господня да вы же линуксоид, тут уж ничего не поможет :D
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    Ты когда регистрировался, надо было читать условия. В них сказано, что вы можете принять участие, если вы "не будете сильно расстроены, если что-то пойдёт не так" :)
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
How to solve problem C?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I used greedy algorighm, but I don't know if it is correct ot not. (Passed pretests).

    Sort people by ai. // fail() means that there is no solution
    We will have array res, where we will keep name of person, his height.
    Then check: if (a1 > 0) fail();
    h1 = 500000;
    for i = 2..n {
    if (ai ≥ i) fail(); 
    if (ai =  = ai - 1) {
    put this person after previous (remember that it may be not last place!), hi = hi - 1
    } else {
    put this person at the (ai + 1)th place, hi = 500000 - ai
    }
    }
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I have the same idea but can't prove it in the contest, now it seems correct.

      But there is an issue, will 500000 be too small? I guess 5000000 would be safe.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        We have only 3000 names, so minimal value is 500000 - 3000 = 497000.
        If I am not mistaken, 5000 will be enough.
»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Please make the statements more clear.. It take a lot of time to understand what is asked in the problem...
»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
что за баг: нажимаю отослать, меня переводит на страницу моих посылок, а отправки нет, и только после нескольких обновлений она появляется
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Подтверждаю наблюдение, проявлялось еще на #100. Правда, не уверен, что это баг.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я один не могу написать комментарии нормально? У меня какие-то кракозябли вылазят в текстовом поле.
»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
It's a very good contest with very good questions.
Thank you
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
what hit me?
»
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Задача Е. Как объяснить правильность 3-го теста из условия. Расчистить можно все дорожки, количество будет равным. Количество простых путей между парами домиков будет равно единице. (кроме того будут, конечно, и не простые пути, но условию это не противоречит)
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Cудя по этому тесту петли надо было откидывать. 

    Путь называется простым, если все домики на пути попарно различны.(внизу задачи сноска).










    5 6
    1 1 S
    1 2 M
    1 3 S
    1 4 M
    1 5 M
    2 2 S
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      О_о
      ну тогда понятность условия оставляет желать лучшего
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Согласен. По моему мнению, петли выкидывать не надо, если с учётом их у нас получается ровно один простой путь, а сколько у нас «не простых» путей (т.е. включающих петли) — не важно. И мне очень хотелось бы увидеть цитату из условия, утверждающую обратное.
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          вот я тоже так думал, полконтеста решал и даже на время забил на контест от безысходности :(
          потом, правда, вспомнил про задачу С и по-быстрому придумал и написал
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Насчет понятности условий. Вот задача из Хорватских олимпиад.
            Или мне мозгов не хватает или....? НО Я НЕ МОГУ ПОНЯТЬ КАК ПОЛУЧИЛСЯ ЭТО РЕЗУЛЬТАТ ХОТЬ УБЕЙ. Так, что эта олимпиада даже очень хоршая по пониманию условий. Кому интересно почитайте.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              как раз тут, по-моему, все понятно
              только не совсем ясно, можно ли делать произвольный циклический сдвиг с этой последовательностью или только на один
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Вот именно. Ответ [1,5,4,2,3] не получается ни как.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Не надо путать элементы последовательности и их номера.
                  Все получается.
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                На один, наверное.
                Иначе бы
                1) это было специально уточнено;
                2) Мирко недостаточно было бы указать последовательность в примере, был бы необходим шаг.
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Хорватских
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        думаю для этого и дали третий семпл, чтобы можно было точно понять условие...
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
унылый раунд
»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
контест для меня закончился на 12 минуте... прискорбно
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
An interesting discovery: B is such a kind of problem, even you know lots of submissions probably would be failed in the system test, it's hard to come up with a vital test case in a short time.  That's very frustrating. 
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yeah. Many people failed the system test.
    And if you want to hack them, you need to understand their codes totally.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто там в тройке призеров?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Мммм, тестирование повисло?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
завалилось всё таки моё решение по D, которое не учитывало того что в отрицательном напрямлении нельзя прыгать на трамплине :(
»
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Thanks for the quick editorials :D
»
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Great contest! Thanks Codeforces! A veryyyy small problem caused me 2 WA! The size of an array!! By the way problems were great! Specially E. I love graph problems!
»
13 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится
Большое спасибо авторам задач за хорошие задачи, очень понравилась 141E - Большая чистка. Было бы здорово если уровень последующих онли див2 останется таким же... хорошая тренировка.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится
    К сожалению, немногие так считают. Лично я придерживаюсь мнения, что контест не должен быть простым, каждый участник должен подумать и потрудиться. Но мало кто со мной согласен.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Хороший аргумент это то, что никто не решил всё и все задачи были решены)
»
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
For Problem E ... I separated all the santa edges and elf edges and then used disjoint set to make the tree.i chose one edge from santas side and one edge from the elfs side and kept on iterating and toggling.. if the edges count of santa and elf is same and the total is n-1. Then there is a possible solution.  but I got WA on case 30.. 


Can anyone tell me why my code fails?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
can someone explain solution for problem C ? i couldn't understand the solution from tutorial... failure condition is straightforward, but how to adjust the heights ?
  • »
    »
    13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    After sorting:
    First, let h1 = n (or what number you like as long as it is not less than n).
    At step i, assign n - ai to hi and decrease hj by 1 if hj ≤ hi (obviously, these changes do not affect previous order). Therefore, after step i, we can maintain a list of numbers from n - i + 1 to n.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      hi,
      can you tell why your solution works ? idea behind it.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        We process from the head of the queue to the tail.
        Now, instead of choosing values, let's think about choosing ranks for these elements (from 1 to n, 1 is the biggest). Then, we can easily choose value for an element if we know its rank.

        First, there's only 1 element, of course its rank is 1.
        With element i, we know it must be smaller than ai elements, so its rank is ai+1. Inserting this element into the list we created so far will increase the ranks of elements whose current ranks are greater than ai.
        For ex: let the a[] after sorting is {0,1,1,2,2,3}
        Array rank[] after each step (bold numbers are whose ranks are increased after each step)

        Step 0: 1
        Step 1: 1,2
        Step 2: 1,3,2
        Step 3: 1,4,2,3
        Step 4: 1,5,2,4,3
        Step 5: 1,6,2,5,3,4
»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
I resubmitted my C and Passed!
count differences between these two codes!
http://www.codeforces.com/contest/141/submission/1024571
http://www.codeforces.com/contest/141/submission/1022993

can u rejudge it please ?!
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится
    devils13. I've submitted your TLE code, and it actually passes.
    Codeforces was so slow today and I think your code deserves to be rejudged.
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      I think the reason is judging a lot of submissions at the same time in system testing might cause a little difference in execution time (1920ms is pretty close to time limit).

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

        the order of my code is n^2logn which is should pass when n = 3,000. u r right it is very close to 2 secs, but my code passes in less than 2 secs.

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

    Process time is not a constant on any operation system, but it could vary a little. Typically 3-10% is acceptable accuracy. In particular on this all author solutions are 2-3 times faster than a time limit. Actually each contest we have some solutions which work around a time limit. Some of them pass system tests, some of them not. But anyway, writing such solution is a risk, because you can't get will it pass tests or not.

    We do not rejudge such solutions, it would be unfair to other participants. We apologize for the inconvenience.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      ok thanks so much!, but I hope to c codeforces avoid such problems in the future :)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Codeforces has not problem. It is NOT a problem. All solutions tested in real operating system, on real CPU. The world is not ideal. And if you try to run the same solution on the same data 100 times, the running time will be different - "Typically 3-10% is acceptable accuracy"
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          no it is a problem, if the servers strong enough it will pass cause my code in the worst case makes 31,294,092 operations. topcoder servers finish them in less than 1 sec. my laptop finish them in less than 1 secs!
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

            can you please tell us how you get such number of operations? what if we replace set with sort? the number of operations will be the same? I think you just have not strong enough test data. Codeforces servers are very fast as i know. 

            upd: with sort your program works only 340 ms, but it is still O(n^2 * log(n)). The constant factor is very important. BTW dont't you forget about N^2/2 calls of "operator new" when you use set? There is more optimal - O(n^2) solution, so there is no any problem.

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

              as I know that the set implementation in the c++ is a red-black tree, which takes log(n) in the insertion. so my code is O(N^2Log(N)) and N = 30000, So N^2Log(N) = 3000^2Log(3000) = 31,294,091.292476962. 

              I know that it is an approximate number and not a 100% accurate. 
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится +1 Проголосовать: не нравится
                see at your modified solution. both variants works O(n^2 * log(n)) but second is 6 times faster.
              • »
                »
                »
                »
                »
                »
                »
                »
                13 лет назад, # ^ |
                  Проголосовать: нравится +3 Проголосовать: не нравится
                don't you know what O(log(n)) means? it can be 2 * log(n) can be 100000000000 * log(n). set insertion is very slow: 1 call of "operator new"(you can google how it's slow) and then (for n = 3000) not only 12 arithmetic operations, but recursive calls, complicated tree rotations and so on... can be 100 * 12 operations, i dont know for sure
            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              There's an even more optimal O(N) solution too.

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится
        It's better to compete in winter cause CPUs work faster in winter than in summer. :D
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Similar issue happened to me once in TopCoder, my Passed System Test solution during the contest is getting TLE in the practice room. :)
»
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
А почему нет виртуального раунда 101?
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо за интересные задачи!