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

Автор ag45root, 13 лет назад, перевод, По-русски
Добрейшего!

11 декабря 2011 Молодёжное научное общество "Q-BIT" и кафедра информационных систем Харьковского национального экономического университета проводят традиционный (уже 9-й по счёту) открытый Чемпионат Харькова по спортивному программированию.

Чемпионат является регулярным (проводится два раза в год) и одним из наиболее массовых соревнований по программированию в Украине.

В рамках Чемпионата соревнования проходят в трёх независимых категориях сложности, что делает его интересным как наиболее подготовленным, так и начинающим программистам.

Участвовать можно как "онсайт" - лично присутствуя на Чемпионате, так и "онлайн" - т.е. удалённо.

Тестирующая система Чемпионата - DOTS (Distributed Olympiad Test System), в разработке которой принимал участие dzulgakov

  • для "онсайт" участников до 5 декабря 2011
  • для "онлайн" участников до 09:00 11 декабря 2011
Следите за новостями на сайте http://qbit.org.ua!
Официальный сайт Чемпионата http://khcup.qbit.org.ua

Внимание, онсайт-участники! 
Открытие начинается в 9:30 в актовом зале Харьковского национального экономического университета. Адрес: пр-т Ленина 9А, м. Научная.
Просьба не опаздывать! В 10:30 уже все должны занять свои места и начать решать тестовый тур.
Начало основного тура во всех дивизионах - в 11:00, окончание - в 16:00
закрытие - ориентировочно 16:30

Внимание! ПРИЗЫ!

Надеюсь, что всё получится. Организовать призы, особенно онлайн участникам (это впервые за всю историю чемпионата) довольно сложно - так что не судите строго, если что-то не получится. Все призы от uh.ua подразумевают активацию за 1 гривну. Получилось примерно так:

