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

Всем привет.

Этим раундом мы торжественно открываем соревнование Яндекс.Алгоритм 2011. Задачи этого раунда были подготовлены мной, конечно, не без помощи команды Codeforces и Яндекс.

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

Как вы уже успели заметить — система функционирует в несколько урезанном варианте. Мы решили перестраховаться и выключили на время контеста некоторую функциональность. После окончания раунда все вернется на место.

Напоминаю, что лучшие 500 участников получат путевку в первый отборочный раунд. Однако, если у вас не получится пройти отбор в этот раз, не надо отчаиваться – вы сможете поучаствовать во второй квалификации, которая состоится 6-го мая в 19:00.

Желаю легкости на подъем,
MikeMirzayanov

UPD: Контест закончен! Всем спасибо за внимание, надеюсь вам понравилось. Хочется поздравить победителя watashi и самого удачливого участника cover_dh, который занял 500-е место! Напоминаю, что лучшие 500 участников выходят в первый отборочный раунд.

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Михаил, вы не сделали возможность выбора, будет ли раунд для участника рейтинговым или нет? 
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Round FAQ:
1) Round will be rated (affects rating).
2) Rules are Codeforces standard rules. Please read them carefully!
3) Also be sure you are registered for the contest! Find yourself here.
4) If you passed this qualification - you can participate 2nd qual. and it also affects your rating.

===

FAQ Раунда:
1) Раунд рейтинговый.
2) Правила: стандартные правила Codeforces, прочитайте их внимательно!
3) Проверьте свою регистрацию на соревнование! Найдите себя здесь.
4) Если Вы квалифицировались в этом раунде - Вы можете участвовать и во втором квалификационном раунде, и он тоже будет для Вас рейтинговым.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Посреди рабочего дня можно найти 10 минут, чтоб сдать задачу, которой вполне может хватить, чтобы пройти, а на рейтинг это пагубно повлияет. Кто-то это уже где-то писал
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А что дороже - рейтинг или квалификация Yandex Open?

      P.S.: Мы тут в английской ветке флудим.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    It would be nice to have a page about this competition, the rules, the advancers and etc.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
больше не флудим в английской
можно было дать выбор, многие бы, я думаю, обрадовались
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Стоит ли говорить, что рекорд по количеству зарегистрировавшихся побит?
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
        "The registration will be opened during the whole contest."

This was written in the email which was sent to me about this round, but I see that the registration is closed.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Будем считать этот завал следствием недосыпа =__=
  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Не у одного меня мозги не работают в 8 утра =) 
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У вас хотя бы утро. А у меня сейчас - полчетвёртого ночи :)
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

During the last minute of the contest, I tried to hack with a Python generator submitted as a file named "tt". Had no time to name it nicely.

I've got the following error.
-----
Traceback (most recent call last):

  File "<string>", line 1, in <module>

IOError: [Errno 2] No such file or directory: 'tt.py'
-----
So, the server tried to open "tt.py" when the file was named just "tt".

I believe it's not the intended behaviour. Will it be corrected?

UPD: The test is incorrect anyway, so it won't affect the results.
13 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится
Thanks for the contest!

There's one thing that confuses me: were contestants still separated by division? If yes, it looks unfair because tournament advancement may be easier if you're in div 2.
13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
За пятнадцать минут до конца раунда сайт был недоступен с 503-й ошибкой. Починилось быстро, но всё равно тревожный звоночек.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    У меня ошибки выдавало не только за 15 минут. По сути в течение всего контеста периодически появлялись =/
13 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится
Ух ты, блин! Еще б 15 минут-и я бы все 5 сдал! 
5 задача сильно понравилась.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Спасибо за контест!

Впервые пытался  взломать чужое решение.

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

Во второй раз вижу, что у участника в задаче A решение за квадрат. Пишу генератор на питоне:

N = 10**5//26                                                                                                                               
S = "qwertyuiopasdfghjklzxcvbnm" * N                                                                                                        
print S + S[::-1]                                                                                                                           

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

Что я делаю не так?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Насколько я понял, там по условию нельзя, что бы строка в выходном файле была пустой. Сам ломал таким же тестом, только в начало добавлял символ 'а', а в конец 'b'
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Вероятно, там было написано, что ответ на ваш тест - пустой. По условию задачи это недопустимо.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится
      А, точно, да, у меня же все пары удаляются, ответ - пустой будет. Не подумал про это.

      Спасибо!
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Возможно не тест пустой, а результирующая строка пустая, после удаления всех пар.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо, так и есть!

      Но поскольку впервые что-то ломал, то подумал, что я не разобрался с тем, как сдавать генератор.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    По условию, после удаления дубликатов должна остаться непустая строка.
13 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
What is the problem with u guys(codeforces or ....).Why problem statement is so confusing.What does it mean ?

"if two consecutive numbers were separated by spaces only (one or more), then exactly one of them should be left" 

