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

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

Всем привет!

Вот и пришло время очередного, уже 80-го по счёту раунда на Codeforces.

Контест готовили: Alex_KPRwingerRADConnectorit4.kp. Надеюсь, что всё пройдёт гладко, и всем понравятся задачи про пробуждение Ктулху, ограбление корована, унылость штанов шахтёра и, конечно же, про очаровашку Хексадесимал.

Кстати, Connector сегодня отмечает свой день варенья — давайте дружно его поздравим с праздником! =)

Всем удачи и приятного времяпрепровождения!
_____________________________________

Спасибо всем за участие! =)

Подведём итоги раунда. В первую десятку в первом дивизионе вошли:

Место
Кто
1
 SergeiRogulenko
2
 hos.lyric
3
 Romka
4
 neal
5
 sdya
6
 KADR
7
 ftiasch
8
 niyaznigmatul
9
 dolphinigle
10
 AleX

Стоит отметить, что с задачей E справилось всего двое: победитель раунда SergeiRogulenko, и MBabin, занявший 76-е место.

Первые три места во втором дивизионе заняли:

Место
Кто
1
 anrieff
2
 zplinti1
3
 Efgen

Поздравляем победителей и желаем всем удачи в следующем раунде!

Официальный разбор будет опубликован позднее. Стоит отметить, что AlexanderBolshakov уже опубликовал свой разбор на страницах Codeforces.

Спасибо Delinur за перевод условий на английский язык!
_____________________________________

Опубликован разбор.

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

13 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится
С днем рождения!
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Yes goodluck to all:)
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

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

  • 13 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится
    Конечно, ведь они раунд только ради вклада готовили... 
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Сарказм? Если по делу, то вот почему в лидерах по вкладу it4.kp не видно?

      А он участвовал наверно не в одном десятке соревнований. Не справедливо.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится
        Конечно несправедливо, ведь вклад можно на деньги обменять в ближайшем банке. 
13 лет назад, # |
Rev. 4   Проголосовать: нравится +47 Проголосовать: не нравится

first thing i would to congratulate to Connector and say HAPPY BIRTH DAY :)
second if you want to solve problems written by  Alex_KPR one of problems authors see below contests

Codeforces Beta Round #9

Codeforces Beta Round #58
Codeforces Beta Round #69


13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Wish you a Happy BirthDay Connector :)
Good Luck Everyone :-)
13 лет назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится
Если хотите как следует подготовиться к раунду от Александра, то настоятельно рекомендую прочитать перед раундом какой-нибудь рассказ Лескова Н.С. и замерить время, которое потребуется на его прочтение. Прочитали? Замерили? Вот столько Вам потребуется на прочтение условия одной задачи.
Всем удачи сегодня :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    В этот раз было уделено много внимания именно условиям. На мой взгляд они весьма понятные =)

    PS Спасибо всем за поздравления =)

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Happy BirthDay,Connector
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

while (2>1){

n+=1;

}

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот если это написать на Java, то при наличии операции после этого цикла не дает всему этому добру скомпилироваться...
    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      можно выкрутиться

      int n=0;
      while(true){
        ++n;
        if(false) break;
      }
      out.print(":)");

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

      Так и жизнь - полоса белая - полоса чёрная... :D
13 лет назад, # |
Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

