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

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

Здравствуйте, уважаемые участники сообщества Codeforces!

Начиная с Codeforces Round #327, я буду координировать подготовку регулярных раундов и прочих контестов, которые проводятся на платформе Codeforces. Обещаю приложить максимум усилий, чтобы улучшить качество подготовки контестов, хотя это и будет проблематично сделать — Zlobober установил высокую планку. Давайте ещё раз поблагодарим Максима за хорошо проделанную работу!

Завтрашний раунд проводится на задачах Московcкой городской командной олимпиады по программированию среди школьников. Пусть вас не смущает, что это школьное соревнование, — среди участников есть золотой призёр IOI 2015 и несколько кандидатов в сборную России этого года, поэтому мы постарались сделать все задачи интересными, а некоторые ещё и сложными. Уверен, что каждому из вас должна понравиться хотя бы одна задача предстоящего раунда.

Задачи были подготовлены коллективом московских авторов в составе (список пополняется): Zlobober, romanandreev, meshanya, wilwell, glebushka98, timgaripov, thefacetakt, haku, LHiC, Timus, Sender, sankear, iskhakovt, andrewgark, ipavlov, StopKran, AleX. Руководство подготовкой осуществляли ваш покорный слуга GlebsHP и председатель жюри олимпиады Андреева Елена Владимировна.

Отдельно благодарим Delinur за перевод условий на английский язык и stella_marine за вычитку.

В каждом дивизионе будет предложено для решения пять задач, разбаловка будет опубликована позднее (не будем нарушать эту традицию).

UPD. Время раунда. Обратите внимание, что во многих странах мира этой ночью переводят часы, а в России не переводят — не пропустите случайно раунд :)

UPD2. Обратите внимание, разбаловка как бы намекает, что надо прочитать все задачи! Div1.: 750-1000-1250-1750-2500 Div2.: 500-1000-1750-2000-2250

UPD3. Результаты раунда и разбор будут опубликованы позднее, когда завершится официальное соревнование.

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

  1. Endagorion
  2. JoeyWheeler
  3. sdya
  4. RAD
  5. -XraY-

UPD5. Появился разбор.

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

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

Nice... :/ A school contest that lots of students can't join in it...Cause we are at school that time :/

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

Good luck!

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

Scoring distribution?

Also, gotta love weekend contests. ;)

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

What's the duration of the round? It is 2 hours on the list of upcoming contests, but the email says it will be 2.5 hours.

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

Welcome aboard! Great deeds await us.

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

Good luck GlebsHP

and Good Job dalex !

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

    It will be good job if I bring back my yellow.

    Actually I'm surprised that nobody noticed that, I was just looking through recent actions and saw that Gleb had edited Mike's blog...

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

Now Zlobober will enter the contribution list. BOOM straight to the top.

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

"Уверен, что каждому из вас должна понравиться хотя бы одна задача предстоящего раунда." Ловлю кароче на слове. Если мне не понравится ни одна, то вы можете искупить свою вину подписавшись на мой математический паблос http://vk.com/turingprekols .

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

I realise that number of contest that made in this time increase why??? some of us have school and others have a work some times i missed lectures to enter the contest i think it is good to make it around 7 , 8 o'clock after finishing our work in order not to be busy

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

    Tomorrow round will be held using the problems of Moscow team olympiad for high-school students.

    Obviously, at the same time.

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

How come AleX's contribution be minus when all his blogs and comments got no downvotes?

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

In the last three contest my rating is decreased .I hope this time my rating will be getting up :D

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

Hope for the best :D

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

Heartily Welcome & All d Best GlebsHP

Thank you Zlobober for the great job u have done! :-)

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

Now it is time to rest,but start to brain storming. Good Luck for every one.

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