what does it mean =>
---- It means one number will be removed.
---- It means one space will be removed.
---- It means all spaces except one space will be removed. 
During contest i submitted with the second explanation above & i got Pretest passed.
Now if i get WA for this reason is it my problem ??
  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    I took it as one number will be removed. I was confused whether which number to remove.
    I bet on the left one and got WA . I was dumb enough to not able to think one space will be removed. Though i still don't know what is the correct one from your three choice.
    • 13 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится
      It is quit normal for anyone to be confused.
      If codeforce can't translate problem statement into English so what is the meaning to set a contest in english version.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

        "Polycarp wants to add and remove spaces in the string s to ensure the following:"

        It is written in the statement. I was also thinking a while about this point, but the statement is ok.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          • 13 лет назад, # ^ |
              Проголосовать: нравится +8 Проголосовать: не нравится
            I can not copy paste it here but there is my clarification and the answer:
            Please broadcast a message about the spaces as if two numbers are separated only by spaces ... exactly one of them should be left - this may refer to numbers.
            Answer:
            1. "Polycarp wants to add and remove spaces in the string ... "
            You are not allowed to do anything else (remove numbers etc.), only add and remove spaces.

            2. In every sample test removing numbers doesn't work.

            3. There were no other such questions.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Same problem. very confusing statements and I think none of the pretests were about the numbers.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Hmm, for me, it means something like: if you have "1<space><space>2", you need to remove all-but-one spaces, so it becomes "1<space>2". I try to challenge other by this case, but it is an invalid case. Now, my conclusion is: we don't need to understand that sentence in order to solve this problem :(
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Are you sure? I took the statement as "one number will be removed." and my solution hacked by "5<space><space><space>9". and also I successfully hacked a solution with:
      "3464574575367357<space>4674575368345646835<space>56,...,...,56,456,...,"
      So the statement was matter.



      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        How come :( yeah I'm pretty sure that I tried to challenge other by that case, and I couldn't as it show: invalid case... That's why I thought that numbers should be separated by "," or "..." and stop making other challenge. Grrrr I should have many successful challenges
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Check your hack, you will see this message: "FAIL Expected EOLN (stdin)"
          You didn't press "Enter" key. The input should end with end of line character. At first I had same problem.

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            I think I pressed "Enter" (this time I'm not so sure), and there was no explanation except "invalid case". Anyway, it's ok for me :)
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Расскажите, пожалуйста, решение задачи D.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Банально жадно решалась с такими ограничениями.

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

    Итого: O(M * N * M)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      На самом деле даже альбом на первом месте перебирать не надо, ведь оно ничем не отличается от всех остальных. 
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А, точно, кольцо же.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится
        А как выбирать если несколько с максимально оставшимися снимками? Если брать с минимальным номером, то не работает.

        Взлом:
        8 3
        3 1 4

        Такое решение строит

        3 1 3 1 3 1 2 ?

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

          Я сделал так: всё тоже самое, только сначала отсортировал альбомы по убыванию количества снимков. Все тесты прошло, этот тоже.

          Не знаю, почему, если честно =) Наверное, случайно)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Мой пост ниже объясняет, как я поступал в такой ситуации, на этот тест мое решение дает ответ: 3 1 3 1 3 1 3 2
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Не зря я значит перебирал первый возможный альбом.
          У меня жадное выдаёт:
          8 3
          3 1 4
          1 3 1 3 1 3 2 3
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Нет, перебирать надо. Пример:
        4 3
        2 1 1
        После того, как мы ставим на первое место 1, мы затем ставив 2 3 ( потому что снимков в них - макс оставшееся, 1), затем ставим 1 - все плохо.
        А меж тем ответ 1 2 1 3 существует.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          дада, 102 тест) прелесть просто
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Не надо перебирать. Достаточно во всех местах кроме последнего в сортировки при равенстве количества в первую очередь брать то, что на первом месте
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А как это доказать?
            • 13 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится
              У меня есть доказательство, но мне очень влом писать. Расскажу при встрече
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Ок, если не забудем :)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится
                  эм, а это разве не очевидно? я пользовался этим фактом для решения задачи
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится 0 Проголосовать: не нравится
                    Куприн, с покраснением:)
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится +13 Проголосовать: не нравится

                    Ваше доказательство напомнило эту байку :)

                    • 13 лет назад, # ^ |
                        Проголосовать: нравится +3 Проголосовать: не нравится
                      гм, это вовсе не доказательство)

                      был один случай, когда хороший знакомый рассказывал решение задачи, и когда я попросил обоснование, он просто ответил: "моё решение правильно, и акцептед это подтверждает" =)
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится +1 Проголосовать: не нравится
                      Хмхм... хорошая байка. Год назад на одном экзамене мне в качестве последнего был задан вопрос, на который я не знал ответа. Однако, хорошо подумав, я сказал: "Вы в своей книге об этом не написали". Получил 5. Думаю, это настолько же справедливо, что и заключать о правильности решения по вердикту жюри :)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +6 Проголосовать: не нравится
                  можно еще положить на нечетные места (кроме последного, разумеется) самый толстый альбом, а потом то же самое. Это вроде проще доказать.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Спасибо. Я чувствовал, что это какой то баян и как то тупо решается. Но увы, не допер.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      С таким решением меня взломали тестом

      6 3

      3 2 1


      Программа пытается поставить 1 2 1 2 3, на последнем шаге единицу поставить не может и выводит -1. На каждом шаге я действительно выбираю альбом с максимальным числом оставшихся. Что тут не так?

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

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

      Благодаря таким решениям у меня +500 =)

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

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

    Мое решение - если в альбоме более n/2 снимков, можем считать, что их n/2 - остальные не сможем расставить.  Если теперь в альбомах в сумме менее n снимков - ответ нельзя. Сортируем альбомы в порядке убывания в них снимков. Теперь берем поочередно альбомы и расставляем снимки через одну позицию - сначала все четные позици заполним, потом все нечетные. Никакие два одинаковых не будут стоять рядом и все позиции будут заполнены.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      о, спасибо)) это больше похоже на обоснованное решение:)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Без сортировки вроде бы вот такой вот тест ваша программа не пройдет:

      6 3

      2 3 1

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Угу, точно. Решение с ней и посылал, а сейчас забыл зачем.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Нужно быть аккуратным, если в каком-то альбоме окажется ровно n/2 снимков.
      4 3
      1 2 1
  • 13 лет назад, # ^ |
      Проголосовать: нравится -15 Проголосовать: не нравится
    Я так бегло просмотрел и заметил, что вроде как никто из отписавшихся не отправил наиболее безыдейное решение на задачу D.
    Очевидно, что если для цепочки и есть хотя бы какие-то запары с расстановкой, то для цепи уже никаких. Так давайте переберем значения первого и последнего элемента (они должны быть различны) и будем очевидной жадностью искать ответ для цепочки со второго элемента до предпоследнего. Там уже понятно, что каждый раз надо ставить наиболее частовстречаемый элемент из допустимых.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Действительно, бегло:)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        То есть решение за O(NM3) уже где-то было описано? Я вроде еще раз глазами пробежался по комментариям и не нашел такого. Решения, где перебирается только начальный элемент не предлагать - оно требует хотя бы чуть-чуть подумать.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Если идея "перебрать первый + жадность" верна, то очевидно, что идея "перебрать первый, последний + жадность" отже верна. То есть может решения с двумя переборами описано не было, но из того, что было написано, ясно что оно тоже верное. А "идейность" - понятие субьективное.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится
      Почему понятно - ведь на предпоследнем элементе тогда может лажа возникнуть, на него есть дополнительное ограничение - несовпадение с последним.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Да, но раз мы перебираем все варианты последнего, то среди них же будет и тот, который стоит в правильном решении, и там лажа не возникнет.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Почему? Не факт же что правильное решение находится жадно?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Выше было написано два решения: одно с перебором первого, второе  - где на первое место сразу ставится жадно максимум, что идентично первому из-за цикличности. Решение с перебором первого и последнего - идентично решению с перебором первого и второго - идентично решению с перебором первого и подставлением максимума на вторую позицию - идентично решению с перебором только первого, которое было описано выше. 

            (Это все безусловно верно в том случае, если первые два описанных жадных решения действительно верные, а не просто прошли все тесты:) Но если они верны, то тогда решение с перебором двух идентично им.)
            • 13 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится
              Тут есть два момента.

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

              2) "идентично первому из-за цикличности" - не понимаю. Вроде выше же было показано, что решение где на первое место ставится жадно максимум неверно без дополнительных хаков )
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну в моей реализации я всегда смотрел оба элемента - предыдущий и последующий (для рассматриваемого интервала они всегда существуют). Изначально все незаполненные элементы просто ставил равными -1.
        Если мы пришли в состояние, когда мы не можем поставить на предпоследнюю позицию ни одного элемента, это означает, что где-то в случае, когда у нас было два альбома в которых осталось равное число неиспользованных изображений мы выбрали не тот. Рано или поздно мы придем к варианту, когда на последнем месте стоит тот самый элемент, который тогда мы выбрали при равенстве. Так как порядок приоритетов у нас всегда фиксированный, то и в этот раз мы опять выберем его же там в середине и к предпоследнему элементу у нас будет все тот же элемент, что и в прошлом случае, но на этот раз он не будет совпадать с последним.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Нет, мы не выберем его же в середине, так как поставив его на последнее место, мы уменьшим его счетчик на 1, и поэтому все наши решения, возможно, будут другими.

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

              Про "в середине" все еще не понимаю. Можно конкретный пример?
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Для теста:
                N = 7, M = 4
                A1 = 1, A2 = 2, A3 = 3, A4 = 1:

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

                По поводу выбора элемента, который у нас имеется в самом большом количестве... На самом деле нам желательно сделать так, чтобы в конце (на предпоследней позиции) осталось 3 варианта, тогда мы в любом случае сможем поставить предпоследний элемент. Если осталось 2 или 1, то нужен порядок приоритетов, который позволит удержать к этому моменту допустимый элемент. Это уже по части предыдущего утверждения. Помимо прочего, нам не важно, сколько у нас имеется в запасе каждого элемента. Нам важно только количество различных элементов. Не может же возникнуть ситуации вида "нам нужен именно ЭТОТ элемент", может быть лишь ситуация "нам нужен любой элемент кроме ЭТОГО". Так давайте будем до последнего поддерживать количество различных элементов как можно большим.
                На звание строгого доказательства это не претендует :)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +6 Проголосовать: не нравится
                  Ага, примерно понятно, спасибо :)
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +5 Проголосовать: не нравится
                  Почему-то на обоснование "наиболее безыдейного решения" потребовалось больше всего текста :)
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится +2 Проголосовать: не нравится
                    На контесте я для себя это обосновал так:
                    "Если не это, то что?!".
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      Кстати, я примерно так же обосновывал решение для себя :)

                      Вообще тупая жадность не прошла претесты, в итоге я решил написать как можно более навороченную жадность, думая что если уже она не пройдет, то не знаю что дальше буду делать. Получилось извращенное решение со сложностью O(N2M2logM), которое мало того что прошло, так еще и за 30мс отработало.
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится +1 Проголосовать: не нравится
                        =======================
                        Мое тоже отработало за 30мс, но там это происходило из-за того, что если ответа нет, то все варианты быстро отбрасывались еще на стадии расстановки, а первый же найденный ответ сразу же выводился в файл и на этом работа программы окончена. Как правило, если ответ есть, то он находится достаточно быстро.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      я посортировал все албомы по убыванию фотографий в них, на первое место ставим фотку из первого альбома (в нем максимальное число фоток). очевидно что если решение есть, то есть и такое. затем рекурсивно перебираем какие фотки будут поставлены на места 2, 3, 4 (они могут быть из одного и того же альбома, если не соседствуют, и эти фотки перебираются только из четверки самых толстых альбомов) затем заполняем массив начиная с позиции n до позиции 5, каждый раз беря фотографию из альбома, в котором на данный момент больше всего фотографий. Доказательства у меня конечно нет, но интуитивно мне верилось что такое проканает.Поясняю почему мне в это верилось. Давайте поставим на первую позицию фотку из самого толстого альбома, а затем будем жадно расставлять до самого конца. У нас может построится решение, а может обломаться тем, что в конце две фотки окажутся из одного альбома. В случае если алгоритм олбомался, а решение существует, можно переставить несколько фоток местами и получить решение. Последнее утверждение требует доказательства, но мне показалось оно разумным и решение прошло тесты. итого 4^3 * n * m. Интересно уже увидеть авторское решение, задача мне не понравилась если честно, чувство такое что я какой-то чит вогнал.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится
    У меня зашел перебор с грамотными отсечениями - пихаем символы по кругу, если на каком-то этапе осталось запихать L символов, и в какой-то кучке больше L/2 + L%2 фоток - то уходим. Естественно, до этого нужно кол-во фото во всех альбомах сделать равным N, убрав лишние из самых больших альбомов.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    В моей комнате было отличное решение maggot092, оно прошло систесты. Решение такое. Сначала оставим от каждого a[i] не более n/2 и проверим, что это вообще возможно. Затем будем ставить a[1] первых, a[2] вторых, и так далее, пока не поставим n штук, на позиции в следующем порядке: сначала 1, 3, 5, ..., а потом 2, 4, 6, ... (нумерация с единицы).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это вроде то же самое, что volkhin написал выше? Как отмечено выше, это работает только если еще и отсортировать a[i] по убыванию.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Сортировать не обязательно, просто четное n и альбом с n/2 - это особый случай.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Да, это я туплю. Конечно, выше описано то же самое. И действительно есть отдельный случай n % 2 = 0 && m = 2 альбом с n/2 фотографиями.
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Oops