.. (I am Sorry .. for disturb you ..now this time ..)
..Happy Birthday .~
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Outdated comment
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится
      http://codeforces.me/help
      Item 6.

      If some people break the few rules we have here for communication, that's not a valid reason to break them too.
      • 13 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится
        Я себя каждый раз сдерживал, чтобы не написать то же самое, что написал Vasya. Как приятно читать его сообщение, надеюсь, что такие будут раздаваться после каждого набора иероглифов.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Учитывая что человек (якобы) из Китая написал по-японски, он явно имел в виду что-то столь же чуждое ему, как и нам... ;-)
        • 13 лет назад, # ^ |
            Проголосовать: нравится +21 Проголосовать: не нравится
          This is English thread, so please do not break the rules you are insisting to enforce so vigourously
    • 13 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится
      By the way, he just said "Happy birthday".
    • 13 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится
      Don't be so rude! I think it's a pleasure to receive a congratulation from international students. Especially if it's in their native language.
  • 13 лет назад, # ^ |
      Проголосовать: нравится -37 Проголосовать: не нравится
    молю бога, чтобы в будущем не было японских или китайских веток.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +63 Проголосовать: не нравится
      Why Russian threads are ok, but not Chinnese or Japannese? Because you do not understand them? By the way, formally this is English thread, so please refrain from using Russian here
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Respect!

        I think it is impolite at all to write in Russian anything while here is kept _international_ contest. Especially in the topic about this contest.

        All foreigners would spent their time trying to check with google-translator whether all these Russian guys are discussing contest problems or chatting about something else...
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Привет всем, кто пишет раунд с Берендеевых полян
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    а нам в ЛКШ.июль не провели кодефорсы :( даже топкодер не организовали, как это раньше бывало :(
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Все CF и TC раунды совпадали с ужином, я думаю причина в этом:(
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Мог сам сидеть, и писать с мобильника.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Никто не просил, а преподы не особо хотели участвовать
      p.s. Кто ищет -- тот всегда найдёт.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А Вы наверное писали со школи, да еще и прошли в финал ТСО ?
        з.ы. поздравляю :)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я писал только ТСО Round 4 из ЛКШ, это единственный контест, который я написал за время школы.
          p.s. Спасибо =)
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А есть ли где-то материалы из школы ? может можно и контести пописать со школи ?
            • 13 лет назад, # ^ |
              Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

              Материалы раздаются торрентом, вот тут можно взять  линк: http://vkontakte.ru/wall-222235_1427
              Насчёт пописать контесты не знаю, спросите у  dkirienko, где их можно дорешивать.

              EDIT: оказывается, просто так нельзя получить материалы из ЛКШ, так что линк вам не поможет, да и дорешивание, судя по всему, для вас закрыто.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всем удачи и пусть победит сильнейший!!!
13 лет назад, # |
  Проголосовать: нравится +47 Проголосовать: не нравится
Отличный раунд! Спасибо авторам и помогающим!
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Просто интересно - а вы тоже учавствуете в раундах? (наверно просто в таблице не отображаетесь)
13 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

Хорошие задачи. Приятно видеть, что и условия "укоротились" ;-)

Что за весьма короткое по записи решение задачи C для div 2. Я в своём такого "навоял", аж стыдно.

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

    Граф Ктулховидный, если он связный и в нем ровно 1 цикл (т.е. количество ребер равно количеству вершин). Разумеется, речь идет о тех графах, которые разрешены условием (без петель и прочей ереси).

    Следовательно, все решение - в одном обходе графа.

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

      Вот допустим есть такой граф:

      5 6

      1 2

      2 3

      1 3

      2 4

      4 5

      3 5.

      В нем много разных циклов есть.

      Если мы удалим некоторые из них (например 1-2-3-1), то граф всё равно не будет ктулховским, т.к. циклов то не будет, но будет путь 2-4-5-3, что вроде не хорошо.

      Поэтому можно по-подробнее про нахождение цикла?

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Такой граф не допускается условием
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Такой граф отсеивается уже тем условием, что в нем ребер больше, чем вершин.

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

        А если добавить еще хоть одно ребро, то появятся лишние циклы.

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

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

      Это Ктулху из 1-го примера, или я ошибаюсь? Как сосчитать 3 (или более) корневых дерева растущих на цикле?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        одна вершина - тоже дерево
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          "Одна вершина" - в смысле дерево из одного корня и одного листа, или дерево только из одного корня (как вершина 1 например)?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            дерево из 1 корня ( как вершина 1 например)
            • 13 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится
              О, тогда спасибо! Одной мистикой меньше на земле... %)
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Дерево — связный неориентированный граф из n вершин и n - 1 ребер (n > 0). (с)условие
                • 13 лет назад, # ^ |
                    Проголосовать: нравится +1 Проголосовать: не нравится
                  Да-да, я понял... Немного неприятно, конечно, но надо быть внимательнее... ;-)
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Я просто расписал закономерность, которая обнаруживается тупым решением на маленьких тестах.
    Получилось... ну не то чтобы сильно мало, но и не сказать, что сильно много.
    UPD: А, пардон, для div2...
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Заметим, что искомый граф - связный и имеет n ребер. Заметим, что любой такой граф нам подойдет
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    То же самое... Проход на связность, поиск цикла, поиск другого цикла. Расскажите, как за 1 проход сделать.

    А, вот сверху написали. Красиво.