very long questions :(

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

Omg it started on 9AM not on 10AM local time.

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

Ну и как искать максимальное независимое множество в графе сравнимости?

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

    Как этот граф нормально строить в таких ограничениях? Стандартная штука с n типами разделителей, кажется, не должна влезать.

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

      Я Ахо-Корасиком строил за O(|S| + N2). Идея в том, чтобы хранить терминальные ссылки на вершины, в которых кончаются строки, а потом пропустить каждую строку через АК. А потом пытался сделать какую-то жадную фигню. Конечно, не получилось. 13850184

      Так что насчет графа-то?

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

        Я умею размер ответа по теореме дилворта вроде. Написал тупость за n*len, получил локально тл и забил на задачу.

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

      бесит задача(

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

      А ответ-то как восстанавливать?

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

        Становимся в верхние элементы цепей, если из какого-то из них достижим другой, спускаемся им вниз. Это O(n3) в худшем случае, реально сильно быстрее наверняка.

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

          Ужас, а слона-то и не приметил.( Вот так доказываешь в кружке по математике теоремы, а задачи все равно не сдаются!)

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

        По теореме Кёнига; собственно в статье на вики это написано.

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

          Восстанавливать можно абсолютно также, как и в задаче о поиске максимального независимого множества в двудольном графе: после поиска парасочетания обе доли разбиваются на достижимые и на не достижимые. После этого из этих четырех множеств легко получить ответ.

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

    Так а как его строить кроме как Корасиком? Я написал, получил ВА8 из-за какой-то дебильной баги, но на претестах работает 2600мс и еле-еле упихивается в ML, на систестах наверняка бы и упало. Собственно, так почти у всех, кто сдал эту задачу, и произошло

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

      Скорее всего, никак. Если бы ограничения были более дружественные, можно было бы суфф структурами. А что плохого в Ахо-Корасик?

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

        А как учитывать вершины-концы строк, достижимые по суффиксным ссылкам?

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

          Я просто сказал, что учтем самую нижнюю достижимую по суффссылкам, а потом в конце за n2 все обработаем: если i выше j в дереве на суффссылках, то добавим соответствующее ребро

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

          Не понял вопроса.. Можно подробнее?

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

            Если для каждой вершины, посещенной в Корасике, искать все терминальные сверху по суффиксным ссылкам (если хочется в графе проставить все-все ребра), то это будет O(len * n), что уж точно не пройдет по времени

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

              Ну можно преподсчитать для каждой вершины term[v] — ближайшая достижимая терминальная по суфф ссылкам, а потом обойти терминальные в прядке уменьшения длины и cnt[term[link[v]] += cnt[v]. Ну и понятно, что когда строку пропускаем через автомат вместо cnt[v]++ делать cnt[term[v]]++. Чтобы в итоге чисто с терминальным поддеревом работать. У него уже размер небольшой.

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

                Да-да, я что-то такое делал: предподсчитал term[v], потом когда скармливал строки, просто ставил ребро из i в stringNum[term[v]], а потом еще какие-то ребра добавлял, как ниже написал

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

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

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

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

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

            Такая длина ввода была выбрана нами для того, чтобы суфф массив за не проходил, а также чтобы отсечь решения за O(nL). Авторское решение было с Ахо-Корасиком, написанным с помощью BFSа. Но так как TL был поставлен как минимум в 3 раза от авторского(а у ikatanic вообще в 6 раз быстрее ограничений), то должна проходить и любая рекурсивная реализация.

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

              А зачем отсекать суффиксные структуры в этой задаче?

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

                Потому что смысл в очередной задаче вида "о, а давайте напишем любую суфф структуру и не будем думать"? А так красивое и простое решение, чтобы придумать которое достаточно знаний ЛКШ группы B-A'.

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

                  то есть, давайте напишем Ахо-Корасик и не будем думать — хорошо, а любую суф структуру — нет?

                  Я уж молчу про воспользуемся "общеизвестными" теоремами из теории графов и не будем думать.

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

                  Эм, для начала задачу нужно решить. На наш взгляд решение данной задачи очень красивое и нетривиальное, состоит из двух частей (построение графа и применение теоремы Дилворта). Например наши лучшие школьники почти с нуля придумали вторую часть решения, но граф строили за , потому что не придумали как быстрее. Не понимаю, чем вы недовольны — для вас задача слишком простая или слишком сложная??

                  PS Мы специально не валили никакие линейные структуры данных. Если они у вас работают долго — неудача.

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

                  Да хорошая задача. Кому-то просто надо попробовать порешать задачи НЕ на строки, а не бомбить с того, что в Е просят Дилворта =)

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

                  ====================================================

                  Ну, моё недовольство касается двух пунктов.

                  1. Отсечение суффиксных структур, обоснованное по сути тем, что авторам они не нравятся. Вот вы говорите, что не отсекали специально линейные структуры, а у вас есть хоть одно решение с ними? Рискну предположить, что нет, т.к. специфика их такова, что константа как по памяти, так и по времени будет минимум в два раза больше при той же ассимптотике.

                  2. Существенный упор на "широко известную в узких кругах" теорему. Ну, туда же идут задачи, которые совсем тупо решаются если применить БПФ, дерамиду, автомат или прочие штуки, которые все умеют, а я — нет.

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

                  Ну так пусть перестанут их давать на кф :(

                  Третий контест уже с последней задачей про строки за последнее время! Вот отвлекаюсь на них и не могу насладиться нормальными задачами.

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

                  Чувак, ну признайся уже, тебя бомбит, потому что оказалось, что есть задачи на строки, которые adamant не может решить =)

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

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

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

                  =========================================================

                  Вообще удивлен, что к этой задаче есть претензии.

                  Почему отсекать решения за и O(Ln)?

                  1) Они асимптотически медленнее. Кажется, все спортивное программирование об этом.

                  2) Хрен с ней, с асимптотикой — они реально, блин, медленнее в разы!

                  Почему мы не сделали так, чтобы линейные решения с суфструктурами проходили? Занятие весьма бессмысленное :) Есть решение, которое гораздо проще по набору используемых техник и которое в разы быстрее. В любой задаче есть практически неограниченный спектр решений, совпадающих с предполагаемым по асимптотике, но имеющих бОльшую константу. Если вы считаете себя сумрачным гением некоторой техники, которая позволяет писать несколько более медленные, но гораздо более клевые решения, это целиком и полностью ваша ответственность, чтобы ваше решение уложилось в ограничения; Заколачивать гвозди микроскопом тоже надо уметь.

                  Наезд на теорему Дилворта вообще носит характер "вот козлы, дали задачу на теорию, которая мне неизвестна", тут комментировать не буду.

                  Одна из самых клевых задач за последнее время, имхо.

                  PS Мы на прошедшем четвертьфинале совершили ровно такую же ошибку из разряда "горе от ума". Ну захотелось нам использовать подъем сетов по суффиксному автомату вместо префикс-функции, ну словили мы ТЛ. Пойду-ка я наеду на жюри, что такое клевое решение не прошло :)

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

                  ============================================================

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

                  Я, кстати, не зря упомянул БПФ. Была вот недавно div. 1 D (кажется, твоя?), которая совершенно тривиально сводилась к нему. Ну, БПФ мне было известно только в самых общих чертах, я скопипастил его с е-макса и сдал задачу. Тогда мой наезд на БПФ был столь же бессмысленен?

                  Если вы считаете себя сумрачным гением некоторой техники,

                  1) Такое ощущение, что здесь снова откуда-то убеждение, что это просто моя личная обида. Да нет же, я строковую часть вполне спокойно написал с помощью АК (и я даже считаю, что это наиболее клевое решение из возможных). Просто я внутренне нахожу отсечение суфф структур неправильным, ведь идейно по сложности решения с ними не сильно отличается от такового с АК, может даже напротив они сложнее. Для меня это что-то в духе того, чтобы зачем-то отсекать от (т.е. несжатие координат от сжатия в ДО).

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

                  Существует суффиксный массив за линию, утверждается, что он работает с хорошей константой и маленьким overhead-ом по памяти. статья и реализации.

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

      Авторское решение с Ахо-Корасиком ест 200 мегабайт памяти, по-этому ML был 512. TL был выставлен более, чем в 3 раза от авторского. Если вам приходится так все упихивать — то возможно вы что-то делаете не так...

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