(a < b && t[i] > cutOff) || (a > n && t[i] < cutOff)

and I've tested in on many cases :)
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Куда пропало соревнование
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Рейтинг будет считаться по общей таблице или будут созданы таблицы дивизионов?
  • 13 лет назад, # ^ |
      Проголосовать: нравится -43 Проголосовать: не нравится
    Лучше б таблицы дивизионов не создавали. Возможно проскочу в оранжевые тогда:)
    • 13 лет назад, # ^ |
        Проголосовать: нравится -41 Проголосовать: не нравится
      Проскочил:)
      • 13 лет назад, # ^ |
          Проголосовать: нравится -36 Проголосовать: не нравится
        Кому-то не понравилось что я оранжевый? Почему так активно минусуют?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +12 Проголосовать: не нравится
          Меньше на вклад смотри. Что ты все время из-за него загоняешься? Когда у тебя появилась одна оранжевая точка - это еще не оранжевый. Да и вообще на CodeForces уже даже красный цвет ничего не значит. Тут рейтинг скачет как давление в 80 лет. За один раунд вот так можно подлететь на 200+ рейтинга если ты еле влез в топ100. И красный может за один раунд вылететь в фиолетовые.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +9 Проголосовать: не нравится
            Я за время своей CodeForces-жизни побывал почти во всех доступных цветах :) За исключением единственно серого, но я не сильно переживаю на этот счет =)
            • 13 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              А есть ли те, кто побывал во всех цветах?
              Вспомнился текст из песни
              "Эй, жители неба,
              Кто на дне ещё не был?
              Не пройдя преисподней,
              Вам не выстроить рай.
              Эй, жители дна,
              Гром смеётся над вами.
              Чтобы быть с ним на равных,
              Есть один путь - наверх!
              "
              • 13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                У меня вот последняя строчка этого припева, кстати, даже возведена в ранг подзаголовка ЖЖ =)
          • 13 лет назад, # ^ |
              Проголосовать: нравится -25 Проголосовать: не нравится
            Паш, мне на него вообще пофиг. И, заметь, я написал "проскочил".
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
HI, can anybody tell me how to solve C?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    we have to Max
    ( a1 + a2 + ... + aa ) / a + ( b1 + b2 + ... + bb ) / b

    to common divisor
    ( b * ( a1 + a2 + ... + aa ) + a * ( b1 + b2 + ... + bb ) ) / a*b <= cnst

    b * ( a1 + a2 + ... + aa ) + a * ( b1 + b2 + ... + bb ) --> max

    then guess that if b > a, then ai sould be >= bi
    else if a < b

    if a == b we must output 1 1 ... 1 1 2 2 ... 2 2
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      i can't guess this statement " then guess that if b > a, then ai sould be >= bi
      else if a < b ",can you explain me?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        lets try to prove that for 2 numbers
        we have a, b and numbers x and y (let x > y)

        ax + by - ay - bx = (a-b)(x-y)
        x - y > 0, so if a > b and a - b > 0, ax + by - ay - bx  > 0

        and finally ax + by > ay + bx
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    S1 / A + S2 / B ->max

    S1 + S2 = total sum of all a[i]

    if A = B then output 1 1 1 ... 2 2 2

    if A > B we need to maximize S2, else S1

    if A > B

    we need to sort array of marks, S1 = a[1] + a[2] + ...+ a[A], S2 = a[A + 1] + ... a[A + 2] + ... +a[n]

    we can count how many marks 1 we must to include in S1, how many marks 2  we must to include in S1.. 


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