0. Всем участникам (онсайт и онлайн)  
Сертификат на годичную регистрацию 1 домена (активация за 1 грн) в доменных зонах com.ua, org.ua или net.ua, а также регистрацию всех последующих доменов по реселлерским ценам  [пакет «Maxi» http://www.ukrdomen.com.ua/prices.php?dom_dsct=3]

1. ПЕРВЫЙ ДИВИЗИОН
онсайт GOLD, SILVER, BRONZE
Сертификат на VPS 500 [ http://uh.ua/vps-hosting-prices.html ] (на команду)
Сертификат на хостинг "Оптимальный" [ http://uh.ua/unix-hosting-price.php ] (на команду)
+ ценные призы (каждому)
+ торт, медали, дипломы
онсайт 4-6 места
Сертификат на VPS 500 [ http://uh.ua/vps-hosting-prices.html ] (на команду)
онлайн 1-3 места
Сертификат на VPS 500 [ http://uh.ua/vps-hosting-prices.html ] (на команду)
онлайн 4-6 места
Сертификат на хостинг "Оптимальный" [ http://uh.ua/unix-hosting-price.php ] (на команду)

2.  ВТОРОЙ ДИВИЗИОН
онсайт GOLD, SILVER, BRONZE
Сертификат на VPS 250 [ http://uh.ua/vps-hosting-prices.html ] (на команду)
Сертификат на хостинг "Оптимальный" [ http://uh.ua/unix-hosting-price.php ] (на команду)
+ ценные призы (каждому)
+ торт, медали, дипломы
онсайт 4-6 места 
Сертификат на VPS 250 [ http://uh.ua/vps-hosting-prices.html ] (на команду)
онлайн 1-3 места
Сертификат на VPS 250 [ http://uh.ua/vps-hosting-prices.html ] (на команду)
онлайн 4-6 места
Сертификат на хостинг "Малыш" [ http://uh.ua/unix-hosting-price.php ] (на команду)

3.  ТРЕТИЙ ДИВИЗИОН
онсайт GOLD, SILVER, BRONZE
Сертификат на хостинг "Малыш" [ http://uh.ua/unix-hosting-price.php ] (на команду)
+ ценные призы (каждому)
+ торт, медали, дипломы
онлайн 1-3 места
Сертификат на хостинг "Малыш" [ http://uh.ua/unix-hosting-price.php ] (на команду)
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Will there be tasks in english ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    The statements will be available in English, but user interface is only in Russian.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      If no one can participate without knowing Russian, Then what are these English statements good for?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      disappointed when I download the problem statement and find it's not in English.
13 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится
Я правильно понимаю соревнование командное? И как выбрать номер дивизиона?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

    Исходя из собственной оценки уровня своей команды.

    P.S.: А результаты соревнования покажут, насколько она близка к реальной силе команды.

    • 13 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится
      Я думаю, спрашивалось не о том, как определиться с номером дивизиона, а как его выбрать в системе.

      После регистрации в самой системе нужно будет еще зарегистрироваться на соревнование. Вот там и можно выбирать.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится
        Я именно это и имел в виду. Спасибо за ответ
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
It tell  Kharkov Open, but why it must be in rusian ?
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
А он разве не будет пересекаться с opencup-ом?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
The links are not working for me. Am I the only one experiencing this?
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

торт, медали, дипломы

Можно онлайнам тоже дипломы? Чтоб хоть память была на старости лет. Не сайт же внукам показывать:) С такими призами - лучше уж медальки вместо хостинга...

  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Можно, я могу отсканировать диплом и выложить на сайт. Но всем рассылать по почте -  это нереально :)
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Расскажите, пожалуйста, как это всё соотносится со вторым дивизионом opencup'а? Буду ли участники opencup'а автоматически включены в зачёт онлайн-тура этой олимпиады? А наоборот?
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Я плохо знаю украинский, так что вопрос - можно ли онлайн участвовать не студентам?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, конечно можно! там всё по русски будет (даже интерфейс), а в первом дивизионе ещё и на английском должны быть условия
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      А что тогда писать в графу "учебное заведение"? Место работы?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Судя по аватару, я думал Вы школьник :)
        Можно ничего не написать - полное заполнение профиля является важным только для онсайт участников, т.к. им надо печатать дипломы.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +29 Проголосовать: не нравится
          Ладно, сейчас всех напугаю и поменяю аватару на актуальную
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Верно ли, что тестирование "повисло"?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Тестирующая система явно не успевает за участниками.

Во втором дивизионе за 12 минут 1 проверенное решение на всю таблицу. При этом у нас уже 2 висит на проверке)

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

Отправили задачу L. Получили WA 14. Дебажили около часа, не успели еще две задачи нормально написать. А потом реджадж. Великолепно.

UPD: Одна из этих задач зашла, а в другой буквально пару символов поменять остается. А у нас отняли час, и мы вторые, а не первые.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Это еще скажите спасибо, что я после такого же часа е**тни с этой задачей додумался переписать long long на int, зная с какой надежностью готовятся подобные контесты, и сразу же сообщил администрации. Я и так решал в гордом одиночестве и времени мне ни на что не хватало, так еще и целый час за просто так отобрали некачественной подготовкой задач. Когда же люди поймут, что задачи перед контестом должен решать не только автор.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      > переписать long long на int
      Хочешь сказать, другие ответ выводили в int-ах, забывая о переполнении, а мы выводили в long long и получали WA?

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        это уже не в первый раз, помню тоже из-за этого падали
    • 13 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится
      Привет, Паша :) Прошу прощения за сложившуюся ситуацию.
      Немного объясню, что произошло. Задачи готовили я и брат, готовили в полигоне. Конечно, у нас было много решений и случайно получилось, что в model solution ответ выводился через %I64d, так как полигон на виндоузе. В полигоне незаметно, что это баг, поэтому и пропустили.
      А следить за ходом контеста не очень получалось. У нас не было админских прав и мы не видели решений участников, иначе, конечно, заметили бы все намного быстрее.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я обычно для избежания багов с выводом, когда не нужно выводить несколько мегабайт лонгинтов, использую cout.
        P.S. А что, из Полигона на сервер открытого кубка вытаскиваются не уже готовые ответы на тесты, а только инпуты и model solution'ы? Жесть полная!
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Как минимум, можно было сгенерить тесты под виндой. Ведь было известно, что ejudge под линуксом вертится, и так же было известно про %I64d.
          А еще лучше - писать Model solution на Java. По-хорошему все равно надо писать решение на Java, чтоб рассчитать TL. А тут еще и проблема с 64-битными числами исчезает, красота.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          Меня еще больше удивляет другой вопрос. А что, через после вытаскивания задач с полигона проверяется только main correct solution?! Остальные решения просабмитить (хотя бы на адекватность TL) сложно?!
      • 13 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится
        Привет, Женя. Ну вот это говорит об уровне проведения опенкапа. Авторы задач не могут оперативно вносить исправления. Я думаю, что если бы вы с Димой видели WA14 у большинства участников, то обратили бы внимание на эту проблему.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Но ведь если тесты сгенерировать через doall.sh, разве так как используется wine, тесты не окажутся сгенерены правильно?
    • 13 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится +17 Проголосовать: не нравится

      Я на эту еб...ую задачу вообще почти весь контест угробил, с перерывами на сдачу всяких халявок из таблицы. Итого две задачи не успел написать =(((

      О какой репрезентативности итоговой таблицы можно вообще говорить после такой жести? Некоторые, забывая про переполнения, получали ОК и шли дальше, а кто не забывал - ВА и тратил понапрасну кучу времени на поиск ошибок в собственном верном коде.

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

      Ну надо начинать контесты хотя бы не в последний вечер перед днем проведения готовить-то! Я все могу понять, но вот скажите: сложно было потратить 30 минут перед контестом на вычитывание условий и проверку того, что там нет явной ботвы?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Так можно и особый вид контестов придумать . Так сказать "для гурманов". Нужно сдать неверное решение и угадать ошибку автора :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +2 Проголосовать: не нравится
        Это избавит от невероятного по ощущениям эффекта "Нежданчика". Можешь себе представить мое удивление, когда, написав (int)res вместо просто res, я получил OK.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я бы наверное долго и истерично смеялся...
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Мораль, ребята, такова: нефиг второй див решать)
            • 13 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится
              Да я вот тоже к этому выводу пришёл. Второй раз за сезон по полконтеста решаю решённую уже задачу.
            • 13 лет назад, # ^ |
                Проголосовать: нравится -19 Проголосовать: не нравится
              А в первом опять были питерские задачи - ничуть не лучше. Там бы вы весь контест потратили на запихивание уже решенных задач.

              Мораль, ребята такова: нефиг Питер и Харьков решать, лучше пойти погулять)))
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Сами по себе задачи-то классные, харьковский комплект мне больше всех понравился из всех опенкапов этого сезона.
                А вот их подготовка мы сами видим на каком уровне...
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Я не спорю, что задачи были неплохие, но что это меняет для результата? Все равно самое правильное было пойти погулять)
              • 13 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

                > Там бы вы весь контест потратили на запихивание уже решенных задач.

                Серьёзно? :) Вы бы, может, сначала порешали проблемсет, что ли, прежде чем так заявлять.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится -12 Проголосовать: не нравится
                  Решал предыдущий, хватило, спасибо. Дал себе слово еще хоть раз решать питерские задачи уже в другой жизни.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится -24 Проголосовать: не нравится
                  Кстати, чтобы проверить мою гипотезу, решать даже ничего не надо, можно просто прочитать пост Zhukov_Dmitry ниже. Цитирую: "В задаче C проходило, наверное, любое решение на Java, и почти ничего не проходило на C++. (это про div1 опенкапа :)". Без комментариев.
                  • 13 лет назад, # ^ |
                      Проголосовать: нравится +25 Проголосовать: не нравится
                    ====================================================================
                    Выборка, конечно, репрезентативнее некуда. N <= 5 команд отписались о том, что не смогли сдать не самое оптимальное решение на С++, а смогли на Java, и это по одной-единственной задаче. Конечно, основываясь на этом, можно сразу же номинировать контест на "худший проблемсет года". Ведь участники не смогли сдать очевидное решение, какой ужас.
                    Читаем чуть ниже посты Ильи и Пети, и понимаем, что есть решения, которые отлично заходят на С++. Более того, с вероятностью 99.9% Гена сдал её на fpc, который вроде как медленнее С++. "Ну а если совсем тупой перебор не заходил - так это уж проблемы участников, нефиг лажу толкать ;)" (с)
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится -34 Проголосовать: не нравится
                      ========================================
                      Ну, на худший проблемсет года я ничего не номинировал. Просто заметил, что вряд ли этот контест должен отличаться от всех предыдущих - то есть с интересными задачами и неадекватнейшими таймлимитами. Ну и обычное для питерских контестов обсуждение "а как толкать ..." вроде бы подтверждало мою гипотезу. Если в конкретно этой задаче толкать ничего не надо было - я рад. Видимо, надо было в другой (например, в А). Ну потому что это ж Питер и они просто не могут себе позволить дать контест без хотя бы одной ботвы.
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится +8 Проголосовать: не нравится
                        ===============================================
                        Есть оптимизации извращенские, а есть идейные... в А как раз решение жюри с нормальными  оптимизациями поэтому палево и не проходило
                        • 13 лет назад, # ^ |
                            Проголосовать: нравится 0 Проголосовать: не нравится
                          =====================
                          "Идейная ботва", хм, прикольный термин, мне нравится =)
          • 13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Да, у нас так и было.
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
наверное не будет ни одного гран-при, в котором в условии не будет косяков
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что-то не могу в первый уровень написать, странно.

    Расскажите, пожалуйста, а как решать задачи Q (про вып. оболочку) и N (про даты).

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

      Q - хз. N - если P > 10 ^ 5, то бежим по всем числам которые кратны P и в тупую проверяем, если меньше, то динамика на цифрах числа.

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А как в динамике кратности учитывать?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          f(i, r, l)  i - сколько цифр осталось, r - остаток от деления на P префикса, l - флаг меньше/больше/равно
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      Мы N решали так. Преподсчитываем в лоб для чисел от 0 до 10 ^ 6, сколько таких "хороших" чисел дает остатки от деления на P, равные 0 ... 10 ^ 6. Далее идем по первым 6 цифрам 12-значных чисел (включая числа с ведущими нулями), если они хорошие, находим для них кол-во подходящих вторых половин по похдодящему остатку от деления на P. Ну и всякие важные тонкости, например нельзя состыковать половинки вида 000001 и 000001 для множества цифр, не содержащего 0.

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У нас такое же решение, но не хватило 8 минут, чтоб его додебажить и Д. Обидно. Могло бы 9 зайти...
    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Для нахождения выпуклой оболчки достаточно для каждого X, которых не более [0, 1000007) найти наибольший и наименьший Y. Но у нас возникла проблема в долгой генерации (Xi,Yi). Тогда найдем периоды, через сколько зациклится Xi и Yi  - X_len, Y_len. Далее пробегаем по всем X из [0, 1000007), смотрим где он первый раз встретился, и дальше прыгаем по массиву Y с шагом X_len, беря индекс по модулю Y_len.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как из второго решается (про диету Деда Мороза). Вся беда в точности, или вообще неправильное понимание условия? Решали и бинпоиском по коэфу кратности, и бинпоиском корня k-ой степени, и прямым взятием сишного корня...
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    Я решал двумя бинпоисками, первый, если p > q, то от 0 до 1, второй, если q > p, от 0 до 100000. Eps=1e-15 у меня. 

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Извините, а вы про какую задачу? Я что-то никаких диет не вижу...
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Там в их втором дивизионе несколько другой проблем-сет просто был, насколько я понял. Это не второй дивизион опенкапа.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Бинпоиск? оО
     q=pow(P/(Q+0.),1/(k-1.));
     bn=Q*pow(q,n-1.);
     printf("%.5f\n",bn);
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Где можно добивать?

      Такое же решение тоже оправляли, ВА1. Названия файлов проверяли, сэмпл и наши тесты проходило, тупые баги искала вся команда примерно час.

      Словом, фэйл, решить 7/10 за 3 часа до конца, 9/10 за 2 часа до конца, и при этом не решить последнюю.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        На сколько я знаю, команда из моего универа пыталась сдать такое же решение, но только считая сразу член последовательности .
        Q*pow(P/(Q+0.),(n-1.)/(k-1.));
        И также ВА1 раз 11 подряд) Я не могу даже такой тест подобрать на котором оно челенджится. И это какой-то реальный фэйл.
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Что там с задачей C див1?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    У нас зашла только на Java. (это про opencup.ru )

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

    В задаче C проходило, наверное, любое решение на Java, и почти ничего не проходило на C++. (это про div1 опенкапа :)

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

      В задаче С не проходило немного недооптимизированное решение на Java и проходило дооптимизированное на C++

      И это если решение типа , где b —  индекс простого, считалось правильным. А то может там ещё какая-то хитрость есть.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Странно, у нас сразу зашло тупейшее решение на c++ (как только заработало за нормальное время локально - сабмитнули, никаких проблем с ТЛ не было). Делали так - meet in the middle по множеству простых, первый набор чисел (~1.5 миллиона) сортируем, второй - генерим "жадно" (сами числа не нужны, нужен только ответ, поэтому если пришли в состояние (n, {pi}), где , где уже были раньше, то возвращаем ответ).

      Ну а если совсем тупой перебор не заходил - так это уж проблемы участников, нефиг лажу толкать ;)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Мы вот додумались до meet in the middle, но до бубна не додумались =) В итоге работало локально где-то 5-6 секунд на макстесте, ну и не зашло соответственно.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Автор предполагал, что нужно придемать две оптимизации - такое запоминание и предподсчет чисел для нескольких первых простых. 
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Можно подробнее про бубен? Я сделал так: генерим левую часть, сортируем её, перебираем правую, бинпоиск для нахождения количества валидных пар. На макс тесте было немного больше чем TL, но переписав на Java, все прошло. Генерация чисел и перебор - рекурсивные. 
        • 13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Ну вот есть рекурсия для второй части. Там 2 параметра - n и сколько ещё простых, и возвращает она число (а в листьях рекурсии делает бинпоиск). Так вот, если , то сохраним то, что она возвращает, в массив, и при следующем вызове с такими параметрами сразу вернём ответ.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            Спасибо, кажется понял. Перебирается левая часть, сортируется, перебирается правая часть. В листьях перебора правой части надо найти upper_bound от целой части N / X. Я не сразу сообразил что, целая часть от N / X в некоторых листьях будет одна и та же.

            P.S. На моем компе работает чуть дольше, чем без запоминания. Но на сервере - ОК :)

    • 13 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится
      Мы, конечно, писали на Java, но у Андрея на макстесте работало 0.1s, кажется. Так что и на плюсах должно было заходить :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится
        Вы - это все-таки вы :)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        А можно посмотреть на код, который на макстесте 0.1с работает?
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Правда ваша - похоже, перепутал эту задачу с какой-то другой. На самом деле работает 1.1s:

          http://pastebin.com/3FTvcHPh
          • 13 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится
            Хм, в этой версии есть переполнение инта, странно, что она работает. Вот вроде без бага:

            http://pastebin.com/2Twssz4p
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Вообще какой-то странный эфект. Автор задачи - Burunduk1, который все-таки пишет на плюсах.
13 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
скоро ли будет проведен реджадж по С (про хоровод)?
и когда разморозка?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите пожалуйста как решать C и G первого дивизиона.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    G: Динамика по профилю с изломом. Профиль - набор из 0 (клетка белого цвета с белыми соседями), 1(клетка белого цвета с 1 черным соседом) и 2(клетка чёрного цвета). На очередное место пробуем поставить черный квадрат. Если после этого меняет свой цвет одна из двух соседних клеток (соседняя вверх или влево), то тогда мы не рассматриваем такой переход из этой маски, потому что вместо того, чтобы сначала ставить белый квадрат, а потом принудительно закрашивать его черным, мы в неком другом профиле сразу поставили чёрный.
    Ну или пробуем поставить белый квадрат, если у клетки нету двух чёрных соседей.
    O(3W * W * H * W)
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      А от куда а вас еще одно *W взялось?

      UPD. А по коду понял. Можно избавиться от *W, если заранее предподсчитать что происходит при постановке какой клетки рядом с какими.

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      G еще можно запихать:D Дп по обычному профилю в лоб. Заметим, что валидных профилей толщины 1 - около 2000, профилей толщины 2 - около 100000, а толщины 3 - около 8*10^7. Предпросчитаем все валидные переходы для профилей толщины 3 в виде [номер профиля толщины 2]->[номер профиля толщины 1] и запишем в массив векторов. Будем считать dp[n][профиль толщины 2], используя предпросчитанный массив. Как считать - вроде бы очевидно)) Итого решение за O(n * 8*10^7) с мелкими хаками. Это работает около 4с.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
так в Харьковском див1 14 тест задачи Хоровод уже исправленный или нет?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На дорешивание опенкапа сдавать можно
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А вообще WA 14 - это OK после реджаджа с почти 100% вероятностью.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кто-нибудь знает как предполагалось решать задачу А с Гран-при Петергофа?

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Бфсом с двух концов.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится
      Ух ты! Зашло в дорешивании бфсом с двух концов.

      А почему это быстрее, можно как-то осознать? Наверное же можно искуственно сделать, чтобы именно в среднем слое было мало состояний?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Если верить разбору, то получается так, что либо очень много стенок и тогда мало достижимых состояний или стенок мало, тогда очень большая середина. Насколько я понял, получившийся граф можно считать почти случайным.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не уверен, что такие тесты существуют.
        IMHO, если в поиске с двух сторон, расширять ту из половин, в которой на предыдущем ходу было меньше вершин, то это должно ускорить скорость нахождения решения.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а можно где-то досдавать задачи ?
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Как скоро в дорешивание появятся задачи IX чемпионата?
13 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится
Может кто-то дать пароль с опен капа?
13 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Кто-нибудь что-нибудь знает про объединение результатов? 

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