13 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится
Loved the contest :)
13 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Кстати, одному мне показалось, что претесты в этот раз были весьма сильными?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не смог 2-4 раза взломать, из-за того что система тормозила...:(
13 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

<JKeeJ1e30-whinning-mode>
Убил час на D, ощущаю себя тупым, на C почти и не смотрел, в буквальном смысле понимаю теперь, что значит "про...бал время". Завещаю будущим поколениям учиться планировать время контеста и не повторять моих ошибок.
</JKeeJ1e30-whinning-mode>

P.S. Да, и решение neal после этого часа смотрится просто прекрасно :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Его решение и до этого часа выглядело не хуже)

    А планировать контест - целое искусство. Сам хотел бы научиться этому.

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

      Я ж, как честный человек, придумывал онлайновое логарифмическое. А тут "читерят" все :)
  • 13 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    Кстати, D - отличный пример задачи, над "честным" онлайновым решением которой я с удовольствием бы подумал в реальной жизни (пока не знаю, может, она решается красивой структурой, или достойна отдельной статьи, или элементарна), но на олимпиаде предполагаемое автором "пропихивание" не доставляет ни капли фана, некрасиво как-то. Будь то sqrt-декомпозиция или разделение на малые-большие b.

    То есть я признаю, что подобные задачи в практике спортивного программирования вполне себе норма, но это не отменяет того факта, что они мне не нравятся как класс.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Можно было без разделения и корневой декомпозиции (см. ниже).
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Это все равно не онлайн.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Ну да, в онлайне не все решается :) Но это же не значит что задачи, где есть только оффлайн решение, нужно отменить как класс. Уже даже выработалась какая-то привычка, что если запросы генерируются не на ходу, то проще сразу над оффлайн решением думать. Возможно, оно совпадет с онлайн, но на ход решения это не повлияет.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Кстати, вроде бы мое решение с контеста довольно просто трансформируется в онлайн версию. Правда, в худшем случае ответ на один запрос будет O(N), но ответ на ~N запросов будет за O(NsqrtN). 
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Да, мне тоже не нравятся корни. Они иррациональны.
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Хороший контест, жаль, не успел зарегаться (особенно учитывая, что написал задачу С через 15 минут после начала).
Единственный минус - задача D, imho, бородата (беру свои слова назад, если sqrt-декомпозиция не заходит).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Заходит конечно же, надо просто аккуратно кодить. C - имхо гораздо больший минус (или есть более красивое решение, чем разбор случаев?).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да. У меня двумя рекурсивными процедурами компактно написалась (см. код в дорешивании)
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    А как делать с корневой декомпозиций? Я решил с отдельным решением для маленьких Б и больших, но как ее туда совать не знаю.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Как раз для маленьких b и делаешь оптимизацию. Примерно так: разобьем все на куски по 1000 элементов, и в каждом куске для всех b < 300 и всевозможных сдвигов для каждого b решим задачу. Дальше, если в запросе b >= 300, то считаем честно, иначе пользуемся указанной корневой оптимизацией.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну собственно я так и делал, но по нехватке памяти пришлось писать оффлайн.
    • 13 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

      Ну это и есть корневая декомпозиция, вроде бы. 

      Хотя можно было без рассмотрения этих двух случаев.  Просто разделим запросы на группы по B и A%B и для всех групп запросов, у которых совпадают эти 2 числа пройдем прыжками длины B по всему массиву. Сложность получается O(NsqrtN + MlogM).
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Happy birthday, Connector! :)
It was such an interesting contest. The guy called Cthulhu was funny :) Good job! Thanks to the organizers. Keep up the good work :)
13 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится
Мдя. E прошла а A и C упали...
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Really love this contest.
Especially the Problem C, it is very creative.
And the pictures in Problem B & D is so cool! Who is the author?