МЕНЯ ВЗЛОМАЛИ НА НЕКОРРЕКТНОМ ТЕСТЕ :(

ЧТО ДЕЛАТЬ ???.....

  • 13 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится
    Что за тест? Может ты не понимаешь почему он корректен?
    • 13 лет назад, # ^ |
        Проголосовать: нравится -21 Проголосовать: не нравится
      Дряпко, в клубе три чела сидят, и ты хочешь сказать что все не понимают??
      • 13 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится
        Видимо, так.
        Solution verdict:
        TIME_LIMIT_EXCEEDED
        Чем мериться количеством, можно было прочитать ещё раз внимательно.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    1) Не писать жирным и подчёркнутым текстом.
    2) Откуда информация, что тест некорректный?

    Какая задача, какой тест?
    • 13 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится
      В условии гарантировалось, что в ответе будет хотя бы один символ, а в взломе вывод пуст..... :(
      • 13 лет назад, # ^ |
          Проголосовать: нравится +25 Проголосовать: не нравится
        Это потому что там TLE.
        Видимо если решение не проходит по времени, то и чекер не запускается. Поэтому в строчке answer пусто.
        • 13 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится
          Запускается там чекер. Не сразу понял в чем дело, пришлось символ спереди добавить, чтоб взламать решение. :)
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            Видимо сначала тест проверяется на корректность, потом тестируется решение участника, потом тест запускается на авторском решении.

            Если решение участника падает (по времени например), то авторское решение не запускается и строчка остаётся пустой.
      • 13 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Мне больше интересно другое...

        Я сломал решение 424785 тестом [ab]49999раз + [ba]49999раз + с.
        Затем прошло точно такое же решине на паскале:

            1. var
            2.  s : ansistring;
            3.  i, n : longint;
            4. begin
            5.     readln(s);
            6.     n := length(s);
            7.     for i := n - 1 downto 1 do if (s[i] = s[i + 1]) then delete(s, i, 2);
            8.     writeln(s);
            9. end.

        И это же решение снова ломается подобным тестом! Правда не видно каким точно... Но суть вроде та же.

        Может бага в системе?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Это моё решение !!! И оно проходит в дорешивании....
          • 13 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

            Значит системные тесты оказались слабые и взломы всё ещё не включаются в них.

            Мне больше интересно как это решение прошло (обошло) мой первый взлом.
            Не должно же было. Тут же квадрат.
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              на вашем тесте решение отрабатывает спокойно линейку, так как в вашем тесте вообще нет двух рядом стоящих одинаковых символов и delete никогда не вызывается. а вот на тесте [ab]49999 + [ba]49999 + c оно будет работать действительно за квадрат, и меня тоже смущает факт что это решение работает не дольше 770мс на систестах.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится +8 Проголосовать: не нравится
                Да! Да! Да!
                Там конечно было вот точно как у вас!
                • 13 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  1. В систестах я вашего теста не наблюдаю, хотя взломотесты всегда добавляются. Во всяком случае в задаче B 41ый тест мой. Возможно, жюри решили не перегружать задачу А кучей огромных тестов участников.
                  2. В вашем тесте не хватает девятки. На 4999 оно действительно имеет право работать квадрат.
                  3. По-моему,  напрашивается вывод, что жюри зачем то пропускает очевидно неверное решение по задаче A. Либо мы чего то не знаем о процедуре delete.
                  UPD: на тимусе оно как не странно получает TLE (задача 1654)
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится +5 Проголосовать: не нравится
                    По-моему Codeforces ещё не научилось добавлять взломтесты...

                    Видимо вы угадали 41й тест. :)
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится +8 Проголосовать: не нравится
                      ====================
                      Нет, взломы действительно добавляются. На всякий случай. Но мало и вручную. Т.е. это пока не автоматизировано.
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          А я видел подобное решение и ломал ровно этим же тестом. И... программа работает за 50мс. Как так?
          Upd. нет, там все нормально, извините.
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Возможно этот вопрос уже поднимался, однако: куда делись графики рейтинга на станицах? Сделано ли это специально, чтобы не давать участникам лишней информации? Когда вернут? :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Наверное, это одна из фич, которые отключили на время контеста, чтобы сервер не перегружать.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    Это сделано для того, что бы облегчить нагрузку на cf во время контеста. Я так думаю
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    "Как вы уже успели заметить — система функционирует в несколько урезанном варианте. Мы решили перестраховаться и выключили на время контеста некоторую функциональность. После окончания раунда все вернется на место."


    По моему это как-то намекает - )


  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вроде бы это сделано для снижения нагрузки на сервер во время контеста с большим числом участников. Сейчас много фич отключено.