After Mathematics and Physics problems in codeforces rounds...

coming soon: chemistry problems in codeforces

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

    I hate math and physics problems too but the one about Chip and Dale is easily solvable by binary search + calculating distance between two points.

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

      I had to solve triangle using cosine theorem and then use ternary search (search for minimum of function). Does the problem have simplier solution?

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

        Here is my solution:

        if it is possible to reach to the destination point at some time T1, then it is possible to reach there for any T2 > T1, since you can just stay where you are (you are always faster than wind so it can't force you to leave your position). So with binary search you just have to check whether it is possible to reach the destination in exactly T seconds. To check that at first calculate the position to which wind will bring you if you will not move at all and then check whether you can get to destination from that point in T seconds (sqrt(dx * dx + dy * dy) <= T * u).

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

          LOL, me so noob %)

          I've solved the triangle and found O(1) solution for the case wind doesn't change, and then used search among angles of movement before wind changes :)

          Also, I'm quite sure, that it is possible to find O(1) solution for whole problem, but it requires mad_math_skillz*long_time

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

            Also my current solution gives information about direction to fly before and after wind changes. It would be pretty if problem required it in output %)

            btw, thank you, aram90

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

            I'm pretty sure I have an O(1) solution. Coded after the end of the contest, working for the samples. Waiting to be able to submit it. Anyway, the idea:

            First solve it without wind change. Basically, you need to set your direction so that your net velocity points straight to the target. If you draw some vectors, you'll see that you have two sides and the angle opposing the longer sides in a triangle and you need to figure out the third one. As sur said, you can do this with the cosine theorem (or you can forget easy solutions and instead find the intersection of a circle and a line like me...).

            If solving this for the first wind velocity results in a time needed that is greater than the given T, you know you'll reach the target after the wind change.

            For this case, consider a coordinate system "fixed to the air", i.e. consider a system where the wind's effect is replaced by the goal point moving in the direction opposing the wind's velocity. Now look at the path of the goal point. Before time T, it's moving with some velocity, reaches some point, then changes its velocity, and somewhere after this change is the time when you can reach it.

            But at this point, the weird movements at the start don't really matter. It's the second movement you want to calculate with. But it only starts this after T. So how do you make it simpler? You pretend that it was moving in the same straight line before T.

            So you move the goal position by the distance it would cover with the first velocity until T, then "wind back the clock", pretending it had the SECOND velocity all along. You set the goal position to this new point. Take care when considering the direction of the wind, its opposite, and subtraction of the opposite... If you have the V and W vectors as given in the input, and G goal position, its new position is G + (T*-V) — (T*-W) = G + T*(W-V).

            This problem will be equivalent to the original, because if you consider it as the "goal point moving", it's in the same position at the same time when you can reach it. And now you can solve it with the previous method.

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

            And yup, got AC for O(1) after some debugging: 13860359

            Solving it for no wind change by intersecting a circle and a line using an ugly quadratic equation. The interesting part is the rest — modifying the parameters to find the intersection when the wind does change as described in the long comment.

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

          Lovely soln :)

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

      Please tell me how. My binary search solution have got WA on pretest 4.

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

    Cool, looking forward to it.

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

    Chip has two recessive genes for blue eyes and Dale has heterozygous brown eyes. Meanwhile Dale has the gene that makes it impossible to roll his tongue on the same chromosome.

    Dale and Chip have a litter of little rodents together. Take as input the name of their baby chipmunks and the probability of DNA crossing over during meiosis. Give as output the chances that a mutation in any given codon will switch an amino acid and give the baby chipmunks purple fur.

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

