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

Codeforces Beta Round #80 - неофициальный разбор
Автор AlexanderBolshakov, 13 лет назад, По-русски
A-div2:
Вычисляем разность n - 10 (т.к. пиковая дама оценивается в 10 очков). Если разность находится в промежутке [1;9] или равна 11, то ответом будет 4, т.к. карт с такими номиналами существует по 4 штуки на номинал. Если разность равна 10, то ответом будет 15, т.е. 4 десятки, 4 вальта, 3 дамы (пиковая дама из колоды извлечена) и 4 короля. Во всех остальных случаях ответ равен нулю (по очевидной причине).

B-div2/A-div1:
Достаточно воспользоваться следующим рекуррентным соотношением: count[i] = count[i - 1] + 1 + (answers[i] - 1) * i, и учесть, что count[1] = answers[1]. Массив answers[i] обозначает количество ответов на i-ый вопрос, count[i] - количество кликов, необходимое для ответа на i-ый вопрос.
Пояснение к формуле:
Чтобы ответить на первый вопрос, нужно перебрать все возможные варианты ответа на него. Чтобы ответить на i-ый вопрос, нужно узнать правильный ответ на (i - 1)-ый вопрос и далее перебрать все ответы на i-ый. Первая попытка делается за 1 клик, последующие - за i кликов (т.к. мы начинаем отвечать сначала).

C-div2/B-div1:
При помощи DFS находим количество циклов в графе и проверяем его на связность. Если граф связный, а цикл один - значит это Ктулху, в противном случае это не Ктулху (К.О.).

D-div2/C-div1:
Основная часть данной задачи - найти закономерность заполнения ячеек патронами. Найдем эту закономерность по индукции. Если патрон один - его можно поместить куда угодно, но т.к. нам нужна лексикографически минимальная строка, поместим его в самую правую ячейку. Теперь разберем случай с большим количеством патронов. Когда у нас один патрон находится в крайней правой ячейке, ячейки с той же четностью оказываются для нас проигрышными, а остальные - соответственно, выигрышными. Т.о. по идее, мы должны заполнять заведомо проигрышные ячейки справа налево, а после их заполнения заполнять справа налево и выигрышные ячейки. Но... это верно лишь для четного количества ячеек. Для нечетного количества ячеек второй патрон выгоднее посылать в предпоследнюю ячейку (т.к. количество выигрышных ячеек все равно не изменится, но зато при лексикографическом сравнении такая строка будет меньше). Далее заполняем аналогично с четным количеством ячеек.

E-div2/D-div1:
Считываем все запросы и сортируем их по b. Далее используем ДП для всех запросов с b < 500 (т.к. запросы у нас отсортированы, для запоминания ответов нам хватит одномерного массива размера n), а остальные вычисляем наивным алгоритмом. За объяснение того, зачем следует выполнять сортировку, спасибо Александру Миланину (Milanin).

E-div1:
Эту задачу я пока не решил :).
Разбор задач Codeforces Beta Round 80 (Div. 2 Only)
  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
C-div2/B-div1: достаточно проверить то, что ребер и вершин ровное количество, и после этого - в ДФС проверить лишь связность. Если граф из условия связный и вершин и ребер одинаковое количество, то простой цикл в нем всегда ровно 1.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Далее используем ДП для всех запросов с b < 500

Вы либо напишите пометку (К.О.), либо распишите, что это за ДП.