13 лет назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится
По ходу соревнований сдал четыре задачи без бревен и шел неплохо. Но в конце меня взломали по второй задаче. Я думал, что это фейл дня. Но во время систеста у меня упала первая задача из-за того, что я конкатенировал stl-строки. Всего-то надо было переписать на массив чаров... Зато перепосланная на 498 баллов вторая задача зашла. Как результат, можно считать, что я сдал первую задачу, но не сдал вторую (первая моя посылка по второй все равно бы не прошла систест из-за еще более глупой ошибки). Справедливость восстановлена...
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Спасибо, не заметил.
Вот только не понимаю людей, минусующих посты с такими вопросами. Ну да это их проблемы...

upd: комментарий к этому
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What about rating? :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I am not able to reply to petr's post. is it a bug?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится
    You don't have required rating to answer Petr, LOL. =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Lol. Actually I am able to post it but after publishing it is shown as a blank comment.
      My comment was:
       As top  500 will be selected from overall ranking table. then how is it easier for div 2 users ?
      Or you are just considering the fact that hacking is easier in a Div 2 room ?
      Correct me if I am wrong.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится
        Yes, I was referring to the fact that hacking is usually much easier in a div 2 room (if the same contestant were to hack there).
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          For div 1 contestants its easy to hack div 2 coder's code. But its not as easy for div 2 coders.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            If I'm a new but experienced contestant (or I created new account), I can get much-much points from hacking.

            But I thought it was obvious.