Div2 B was exactly same problem came in ACM ICPC Dhaka Regional 2014. That's why people from Bangladesh could solve it earlier.

However, Problem set was very much enjoyable! Thanks to the setters! :)

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

    hahaha !! that's right !!! the only difference was we had to replaces a with b in ICPC Dhaka regional 2014 and today we had to swap.

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

    Does it actually matter?If the problem was C/D then it would matter.I think none of the coders could use their previous code.And problem B is never that much difficult.So it doesn't effect that much because most of the coders who can solve B always they will take just few minutes to solve it.

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

well, I got really stuck on that Div2 C.... Probably sohuld have just started to solve next problems

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

Div2B WA in pretest 1?

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

Div 2 B WA in pretest1?

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

C has very weak pretests

3 3
1.2
1.2
333

Is a nightmare.

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

    I thought the nightmare was something like:

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

      Those are the easy cases for the correct solution. The tricky corner cases are when the 3 paths intersect on a tile such that it contains '1', '2' or '3'.

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

        Isn't there just two cases?:

        — Connect any 2 pairs of components with shortest routes

        — Connect all 3 components to the same free cell with shortest routes

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

    The answer is 0.right?

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

    Oh come on, I said to myself "I will handle the 0-case at the very end", and forgot it, of course. Nightmare.

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

    "It is guaranteed that initially it is possible to reach any cell of any state from any cell of this state, moving only along its cells."

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

      I hacked with this test, so it must be according to the statement. And my common sense tells me it obeys what you said as well.

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

        Ohh never mind, I thought the two 3s on the top were part of the map, sorry.

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

Not sure if I'm the only one who didn't like the problems :)

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

    Pretty sure you're not alone. I don't like it either but that's just because they are quite difficult for me. The problemset itself is quite nice.

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

      My C also failed the system tests.. now I totally hate the problemset :P

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