→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Cant it be translated in English
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Я думаю, стоит чуть-чуть разжевать задачу Е(див2).
Давайте разделим запросы на два типа: к первому типу отнесем запросы у которых b меньше некоторой константы q (какой именно рассмотрим позднее), ко второму типу, соответственно те, у которых b > q. 
Решим задачу для запросов второго типа наивным алгоритмом, просто посчитав сумму всех элементов массива. Очевидно, что для каждого запроса второго типа будет не более нужных элементов массива. Тогда все запросы мы выполним за время . 
Решим задачу для запросов с b ≤ q. Рассмотрим отдельно запросы с каждым конкретным значением b.  Для каждого запроса нам нужно посчитать сумму элементов массива, номера которых не меньше a и равны a по модулю b. Тогда пройдемся по массиву с конца и на каждой итерации будем поддерживать массив p, где pi - сумма пройденных элементов массива номера которых дают остаток i по модулю текущего b (в данной группе запросов). Тогда, если мы в некоторый момент находимся в ячейке v и разбираем группу запросов с некоторым b, то в данный момент мы знаем ответ на все запросы с a = v и фиксированным b. Тогда за полный пробег по массиву мы ответим на все запросы с фиксированным b. Для запросов первого типа мы решили задачу за время O(p· q).
Получаем решение задачи за время . Таким образом q стоит приблизить к . 
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    Добавил бы следующее к этой динамике: для случаев с b < 500 можно ещё оптимизацию сделать: если b<числа ограблений с этим b, то наивный алгоритм работает быстрее. Ведь так мы проходим весь массив коров, а так только часть (если у нас 5 ограблений с b=10, то мы пройдём 5/10 массива коров с наивным алгоритмом (каждый раз мы будем проходить 1/b часть массива максимум).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, можно, да. Только не совсем понятно, зачем. Если реализация нормальная, то оптимизации не нужны, а если реализация кривая, как была у меня на контесте, то и оптимизации могут не спасти. 
      → Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

По поводу D(div1). Непонятно, зачем разделять запросы на два типа. Реально решение еще проще.

Решение. Посчитаем наивно все запросы. Единственная оптимизация, которую мы сделаем - сгруппируем запросы (a, b) и (a', b), если a mod b == a' mod b. Ясно, например, как посчитать (2,3), (5,3) и (11,3) за n/3 операций без всякой дополнительной памяти, ДП и т.д. Все решение - сортировка запросов.

Доказательство. Чтобы ответить на (a,b) нужно сделать n/b операций. Но т.к. мы сгруппировали модули, то надо обработать не более b таких запросов. Получаем, что за обработку 2n элементов можно выполнить не менее 3 запросов, за 3n - не менее 6, и т.д. Итого время работы - O(n * sqrt(p)).

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

    Ну, под ваше решение, очевидно, подбирается худший случай (такой, что не найдется никаких пар, чтобы a mod b == a' mod b) - очевидно, для решения с просчетом всех ответов для данного b это наоборот лучший случай. А "посчитать (2,3), (5,3) и (11,3) за n/3 итераций" - это как раз еще один вариант ДП. Пусть и с O(1) дополнительной памяти.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну подбирается - и хорошо, доказательство-то для худшего случая. Я не говорю, что это решение быстрее, просто его описание занимает три строчки.
      → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А где здесь ДП? Просто линейный проход по массиву. Циклом вроде такого:
      for (int i = a % b; i < n; i += b) { ... }
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ДП - решение сложной задачи путем разделения ее на перекрывающиеся подзадачи и решения каждой из этих задач не более одного раза. В данном случае и линейный проход по массиву попадает под это определение. Просто нам достаточно запоминать всего одно значение - предыдущую сумму, это Вас и смущает.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится
          Хм, ну тогда 90% олимпиадных задач - это ДП. Взять даже этот раунд КФ.
          Задача А: Мы идем циклом и накапливаем сумму. Та же ситуация что в задаче Д. Можно считать ДП.
          Задача B:  Как работает дфс? Он берет одну вершину, идет из нее в остальные, помечая ее как использованную. Т.е. после одного перехода получаем граф без одной вершины, т.е. сводим исходную задачу к задаче размерности на 1 меньше. Чем не ДП?
          Задача С: Там даже в "разборе" написано "будем решать задачу индуктивно", что подразумевает сведение к меньшей размерности. Тоже ДП.
          Задача D: описано в предыдущем посте.
          Задача Е: нахождение макс. потока сводится к последовательному вызову функции дфса, а как мы выяснили из задачи Б, это ДП.

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

          И меня смущает, изречение, написанное несколькими постами ниже: "Это Вам должно быть стыдно, что Вы не можете увидеть и/или закодить ДП применительно к данной задаче" и как пример дан пост OBepkJIokEP. Вы можете называть динамикой все что угодно, но если это определение не является общепринятым, то не нужно его повсюду использовать.

          Точно так же можно называть телевизором все, у чего есть дисплей и долго удивляться, почему когда Вы на вопрос "Который час?" отвечаете "Не знаю, забыл дома телевизор", люди искоса на Вас смотрят.
          → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    А если i-ый запрос будет парой (1,i), сложность вашего алгоритма будет O(n*p), что примерно 10^10, что очевидно и в 4 сек не зайдёт. Или я не понял вашего алгоритма?
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

      Нет, сложность будет n/1 + n/2 +... n/i + ... - p-я частичная сумма гармонического ряда. Это примерно O(n*ln(p)).
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
I'll translate the remaining part a bit later...
→ Ответить
13 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Честно говоря, разбор мне не понравился, поскольку очень многие вещи оставлены не завершенными. 
Вот например, задача А (див2): "Во всех остальных случаях ответ равен нулю (по очевидной причине)." 
Так трудно написать почему? Все же, ее не все сделали, мне кажется. Или, с таким же успехом, можно было бы просто написать "А (див2) - очевидно". 
Далее в задачи Е (див2), я так понимаю, сначала не было объяснения - для чего сортировки. Так а почему было браться за разбор задач, если нет ПОНИМАНИЯ решения задач? Тем более, нет разбора задачи Е (див1). 
На мой взгляд, разбор выглядит, как план действий. Но если бы я хотел знать, "что нужно сделать, чтобы сделать эту задачу", я бы мог просто взглянуть в чужой код. А в разборе, мне кажется, как раз должен делаться акцент на том, ПОЧЕМУ нужно так делать, а не на том, ЧТО нужно делать. 
Простите за, возможно, слишком критическое мнение, но я просто с этого разбора почти ничего не почерпнул, и очень бы хотел увидеть разбор от авторов.

Edit: Ну и где же обяснение о сортировке в Е(див2)? :/
Edit2: Я уж молчу о обяснении ДП в Е(див2). Ну не стыдно ли?!
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вы так наезжаете на меня, как будто сами решили все шесть задач с раунда. Извиняюсь за лирическое отступление.
    По поводу A-div2. Разве существуют карты с отрицательным/нулевым номиналом или с номиналом больше 11? Не очевидно? Если не очевидно, я бы посоветовал сменить род занятий...
    По поводу E-div2. Вообще, я с критикой по большей части согласен. Но, во-первых, tunyash уже все разжевал. Можете считать разбором не то, что написал я, а то, что написал он.
    По поводу "Edit2: Я уж молчу о обяснении ДП в Е(див2). Ну не стыдно ли?!". Это Вам должно быть стыдно, что Вы не можете увидеть и/или закодить ДП применительно к данной задаче. Тем более, в комментариях описано два варианта ДП (вот и вот).
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну и опять бесконечно много оставлено на капитана Очевидность. :(
      И... Да нет, лучше промолчу.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
translate.google.com
seems pretty good at this. And that's how I read Russian and Japanese posts.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Решил D sqrt-декомпозицией, оффлайново.

Запросы так же делятся на два типа: b <= B и b > B. (в моем решении B = 175). Вторые обрабатываем, что называется, втупую, а с первыми поступаем так:

Заметим, что для конкретного b ответ является суммой на отрезке одной из таких последовательностей:
a[0], a[b], a[2b], ...
a[1], a[b+1], a[2b+1], ...
.................................
a[b-1], a[2b-1], a[3b-1], ...

Теперь к каждому такому воображаемому массиву применяем sqrt-декомпозицию. Сохраняем все эти данные в трехмерный массив p, где p[i][j] содержит предпросчитанные суммы одной из указанных выше последовательностей (здесь i = b, а j - это индекс первого элемента в массиве a (от 0 до b-1)).

Каждый массив p[i][j] имеет длину sqrt(n / i), а общее число элементов в p равно sum{i*sqrt(n/i)} = sum{sqrt(ni)} <= B*sqrt(nB) <= 1500000, что прекрасно лезет в память.

TeX-формулы в предпросмотре выглядели настолько ужасно, что решил их не применять
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Поддерживаю - спасибо за разбор. А то некоторые прикапываются, как будто автор был обязан его писать. Если не нравится - можно было просто не читать, и уж тем более ничего не комментировать по поводу качества.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    Присоединяюсь...

    Все когда-то начинают писать в первый раз и вот в этот момент их нужно поддержать. Если есть огрехи -указать, неточности - подправить и направить в нужное русло.
    Другое дело что "молодой и горячий" сам "вызывает огонь на себя" тем, что вместо фраз "Спасибо за замечание, учту..." или "А как бы Вы (ты) посоветовали (вал) написать?" и т.д. в ответ пишет "Можно подумать..."
    Так что желательно сбросить пар и перейти в более конструктивное русло.
    А если кому-то не нравится - так здесь неофициальный разбор, как указано в теме, возьмите и предложите свой. Опять же пользы будет всем, как и автору поста, так и писавшему, да и остальным тоже, особенно тем, кому это интересно

    Так что не бойтесь критики и не реагируйте на неё резко - подумайте и попробуйте написать по другому... А потом всё начнёт потихоньку получаться.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      А обсуждение задачи "Принадлежность точки отрезку" Вы уже забыли...

      Теперь по теме. Вообще, критика-то уместна, но не в таком виде. Какие фразы меня явно задели:
      1. "Так а почему было браться за разбор задач, если нет ПОНИМАНИЯ решения задач?" - ну откуда ему знать, понимаю я или нет? Во-первых, все я понимаю.
      2. Уже процитированное "Я уж молчу о обяснении ДП в Е(див2). Ну не стыдно ли?!" - А действительно, за что мне должно быть стыдно? Ну не описал я подробности ДП, ну и что? Чем его не устраивает описание, которое дал tunyash? Лично для меня оно более чем понятное. Даже если человек не может его понять - зачем переходить на наезды?
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится
        Вам ответили, что в  лекции был указан именно целочисленный подход для решения подобных задач. И отвечать желательно не через месяц на другом ресурсе, а сразу и там же - в группе. Каждой информации - своё место.

        Ну так я и написал, что реакция с обеих сторон резковата. Кто-то резковато покритиковал, автор - сразу чуть ли не с обидой в ответ резковато отвечает, что и перешло почти, как Вы правильно заметили, во взаимные наезды.
        Если бы все обращали внимание на все резкие слова  сказанные в их адрес, это было бы что-то невообразимое.
        Поэтому прочли - там где сочли нужным - ответили, а если не сочли нужным отвечать - не ответили. Но в любом случае нужно просто анализировать не только решения, но и сообщения. И задавать себе вопросы, типа "А как бы элегантно написать так, чтобы в следующий раз подобных "наездов" не было?" Это по сути процесс взаимного общения, пусть и дистанционного и разные люди по разным причинам иногда на одну и ту же фразу реагируют по разному. Поэтому и тут нужно каждому учится искусству подобного интернет-общения.
        Так же и в реальной жизни: один раз с женой пошутил - рассмеялась, так как хорошее настроение было, а иной раз за подобную шутку можно чуть ли не поварёшкой по лбу получить... :)  

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

          Задача:
          Принадлежность точки отрезку
             Определите, принадлежит ли заданная точка отрезку.

          Технические условия
             Входные данные

             Шесть целых чисел - координаты точки и координаты начала и конца отрезка. Все числа не превышают по модулю 10000.

             Выходные данные

             Вывести "YES", если точка принадлежит отрезку, и "NO" в противном случае.

          Разбор:
          Достаточно проверить, что модуль разности длины отрезка и суммы расстояний от заданной точки до его концов практически равен нулю, или что аналогично: меньше очень маленького числа, например 10^-10.

          P.S. Обсуждаю эту тему тут по той причине, что из ДЛКШ я был выкинут за неактивность (начавшуюся как раз после обсуждения этой задачи).
          → Ответить