13 лет назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится
The server was too slow, I can't submit any problem for 50 minutes. Anyway, good problemset.
13 лет назад, # |
Rev. 3   Проголосовать: нравится +4 Проголосовать: не нравится

В задаче B во время контеста получил "Неправильный ответ на претест 5" (посылка 428332), но на своём компьютере программа выводила правильный ответ. Заменил "while (cin.get(ch)) s.push_back(ch);" на "while (cin.get(ch))  if (ch!='\n') s.push_back(ch);", то есть если следующий символ во входном файле не равен новой строке - считываем его, в результате "Полное решение". Отсюда делаю вывод что в претесте 5 в строке есть символ новой строки, а это противоречет условию задачи.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    да, таже проблемы была
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    у меня та же проблема :(
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Каждая строка текстового файла всегда заканчивается символом перевода строки. На Codeforces это правило всегда четко выполняется. Данная задача не исключение. Пятый тест не был особенным, просто ваше решение так отработало.

    В этой задаче я бы считывал данные как getline(cin, s) - это надежный и кросплатформенный способ.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    "слудючий символ" - Чумачечая весна? Мда, попса влияет на наше сознание, по крайней мере у меня проассоциировалось...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
My solution of problem B (#427173) had WA on test 8.
But, it returned correct answer on custom test with input of test 8.
Why did such a thing happen?
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Баг: точка в графике рейтинга подписана как

Открытый турнир Яндекса 2011<BR>Квалификация 1
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    в контакте так же выглядит, если щелкнуть "мне нравится"
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а в задаче B по условию может быть перевод строки в тесте?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    по условию
    >>Входные данные
    >>Входные данные содержат единственную строку s.
    как мне кажется не должен содержать, но
    #include <cstdio>
    #include <cstdlib>
    int main(){
        char c=getchar();
        while(c!=EOF){
            if (c=='\n') return 1;
            c=getchar();
        }
        puts("1, 2, 3, ..., 10");
        return 0;
    }
    получает runtime 1 o_O
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Конечно, каждая строка текстового файла заканчивается символом перевода строки. Тест 5 не был особенным. Все тесты имеют вид "некоторая-строка\r\n".
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Строка может заканчиваться переводом строки. Т.е. файл может заканчиваться /n+EOF, в принципе и должен. Где-то говорили, что это признак хорошего стиля тестов.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        Более того, если даже задача - парсер и во входе допустимы пустые строки, которые надо как-то нетривиально обрабатывать, то, скажем, файл с текстом <something>+/n+EOF надо обрабатывать как содержащий одну строку - <something>. Этот факт был со скорбью и негодованием мною уяснён экспериментально в одном из первых раундов Codeforces.
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

http://acm.timus.ru/problem.aspx?space=1&num=1654&locale=ru

Никому ничего не напоминает?)

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Can anyone help me to figure out why his code for A
Runtime error on test 12

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

Hope to see no more morning-contests :)
It's really hard to wake up before 11:00
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Yeah, had to wake up 6AM to make it (UK time).
    • 13 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится
      I did not sleep at all :) The contest started at 1.00am in Cuba.
      • 13 лет назад, # ^ |
          Проголосовать: нравится -12 Проголосовать: не нравится
        به آریو برزن:
        شما میباس صبحها بری مدرسه!!!
        نه اینکه تو خونه بخوابی
        از خودم یاد بگیر:D
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

          不是每個人都明白你寫什麼。可能會更好地使用英語進行交流:)
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Haha...!
            It'd be nice to have a auto-translate option for comments in non-English. Using Google Translate API maybe.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Come on guys. stop writing in Persian and Chinese. This is not nice really. Imagine what happens if everyone wants to write comment in his own native language? Do you enjoy that really?


            @Sajad: Call me Amir :) , I don't go to school. It's a waste of time :D

            • 13 лет назад, # ^ |
                Проголосовать: нравится +5 Проголосовать: не нравится
              Don't panic there:) the Chinese above is something like this:

              "Not everybody understands what you are saying here. If using English, maybe we could understand each other better this way."

              So you see, just a little in-joke for Chinese speaking people:)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        you are cuban pepper))
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
epic fail