How to solve Div. 2 C?

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

    by coding of course

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

    My solution was based on the following observations:

    1. a_0 and a_n are always stable.

    2. b_i = a_i if at least one of the adjacent values is the same as a_i. Consequently, b_i = 1 — a_i if both of the adjacent values are different (for i in [2,n-1]). Moreover, a_i will be stable if it is part of a continuous subsequence of the same values.

    3. Let A be the string of values given. In this string, there exist at least two stable values (namely the end points). Let S be a substring of A such that the end points (p and q) of S are the only stable points in it. Without loss of generality, assume that p = 1. Then, the substring S' formed by removing the these two points must be alternating (either of the form 0101...0101 when q = 0, or 0101...010 when q = 1 ). In the first case, S' will eventually become 1111...111 as consequence of the previous observation. In the second case, S' will become 111...000, where the amount of 1's and 0's are the same.

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

      I almost did the same.But i don't understand why i got WA in pretest 6.Can you check what did i miss here? My Code By the way,is there any case for which the answer will be -1 ?I didn't find anyone!

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

    The longest alternating sequence is the answer. If it starts and ends in same digit, then every digit in between becomes that digit. Else, if it starts and ends in different digit, then there are equal numbers of 0's and 1's serially.

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

    Basically there are stable and unstable intervals. If anywhere in the segment you find 00 or 11, then they are not going to change, but any segment such as 010 or 101010 is going to change, depending on what stable intervals they are surrounded by.

    Finding the intervals is a nice application of regular expressions,

    segs = re.findall('(.*?)(0{2,}|1{2,})', s)
    

    This splits something like 110010101110100 (I added doubled the ending coordinates, as they are stable too) into [('', '11'), ('', '00'), ('1010', '111'), ('01', '00')]. From there you just have to change the unstable '1010' into '0011' and '01' into '10' and you're done.

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

      ..and another way with regexes using lookaround: if repetition "1 - NUMBER_1, NUMBER_1"+ is surrounded with "NUMBER_1,NUMBER_1" from left and with "NUMBER_2" from right, then it changes to "NUMBER_1" * (length_of_repetition / 2) + "NUMBER_2" * (length_of_repetition / 2). e.g. 13873903

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

how to solve div2 E? Как решить div2 E?

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

For Div2 D can anyone show me how sample case #2 works? Cant understand how 11.547005383792516398 come out. I think it should be 20/sqrt(3);

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

I think we will see a lot of WA on the fourth task.

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

Div2 C....I thought its my lucky day when reading till second last paragraph of a problem

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

    Haha me too :P

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

      Can you find any case that answer "-1"?I puzzled it for a long time

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

        My solution without "-1" case was accepted on pretests. Final sequence always exists.

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

          You shouldn't consider that fact a proof.

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

            I ran my slow solution for all binary sequences from 0 to 2^20, not a single one got stuck. Enough of a proof?

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

              Of course it is not enough for a proof, it may work to feel save in the middle of a contest, but it wasn't a demonstration at all. BTW, the proof is not hard.

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

hi all this constet was one of the best contest that i participate in it :) ty all hf;)

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

Thank you very much!This is my first contest in CF.I really have a happy time!Expect next contest!

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

А можно поподробнее, когда ждать результатов? Ориентировочное время-то известно наверно?

Судя по информации здесь, результаты будут не раньше 4 дня.

Раз такое дело, почему бы не проводить раунд по официальным соревнованиям так, чтобы он заканчивался примерно в то же время?

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

    тогда теоретически участники оф соревнований могут слить условия до начала раунда на кф

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

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

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

    Потому что мы наиболее свободны в середине контеста. В начале решаем какие-то внутренние проблемы, а в конце печатаем дипломы и т.п.

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

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

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

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

        Я отвечал на вопрос о времени проведения раунда.

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

          А давай теперь на вопрос о результатах :) Люди интересуются, почему бы не сообщить их участникам пораньше, на этот счет же есть официальная позиция наверно?

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

When will the closing ceremony finish?

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

    Yeah I too is waiting for Editorials.

    Please feed us with editorials so that I can go back to sleep!

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

Why Div.1C is C ?

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

Div 2 C >>>>...> The Great Wall Of China (For my rating). :-( When can I cross it?

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

problem c ,, div 2 , when the answer would be "-1" ,, i think there is no possible case where the answer is "-1" ,, is it ?!!

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

    The answer is never "-1". It can be shown easily by induction (a1 never changes, and if numbers a1, ... ak never change after k steps, then ak + 1 cannot change after k + 1 steps).

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

When is the closing ceremony of the official competition? (How many hrs from now?)

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

How to solve Div2 C other than simulating?

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

    Notice that any substring containing more than one consecutive zeroes/ones will remain as it is, so the only case we have to think about is 10101... If you notice carefully, after each move the leftmost and the rightmost digit of this substring will become safe (it will become equal to whatever is beyond it), so you can easily come up with a O(N) solution. So we just have to update cnt as max(cnt,(length of unsafe substring+1)/2))

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