13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Nice set of Problems... !!

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
What's wrong with sys.tests in DIV2?
13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

По какой причине систест в Div2 завис на 100% (в самом конце видно два решения с вердиктом "Отказ тестирования")? Михаил Расихович забыл добавить дефайн ONLINE_JUDGE в строку компиляции?


UPD. Даблпост :).
13 лет назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

возможно я что-то не так понимаю, но допускается условием задачи В(div-1) такой тест?
6 7
1 2
2 3
3 1
1 4
3 4
4 5
4 6
я сдал два решения одно(595609) выводит "NO", второе(594111) "FHTAGN!". Эти два решения проходят все тесты авторов.
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Today it's my birthday too (seriously)
13 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится
First of all - great contest!
On an unrelated subject I was wondering whether it is not a good idea to modify either the Div1/Div2 limits or the formula for increasing rating of lower-rated (i.e. blue and below) coders to gain more points by performing well, because now Div1 has around 300 contestants and Div2 has over 1000. In my opinion it would be better if the numbers are more balanced.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Absolutely agree. The current formula make less stable Div 1
  • 13 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится
    Also now I noted that the winner of Div2 has solved more problems than me (since their B, C, D, and E are equivalent to our A, B, C, and D) and gains less rating then I did. That's surely odd.

    About problem E (in div2) which was the same as D in div 1:
    Looking at the constraints we can see that N * sqrt(N) solution will pass. Let's for clarity call the queries' pair (a, b) as (start, skip). Now we can divide the problem into two: if skip is more than or equal to sqrt(N) we can use the naive algorithm that just implements the check - then the query has complexity O(sqrt(N)). If skip is less than sqrt(N) we use another algorithm - we precalculate for each possible skip (up to sqrt(N)) and each index from 0 to skip - 1 what is the sum of numbers in positions, that give remainder index when divided by skip. We group each sqrt(N) consecutive values into buckets. This precalculation takes O(sqrt(N) * N) time and memory (which is over the memory limit, but we will fix that later).
    Now, for each query in which the skip part is less than sqrt(N) we can iterate from start upwards until we reach new bucket (and accumulate the current result). After we leave the bucket, we no longer need to accumulate the answer value by value but we can do it bucket by bucket instead (which is okay, since we want ALL values until the end). So we must iterate at most one bucket in O(sqrt(N)) and at most the rest of the buckets, which is also O(sqrt(N)). So the overall time for the query is also O(sqrt(N)) (after doing the precalculation).

    By now we have precalculation which is O(N * sqrt(N)), query of type 1 which has complexity O(sqrt(N)) and query of type 2, which has complexity O(sqrt(N)). This is sufficient for solving the problem in the given time limit.

    The only problem left is what to do with the insufficient memory. If you've ever seen dynamic programming problems with memory optimization done by iterative calculation of values (removing one of the states of the table), then the optimization we can do in this problem is almost the same. We sort the queries by 'skip' (in ascending order) then calculate only part of the table for each skip (thus compressing the memory by sqrt(N)). We then store the answers for each query (using queries of type 1 or 2, depending on the skip value) and in the end just print the results in the correct order.

    Long description, but hopefully useful for some! :)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      It seems like I missed one of the best rounds. I really liked the problemset.

      I think there are too many things that could be improved in Codeforces.  Some Div 2 coders are really good and rating system is really strange.

      One thing that I would like to see very much is the problem statistics. For example, after each problem they could post the percentage or number of with verdicts "failed pretest" , "hacked", "failed system tests", and "accepted", not only the number of accepted submissions.

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


      I tried espr1t's approach with buckets  .. useful to me at least!  :)

      .. but it fails on example 8.
      Unfortunately I can't reproduce the error, the list of values in the input is truncated.
      It's correct on several random examples with either b smaller or larger than sqrt(N).
      link to the C++code.

      I wonder why it's incorrect.  Does anyone see? Thanks a lot for your help!


      Update:  Example 8 is the only one which fails.  I added a condition to treat it separately with the naive algorithm, and that passes the tests now.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yes ,I agree .It would be great idea...
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
I had a query concerning Problem C Div 2. I solved it using the following approach in practice :-