Кто знает, как решалась Е div 1? Мы пытались пропихнуть динамику по вектору (количество компонент-деревьев каждого размера) + количество компонент с 1 циклом, но там выходило порядка 8М состояний, что едва ли вписывалось в МЛ и работало несколько минут на макстесте:(

  • 13 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится
    У меня считалось количество компонент валентности 1 каждого размера - таких состояний 1.3M (каждая компонента имеет валентноть 0 либо 1, но компоненты валентности 0 нам не интересны - только их суммарный размер, который получается вычитанием).
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      М-да, это надо обладать особым талантом, чтобы ввести левый параметр в динамику, который все усложняет и никому не нужен:(
      Спасибо!
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Внезапно! После того, как я начал всегда проводить ребро от компоненты самого большого размера, а не самого маленького, количество состояний на тесте "50 0" упало с ~1.295М до 1276. Правда, получает ВА по точности (при умножении на 249 9 знак теряется), но ВА 60 показывает, что это верное решение. Интерестно, знали ли о нём авторы:)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Нас этот результат тоже поразил. Все оптимизили и оптимизили и тут вот вдруг решение стало работать бесконечно быстро:)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится
        Да, так действительно в очень много раз быстрее. Теоретически, правда, не знаю, как хорошо оценить. Но интуитивно (а также если при отладке вывести все просмотренные состояния) понятно: например, из разбиения на слагаемые 50 = 1 + 1 + 1 + ... + 1 не получается других размера ровно 50, кроме 50 = x + 1 + 1 + 1 + ... + 1, то есть всего 50 из 204 226 разбиений, следующие тоже получаются не более чем с двумя числами, отличными от единицы, и так далее. А если проводить ребро из самого маленького слагаемого, получаются чуть ли не все разбиения на слагаемые.

        Правда, самый долгий для такого решения тест — не 50 0, а что-то типа разбиения 50 = пара троек + десяток двоек + сколько осталось единиц. Но даже на таких тестах работает очень быстро (не оптимизированное решение с map <vector <int>, int> [51] укладывается в 0.4 секунды).

        Кстати, в этот раз жюри для разнообразия было “добрым” и ставило ограничения в большинстве задач по не самым оптимальным даже асимптотически решениям.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вроде B рассказывали на разборе, но интересно было бы еще раз послушать решение.