Div-2 C >>>> The Great Wall Of China..(for my rating) :-( When can I cross it?

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

Расскажите D

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

    Две динамики по типу рюкзака. В первой dp[i][j] = максимальная сумма для i элементов, которые мы можем поставить в конце первых k элементов не более чем за j операций. Во второй dp2[i][j] = минимальная сумма для i элементов, которые мы можем поставить в начало последних n - k элементов не более чем за j операций. Ответом является минимум из всех возможных сумм .

    То есть, мы берем t каких-то элементов из первых k, и заменяем их на какие-то t элементов из последних n - k. Для этого сдвигаем и те, и те к "границе", и за t2 операций свапаем их.

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

    А у меня была динамика dp[len][m][s] — минимальная сумма первых m элементов в перестановке, которую можно получить из первых len элементов , потратив на это s обменов. Переход в такой динамике — O(1), ответ будет в dp[n][k][0..s].

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

Looking at the hacks, looks like DIV2D / DIV1B will give many WAs..

What was the hack that dreamoon_love_AA used four times?

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

Кто-нибудь получал ответ 3.7657803760 в Div1B?

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

    Да, это вроде если ветра во второй части пути не в ту сторону посчитать.

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

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

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

      Я думал, что так делать не оптимально, но до сих пор не понимаю почему (

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

        Ну например, если в двух частях пути ветры будут (-20, 0) и (20, 0), то они могут уравновеситься в итоге, и поэтому выгоднее будет их игнорировать, а не тратить время на борьбу с ними. Да и вообще в оптимальном ответе, скорость дирижабля (относительно воздуха) должна быть постоянной в течение всего пути.

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

    У меня получился 3.6689300537

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

Tasks were ok, the idea for the second is pretty standard, the third task is cool, the fourth is good, but I couldn't solve it on the time. The fifth task I didn't understand.

But the texts were awful. In the first task we have one not important part, in the thrid task the main thing wasn't on the right place ( ai=0 or ai=1) and samples in the fifth task weren't explaned...

Thank you for the contest GlebsHP, I am waiting your new round !

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

I solved Div2 A and Div2 C easily, but for some reason I had quite a lot of trouble with Div2 B. The only way I could think of in the end was to keep swapping integer arrays to denote swap of two letters. Does anyone have a better way ?

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

    How do you solved Div2 C?

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

      You have to find all alternating sequences. The longest alternating sequence will provide the first answer.

      My algorithm is based on the followings:

      1) If the alternating sequence has odd length , then the sequence has same bits on both the side (You can easily prove how). So this sequence will eventually be consumed by those bits to become stable.

      2) If this sequence has even length , then the sequence has different bits in each side (Again, the proof is easy). First half of the sequence will be consumed by the bit on the left and the second half will be consumed by the bit on the right.

      3) Step required is ceil(length/2). The answer is the maximum of them.

      Solution passed the pretests. I am a little bit worried about the -1 case though. I am pretty sure this case doesn't exist. But I couldn't prove it.

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

    You can make temporary mapping array 'a' -> 'a' ... 'z' -> 'z', simulate on it for O(26*m) and apply it to string for O(n)

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

    you can use a array f[] to store the letter's meanings.

    and for every swap operation , you can updata your f[] array in O(26) Time.

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

How long till the closing ceremony?

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

И все-таки, чем обоснована задержка систестов? Не совсем понимаю, как это может повлиять на официальное соревнование.

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

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

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

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

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

        Ну ведь детей отпускают в туалет, там они могут посмотреть всё, что нужно

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

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

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

      На онсайте нет доступа к CF и они не могут участвовать и там и там.

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