1. First find if the graph has a cycle. If not return NO.
2. Now try removing a edge each time, and run a bfs to see if there is no cycle anymore. If there is no cycle anymore, try to find the nodes between the two nodes for which you removed the edge. There are our possible roots for the rooted trees. Check if indeed these are roots. If no return NO, else return FHTAGN.

Is there a better approach then this ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    If a connected graph has n - 1 edges then it's a tree, and adding one edge will result in a cycle with trees going out of each cycle node. So it's enough to check if n = m and the graph is connected.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    I used a topological sort type of algorithm:
    1. make sure the graph is connected (DFS)
    2. remove "leaves", i.e. nodes with degree 1 until there are none left
    3. check that the resulting graph is a circular, i.e. there are at least 3 nodes and each has degree 2
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    if n=m and the graph is connectd return FHTAGN(you can use union-find set)
    else return NO

  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    One more approach is to use a DFS which counts the number of simple loops in the graph.
    Having performed it you just check that only one loop was found and that the graph is connected.

    However, m = n check is surely more elegant way :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    During contest i just checked two condition ....
    This graph has a single cycle and every vertices connected...if yes than FHTAGN else NO.
    I did this through DFS.
13 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится
*мысли вслух* Вроде и не такое уж низкое место вышло (72-ое), а рейтинг все равно падает.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    У tourist'а вон за 4ое падает ;) Всё же согласись, 72ое место - это слив, у красных рейтинг за такое должен падать.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится
      Пожалуй, соглашусь. Если посмотреть по рейтингу, где я должен был находится среди участников до начала контеста, то будет сильно выше, чем 72-ое место. Просто интуитивно сравнивал с топкодером, а этого, конечно, нельзя делать.
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Problemset and statements of last 2 contests have been pretty good,thanks to problem-setters.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Подскажите, пожалуйста, в чём суть решения задачи Русская рулетка.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    можно заметить, что чем больше мы ставим патронов, тем нам хуже (вероятность выигрыша меньше)
    поставим 1 патрон в крайнюю правую позицию(либо в любую другую и сделаем циклический сдвиг)
    .........X
    теперь рассмотрим циклические сдвиги барабана, которые являются для нас проигрышными
    .-.-.-.-.X
    если мы поставим в такие клетки патроны - нам от этого хуже не станет(шансы не изменятся)
    т.е. можно смело превращать в вид
    .X.X.X.X.X
    дальше, каждый засунутый патрон уменьшает наши шансы, т.е. можно ставить в любые клетки
    но т.к. нам нужна лексографически минимальная строка, то ставим их в конец этой строки
    .X.X.XXXXX
    по сути надо рассмотреть несколько случаев (четность/нечетность n, четность/нечетность k)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Ого, я абсолютно по-другому рассуждал. Если рассмотреть участки из подряд идущих пустых мест, заканчивающиеся патроном, то станет ясно, что Саше выгодно сделать как можно больше участков нечетной длины, то есть по сути надо разбить n-k на k неотрицательных слагаемых, чтобы нечетных было как можно больше, ну а там уже можно выделить какие-то случаи и т.д.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

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

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

    В том, что ячейки заполняются патронами следующим образом (приведу примеры для n == 6 и n == 7):

    6 1 : .....X
    6 2 : ...X.X
    6 3 : .X.X.X
    6 4 : .X.XXX
    6 5 : .XXXXX
    6 6 : XXXXXX

    7 1 : ......X
    7 2 : .....XX
    7 3 : ...X.XX
    7 4 : .X.X.XX
    7 5 : .X.XXXX
    7 6 : .XXXXXX
    7 7 : XXXXXXX

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