Научите меня читать
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    только я такой особенный или у кого-то тоже возникли непонятки с формулировками в Б?
    • после каждой запятой шел ровно один пробел (если запятая является последним символом строки, то это правило к ней не применимо),
    • перед каждым многоточием был ровно один пробел (если многоточие начинает строку, то это правило к нему не применимо),
    • других пробелов быть не должно.
    при тесте "... ," ответ должен быть "...,", а я возвращал "... ,"
    немного не ясно почему, ибо про разделение чисел пробелами сказан, а про разделение знаков - нет. понимаю, что сам виноват, но все же неприятно из-за этого схватывать WA
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Ну я тоже сперва примерно с этим тупил, и не проходил первый sample
      но:

      других пробелов быть не должно.

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


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

can anyone tell me how to solve the problem E.

although it has tag of tree and dp, but i think it is not a tree, how can we to solve it with tree dp.

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

    1). Lets choose some person and walk to its' friend, to a friend of a friend and so on. Obviously, at some point we will receive a cycle. So, generally, our graph ( nodes=people, edges=friendship) is divided into cycles with som "tails" whom which you can go into the cycle by edges. 

    2). Let's traverse every edge. Cycle remains cycle and from some nodes on a cycle we now can go to some other nodes, possibly from one node to few different nodes. So actually our figure is a cycle with oriented trees that "hang" on the nodes of cycle.

    3).For each tree compute the following DP: 

    F(i,0) = maximum number of pairs we can choose from subtree of i we we don't use i in any pair.
    F(i,1) = the same if we match i with some of its descendants.

    Obviously, F(i,0)=sum(max(F(Child i,0), F(Child i,1))) for each child of i.
    Obivously, F(i,1)=max(F(i,0)-max(F(Child i,0), F(Child i,1))+F(Child i,0)+1) for each child of i. (We loop through all children of i and try to pair i with that child).

    4). Now we have two options: to match last node of a cycle with first one, and not to match. In both cases we then delete our edge from last to first node and we get a chain. We perform almost the same DP on this chain:

    G(i,0) = F(i,0)+max(G(i-1,0),G(i-1,1)) - we don't match i-th node with anything.
    G(i,1) = max(F(i,1)+max(G(i-1,0),G(i-1,1)), F(i,0)+1+G(i-1,0))
    For G(i,1) we have to options: we either match our node with some node in its subtree (first value in max) or match it with previous node in cycle and add F(i,0).

    In case if we match 1-st and last node, G(0,0)=-infinity, G(0,1)=1+F(0,0) and the answer is in G(n-1,0), because n-1-th vertex can not be matched with previous node as it is already matched with the first one.
    In case if we don't, G(0,0)=F(0,0), G(0,1)=F(0,1) and answer is max(G(n-1,0), G(n-1,1)).

    Also, to make it easier, I wrote about DP that just returns maximum number of pairs but I hope it is obvious how to turn in to DP that returns maximum number of pairs|maximum number of boy-girl pairs.

    Hope this helps!

    PS. Solution below is better because it is easier and uses only one DP instead of two.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

      >> S. Solution below is better because it is easier and uses only one DP instead of two. 

      In such case your approach has to be more general than approach formulated below. 
      If no, than your approach should be just more complicated and doesn't solve more general class of such problems ? Can you clear it ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Each connected component in the graph has exactly one cycle. Pick any edge from the cycle and remove it from the graph, now we should consider two cases: a picked edge is in the answer and it isn’t there.  Both cases can be easily solved with dp on tree.