Great problems ! I would have loved to spend more time solving problem D during the contest, lost so much time to understand that I needed "cin.ignore()" in problem B :(

Thanks for the contest.

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

At least are we going to be allowed to check others submission's ??

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

Is there any information on when the closing ceremony will finish?

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

A round announcement without thanking MikeMirzayanov :D

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

Why should we wait with the results until the closing ceremony's end?

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

    This is to keep up the excitement of the on site contestant until the declaration of the winner names at closing ceremony.

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

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

When the closing ceremony will end ?? :(

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

Кто-нибудь может объяснить, почему в задаче Div.2B может быть ошибка на претесте 1, которая пропадает при замене scanf на cin в считывании символов, которые мы будет менять местами?

И разве претест 1 не совпадает с тестом из условия?

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

    cin >> char >> char считывает c автоочищением потока (поправьте, если я не прав).
    cin >> x >> y; //Считает x и y, как бы ты ни писал их — через пробел или нет
    scanf("%c%c", &x, &y) считывает строку и подставляет значения в x и y, исходя из нее
    То есть, если ты вбил "2 3", то scanf посчитает, что в x надо записать '2', в y — ' ', и оставить "3" как то, что не записалось в переменные (или как-то так)

    int main()
    {
    
    	char x, y;
    	scanf("%c%c", &x, &y); //вбиваем "2 3"
    	cout << x << ' ' << y << endl; // получаем на вывод "2 "
    	cin >> x >> y; // вбиваем "2 3"
    	cout << x << ' ' << y << endl; получаем на вывод "3 2", ибо "3" осталось с предыдущего ввода
    	return 0;
    }
    
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Я это установил во время контеста экспериментальным путем и с помощью костыля избегал этого (а именно — считывал второй символ повторно).

      У меня это решение проходило оба теста из условия, однако на сервере выдало WA1.

      Причину этого я так и не понял.

      В любом случае спасибо за объяснение.

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

      Вроде как можно написать вот так:

      scanf( "%c %c", &x, &y );

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

        Зафейлится при вводе следующей пары символов, ибо перевод строки — тоже символ

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

          Добавим перевод строки:

          scanf( "%c %c\n", &x, &y );

          Правда тогда может зафейлится на последней строке, если в ней этого перевода нет.

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

            Тогда зафейлится на первой строке, причем с TLE, причину этого я еще не понял, но как это выглядит: считал первую пару символов с переводом строки, и scanf ждет еще какой-то символ, в результате первая пара символов начнет обрабатываться только после ввода второй пары.

            P.S. Отмена, это наблюдается в 2015 студии, на 2010 все будет работать норм.

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

        Чтобы учесть все пробелы и переводы строк лучше вот так:

        scanf(" %c %c", &x, &y);
        

        перед каждым %c пробел — это пропуск пробелов и переводов строк

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

          А вот это круто, спасибо.

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

          Это гарантировано стандартом?

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

            думаю, да. Также как scanf("%d %d") считывает второе число, пропуская лидирующие whitespace (и переводы строк и пробелы).

            A single whitespace in the format string validates any quantity of whitespace characters extracted from the stream (including none). (whitespace characters include spaces, newline and tab characters) cplusplus.com

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

    В случае со scanf, лучше было бы считывать не (char char), а (char[2] char[2])


    char x[2], y[2]; scanf("%s%s", x, y); cout << x[0] << ' ' << y[0] << endl;
  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    Мой тебе совет: научись один раз использовать getchar() и таких проблем не будет возникать. Сможешь считывать любые данные, которые поступают на вход, да еще и быстро. Да, возможно по началу долго писать такой ввод, но потом данный скил сохраняет время и нервы на контесте :-) Успехов!

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

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

      Как balalaika выше ответил, легче и лучше просто читать %s в char[2].

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

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

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

No sign of closing the closing ceremony.

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

What is wrong with Div 2 B solution? Both fail on testcase 1.

Brute force — https://ideone.com/YvASbz Runtime Error — https://ideone.com/cy83S0

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

Why kill the time? plz start the system testing. Every one waiting for system testing.

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

    I think it is because of the onsite events. They cannot start system test now. If they did, there would not be much fun in the closing ceremony(or something like this).

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

Please notify us with any comments. What causes this delay?

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

    UPD3. The results and the editorial will be published later, after the closing ceremony of the official competition

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

Seems like contest is not of 2 hours but of entire day ;)

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

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

System testing started. Feeling emotional :P

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

Finally system testing started !!!! -_- :D

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

why TLE?

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

System testing finished but practice mode is not enabled! Why?

UPD. It's now fixed.

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

Прождали систестов, теперь вперед ждать обновления рейтингов! Хэй!

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

    рейтинг можно посчитать самому, формула открыта же

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

      Maxim, 1k_trash и я недавно набросали расширение на хром. В любой момент времени на контесте у вас есть такая колонка, что весьма прикольно. Если предикшн совпадет с результатом, то допилим и на днях опубликуем.

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

        а у вас оно как считается — прямо в браузере или на сервере? Я вчера тоже сделал сайт на эту тему, чтобы потратить сгорающие промо-коды с hackerrank, но амазон затянул с активацией ec2-инстансов для моего аккаунта и запуск пришлось отложить. А теперь видимо и вовсе отменить, чтобы не плодить велосипеды)) Если надо, могу поделиться дампом раунда #326, на котором тестировал формулу

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

          Сейчас будет смешно: считаем за N2 * log(N) на джаваскрипте)))))))

          у меня вообще нету опыта в этой сфере, так что мы были бы рады любой помощи)

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

        расходимся

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

          Я немного потьюнил формулы:

          • ускорил сходимость: contestant.delta = (contestant.needRating - contestant.rating) / 3; -> contestant.delta = (contestant.needRating - contestant.rating) / 2;
          • ограничил анти-инфляционный эффект (в посте отпишу что да как).
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Еще ждать дорешки приходится.

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