Не могли бы автора задач где-нибудь выложить  12 тест 4 задачи
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can somebody explain Div2 Problem. D and Problem. E ??
Thx a lot!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А где можно прочитать про расчет рейтинга?
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
  В разделе "Запуск" реально не хватает возможности добавить генератор инпута. Я был очень удивлен, когда ее не обнаружил.
  Когда формат соревнований предполагает сдачу задач "вслепую" (ну не считая претестов), то такая возможность жизненно необходима.
  В задаче Д очень хотелось проверить как будет вести себя решение на макстесте на сервере. Локально, конечно, протестировал, но уже были случаи, когда время работы на моей машине и на сервере существенно различались. А в этой задаче как в никакой другой нужно было проверить скорость работы - какие b считать маленькими мне подсказал только опыт, а хотелось бы убедится ДО систеста, что он не подвел :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Другой вариант (вполне-таки дополняет Ваш): можно было бы добавить возможность загрузить тест произвольного объема (в разумных пределах, к примеру, до 10МБ).
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Ну можно например написать генератор прямо в решение. Сложность и время работы от этого должно пострадать очень не сильно. Я понимаю, что вы можете парировать тем, что это не дело. Я лишь предложил как вариант.

    • 13 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      Просто для взломов такой функционал уже реализован. Так что почему бы не добавить его и в закладку "Запуск". Было бы удобно.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In Problem D. I don't even understand sample data
5 2 5
1
2
3
4
5
why is it ...XX
this configuration Sasha will have 3/5 probability to lose while .X.X.
being 3/5 to win. why is ...XX the answer?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Actually it' said in problem statement - "Sasha selects any k out of n slots he wishes and puts bullets there. Roma spins the cylinder so that every of n possible cylinder's shifts is equiprobable." This means that after selection the cylinder can be shifted and the position of slots will change
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Your chance to win with .X.X. is 2/5, and not 3/5. You will lose if the roullete stops at some of the two Xs or if it stops at the last position (you will survive the first shoot, your enemy will survive the next one (there's a dot at the first position) and then you will die (there's an X at the second position)). So there're 3 positions out of 5 where the roullete may stop to make you lose.
    Both configurations give you the same change of surviving, but "...XX" is lexc. smaller.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
it seems that there are something wrong with Judgement. It cannot judge.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Are there any data sets in DIV I E like this?
2
2 1 2
2 1 2
-2 -3

Are there any pairs of sets exactly the same?
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
А контест классный был! спасибо. Особенно порадовали интересные условия задач. Так держать!
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I am from China.Happy birthday,connector.

生日快乐!

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

I have a suggestion that the popped-up window is too small when viewing others' source code during hacking and the source font is not suitable enough.I think the font "New Courier" is better.

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

Since I can't delete my comment, just smile for your attention :)

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    +9 (altogether for the previous 3 posts) for double posting with huge font? I have some feeling that if you were a guy (or at least didn't have that picture) it would be a whole different story...
13 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

I have a suggestion that the window popped-up is too small when viewing others' sources during hacking and the source font is not suitable enough.I think the font "New Courier" is better.

Sorry for my poor network. I am not on purpose to type it many times.