Кроме того, вопрос: есть ли полиномиальное решение для произвольного графа, а не только дерева, для такой же задачи?

И тот же вопрос для задачи с полуфинала - есть ли полиномиальный алгоритм, позволяющий сказать, сколько нужно добавить ребер в произвольный неориентированный граф (в задаче с полуфинала было дерево), чтобы в нем не осталось мостов?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

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


    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В задаче B для произвольного графа, наверное, тоже работает.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    и как же решать задачу В? для тех, кто не смог попасть на разбор
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Заметим, что если в дерево добавить ребро vu, то все ребра на пути по дереву из v в u перестают быть мостами. 
      Нужно обладать такой струтурой данных, которая умеет хранить дерево, на пути помечать ребра и говорить сколько ребер непомеченных.
      Это Heavy-Light Decomposition c деревом отрезков с массовыми операциями.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Burunduk1 рассказывал более простое, по его словам, решение с LCA, но упомянул и это, сказав, что вы его сдали.

        Есть ли у вашей команды идея решения с LCA (и что-то там было про дерево из 4*k вершин)?
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Хмм.. На контесте я сдал то решение, которое описал выше. Ну в решении нужно было lca юзать, для того, чтобы разбить путь в дереве, на два вертикальных пути.
          Какой-то идеи про LCA и 4 * k вершин не было.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +16 Проголосовать: не нравится
          Более простое решение с LCA:
          1) Разобьем каждое добавляемое ребро <v,u> на 2: <v,lca(v,u)> и <u,lca(u,v)>
          2) Для каждой вершины предпосчитаем время входа и глубину.
          3) Возьмем в дереве только интересные вершины - концы добавляемых ребер и lca соседних в порядке обхода DFS'a пар таких вершин (для этого просто сортировали ребра). Сожмем ребра.
          4) Теперь запустим DFS на графе из этих вершин и решим задачу втупую (посчитаем кол-во покрытых ребер). Мы на самом деле не запускали DFS, а эмулировали его, отсортировав интересные вершины по времени входа.
      • 13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится
        Дерево отрезков не нужно: нам ведь просто нужно посчитать длину объединения отрезков оффлайн :)
        • 13 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          На самом деле разница небольшая в масштабах всей задачи, ведь из дерева отрезков нужна только одна функция, set на отрезке, а это не больше 10 строчек.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