still not able to see testcases and submissions :(

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

Why is there so much delay? 1. there was delay in testing 2. now practice mode is not enabled 3. there is no editorial uptil now. 4. I can't see other's submissions.(What is the point of making submissions invisible until system testing is over)

Please do it quickly.

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

Was worried about plateauing for a while but it seems like I'm still improving!

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

Feel free to upsolve and read other contestants code. Yes, i'm feel free while the others codes are blocked <3

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

I am a Div 2 participant. My submission for question 1 was processed by the server twice. Hence there were two submission both at the same timestamp. Also, I was penalised 50 points as resubmission. Why did this happen? Can something be done regarding this?

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

Why rating change is so delayed ??

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится
UPD4: ............ Congratulations to Div. 1 top-5

Why only Div. 1 winners ? What about Div. 2 winners (or top 5) ??

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

Is this round even rated ? !

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

UPD4. The system testing is over, results are now final. Feel free to upsolve and read other contestants code. Congratulations to Div. 1 top-5:

How?

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

Still unable to "read other contestants code"

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

    "I give you A you give me B"... this won't be considered as cheating now :P

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

Rating — time limit exceeded.

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

these people have no idea what theyre doing

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

Was this round rated? Or is the rating change delayed for some reason?

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

    I have been starting to wonder the same thing. And it was my first time solving C too :/

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

      well this problem C was the only problem C in these recent contest which needed a bit of thinking :) others were just brute force and corner cases (we call it tof in persian )

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

        Actually, I need to rephrase. It was my first time solving 3 problems. And yes, I think you are right. In some of the previous contests, I somehow found B harder than C.

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

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

CF skatilsya, ranshe lu4she bylo((

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

We can't "read other contestant's code" yet GlebsHP :P

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

Atleast make the testcases public. Can't wait to see where i went wrong in Div2 C.

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

I am quite disappointed in today's problemset, especially since there was like 20 people involved in preparing the contest. For me ideas for B, C, D are quite old and standard (and I'm guessing many people feel the same way, as there are 45 people passing all 4 problems, and much more passing pretests). And did authors know that D has observation that s < 6000? How can it worth 1750 points?

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

    It is impossible to have five problems with new idea every round. What we try to achieve is to offer something new to everyone. The result is that for almost everyone there will too easy and too hard problems, but at least one problem will be the right challenge to his\her solve\write abilities. Problem E was your challenge yesterday.

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

Zlobober back maybe ? :D

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

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

Looks like GlebsHP is counting rating manually :)

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

    or maybe code that computes rating is like this:

    sleep(10 * 60 * 60 * 1000); //10 hours
    update_ratings();
    
»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

hi first thank GlebsHP for prepare The Contest, the problems are very nice and creative:) but system rating... :(

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

For those interested, here is a much easier version of three states. http://www.usaco.org/index.php?page=viewproblem2&cpid=88

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

    The problem is very simple anyway :)) In my opinion, it was the easiest div1 problem from the contest

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

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

Finally we can see submissions. I hope ratings will be updated soon. :)

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

Never had such bad experience before. Everything seems messed up. :( system testing has finished 3.5 hours ago but, no rating change. Still can't see others code and test cases !!

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

They should change Codeforces' logo for this blog to something like

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

13849187 , what is wrong with this code? Why is the output blank? It runs fine on my compiler

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

Finally rating change. o_o Waiting for saturday contest. :)

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

waiting for solutions for the contest...

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

    Editorial in Russian will be published in approximately 10 minutes. Unfortunately, English one will be published only tomorrow.

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

How to solve problem D? I used ternary search to find the best angle we have to move until time t and them go directly to destination. (or go to destination under t seconds). but my code couldn't even answer the first test case. here's my code http://codeforces.com/contest/591/submission/13852036

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

    You don't have to care about the angle, all you need to care about is the time taken. Say that you're making a guess that the trip will take h seconds, and the other variables are as given in the problem statement. That means that during that trip you will be moved to the direction vx,vy for min(h,t) seconds and to the direction wx,wy for max(h-t,0) seconds. When you know this, you can move your starting position to x = vx*min(h,t) + max(h-t,0)*wx + x1 and y = vy*min(h,t) + max(h-t,0)*wy + y1 to compensate for the wind, and pretend there's no wind. Then you can just check whether you can get to the destination from your new starting position in h seconds. Now that you can check if the trip can be made in time h, you can just make a binary search.

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

Московская командная олимпиада школьников по программированию добавлена в тренировки.

Лига A и Лига B соответственно.

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

Не добавлены авторы у контеста div2.