13 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Раскажите пожалуйста как решать задачу Е.
По существу, я так понимаю, что она идейно очень похожа на вот ету http://codeforces.com/contest/70/problem/E. Очень бил би благодарен за хорошое обєснение, возможно нє только етой задачи(Е. По парам.), но и самого принципа. Да и еще парочку задач разной сложности чтобы ето закрепить. :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Перенесу обсуждение сюда.

  1. var
  2.  s : ansistring;
  3.  i, n : longint;
  4. begin
  5.     readln(s);
  6.     n := length(s);
  7.     for i := n - 1 downto 1 do if (s[i] = s[i + 1]) then delete(s, i, 2);
  8.     writeln(s);
  9. end.
Это код посылок 427555 и 427592 с соревнования (от Ministr).
Код абсолютно одинаков. Разница в том, что первая посылка получает
Превышен предел времени на взломе 1 [взломы], а вторая Полное решение [претесты].

Подумал-подумал и решил проверить это решение на систестах в дорешивании. Результат:
Delphi: Превышен предел времени на тесте 12, 1000 мс
FreePascal: Полное решение, 770 мс

 Теперь мне хочется прогнать этот код во фри на сервере с тестом [ab]x49999 + [ba]x49999 + c. К сожалению сейчас это сделать невозможно (ограничение на ввод - 20kb).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Оно, конечно, не совсем то, но допиши код генерации теста в саму прогу. Я думаю, что медленнее от этого она точно не станет, но при этом останется в TL.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Уже сам проверил. На delphi работает ~12 секунд. Как-то нехорошо вышло.
    UPD. На fpc - 3,5. Код здесь.
    • 13 лет назад, # ^ |
      Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

      UPD2. Так там 400к символов. Пост выше игнорировать наверное.

      А вот этот код с 200k символами работает на fpc за 840 ms.

      И 3050 мс на Дельфях.

      Так что шанс сдать этот квадрат видимо был. о_О

      Интересно что за тест был 2й и 3й, которые его поломали.

      UPD. Да, оба не умеем считать)))
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Тут всего 100Кб из 200 разрешенных условием.
        UPD. Считать не умею.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Более того, если вызывать delete в конце строки(особенно от последнего символа) то получится что-то похожее на линию. 
        Для этого нужно просто обрабатывать данные по мере считывания.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Мы сейчас говорим конкретно про это решение. Оно квадратичное в худшем случае как не крути. :)

          А точнее даже не об этом решении, а о том, как оно проходило взломы и было снова взломано.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
  • var s,b:ansistring; 
  •     i:longint; 
  •  
  • begin 
  • readln(s); 
  • b:=s[1]; 
  • for i:=2 to length(s) do 
  •     begin 
  •     if (b<>'') and (s[i]=b[length(b)]) 
  •        then delete(b,length(b),1) 
  •        else b:=b+s[i]; 
  •     end; 
  • writeln(b); 
  • end.

    Мое решение, которое не обращается к несущестующему символу. Памяти ест вдвое больше, зато не падает на aaabbbcc

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
При участии вне конкурса во второй квалификации, влияет ли она на рейтинг?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    MikeMirzayanov
    Да, все раунды будут рейтинговыми. Более того, во всех них сможет принять участие любой желающий. Если участник не квалифицирован на этот раунд, он будет участвовать вне конкурса, но рейтинг участника будет пересчитан в соответствии с совмещенной таблицей результатов участников в конкурсе и нет. Вероятно, исключением станет финальный раунд, поживем-увидим.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, так уже было на Manthan.
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Hi!
I don't know why I can't register Qualification 2.

It said that I had already qualified into the competition, and let me choose whether I want to register as OUT OF COMPETITION participant. I choosed "Yes", but it didn't work, I still can't register this competition.

Anyone can explain this and help me? Thanks a lot!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати, видимо впервые более 1000 человек участвовали в контесте.
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Что то мне подсказывает, что количество участников второй квалификации перевалит за 2000=)
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Дайте все-таки уточнить.
При регистрации на вторую квалификацию мне сказали, что я регаюсь вне конкурса, потому что уже квалифицировался в первый раунд.
Значит ли это, что раунд не повлияет на мой рейтинг или все-таки повлияет?
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
А когда будет официальный разбор задач от автора тура?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
я бы хотел спросить насчет второго квалификационного раунда Yandex.

кто там участвует вне конкурса для них раунд будет не рейтинговым?  или же рейтинговым?
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Жесть. Уже за две штуки учасников перевалило.
Дай Бог что б сервак выдержал :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Really curious about will there be editorials for Yandex Open?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А будет ли вообще разбор?
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi, can someone give me some hints for problem D? I have got to ask since there is no editorial available. Thanks in advance.