С призами для онлайн учасников тишина?)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится
    А можно выспаться? пожалуйста!
    Организация Чемпионата для онсайт участников, а их было около 300 человек, - это несколько бессонных дней и ночей.
    Всё что было обещано - будет 
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      а дорешивание будет где нибудь открыто?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А можно узнать, что произошло с задачей E  у команды ХНУ им. В.Н.Каразина: Челноков, Гризун, Подлесная ?
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

        Отправка была за 10 секунд до конца контеста и тестирующая система не успела загрузить себе решение (поскольку ее выключили почти сразу после контеста). В итоге решение было протестировано позже (примерно в 20 часов), когда систему снова включили. Решение оказалось правильным.

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
            С одной стороны, нельзя не порадоваться за такое везение команды (жаль, только что до награждения всё не прояснилось)....
            Но всё таки осталась неясность. В таблице сразу после разморозки у этой команды было 3 неудачных отправки, последняя - в 4:59. После "окончательного подсчета" - оказалось 3 неудачных отправки + 1 удачная в 4:59. Внимание вопрос: на последней минуте было 2 сабмита или один?
            И ещё:  на закрытии одна из команд получила специальный приз за удачный сабмит на последних долях последней секунды контеста. Почему же не обработался тот, что отправлен "за 10 секунд до конца контеста"?
            Наверное, я сам тут ответил на свой вопрос, но было бы приятно получить авторитетное подтверждение. :)
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да, действительно, было 2 отправки в 4:59:10 и 4:59:50.
            И вторая из них была последней успешной отправкой на контесте.
            К сожалению, не я отвечал за тестирующую систему, поэтому не знаю причины, по которой она не успела загрузить сабмит.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится
        Я ни капельки не удивлен тем, что мой сабмит проверили через 6 часов. Это нормальная ситуация! Как обычно идеальная организация! Но теперь без "слешей" :) Слава Богу задачи готовили хорошие ребята. 

        Кстати отправки по E у меня одинаковые, но одни получали ТЛ, а последняя прошла. Та же ситуация с J: 6 сабмитов одного кода 3 ТЛ и 3 ОК (причем прошли они за 0.1 сек из 1 допустимой) :) 
        В общем завидую тем, кто сдавал задачи в джадже, а не в этой великолепной ситсеме!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to solve problem I ?
You could write answer in russian.:)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Заведем массив used[v][n] - были лы мы в вершине v так, что когда пришли в нее мы уже прошли по n ребрам, которые сопадают с нужной последовательностью. В цикле для всех непосещенных used[v][0] запускаешь такой дфс (например рекурсивный, второй параметр - глубина рекурсии). Если пришли в состояние used[v][k] - выводишь текущий путь. Так как надо найти лексиграфически наименьшее, то списки смежности для всех вершин надо заранее посортировать.
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А результаты Open Cup, случайно, не будут учитываться при распределении призов?
А то я сравнил эту и эту таблицы и обнаружил, что если их слить, у нас будет 6 место. Сертификат на хостинг "Оптимальный" все-таки!

Вообще таблица какая-то странная, как так вышло, что Egor решил 7 задач, а три плюшевых медведя - восемь?