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

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

Предсказание Панорамикса (задача A, 2-ой дивизион). Автор задачи - Alex_KPR

 

 

В начале условия задачи подробно описано, что называется простым числом, и что называется следующим после x простым числом. Суть задачи сводилась к тому, чтобы проверить, является ли m следующим после n простым числом.

Поскольку n гарантированно простое, нужно проверить два случая:

1. Число m является простым, и

2. Между n и m нет других простых чисел

Действительно, если между n и m есть некоторое простое число k, то m уже никак не может быть следующим после n простым. Ограничения в этой задаче небольшие, поэтому решать её можно следующим способом:

for(int i=n+1;i<=m;i++)
{
    if (prime(i))
    {
        if (i==m) return "YES"; else return "NO";
    }
}
return "NO";

где prime(i) - любая возможная проверка числа на простоту.

Другое простое решение этой задачи - учесть тот факт, что ограничения не превышают 50. Можно найти все пары чисел n и m вручную и написать решение в виде серии условий, примерно так:

if (n==2 && m==3) return "YES";
else if (n==3 && m==5) return "YES";
else ...
else if (n==43 && m==47) return "YES";
else return "NO";

Такое решение тоже проходило все тесты.

 

 

Асимптотика зависит от конкретной реализации и варьируется от O(1) до O(n + m).

Если вы не знаете, почему ваше решение получает вердикт "wrong answer", то возможно, вам стоит проверить своё решение на тесте "2 5".

 

 

Депрессия (задача B, 2-ой дивизион). Автор задачи - Marishka

 

 

Первое, на что нужно обратить внимание - при движении одной стрелки другая остаётся неподвижной. Фактически, это означает, что теперь нам нужно решить две подзадачи:

1. Определить, на какой угол повернуть минутную стрелку, и

2. Определить, на какой угол повернуть часовую стрелку

В условии сказано, что стрелки-усы Когсворта двигаются равномерно и непрерывно. Это значит, что при любом, даже очень малом увеличении времени Δt и часовая, и минутная стрелка сдвинутся на некоторые углы.

Поскольку число минут всегда целое благодаря формату HH:MM, то каждая минута будет добавлять ровно 360 / 60 = 6 градусов. В свою очередь, на угол поворота часовой стрелки влияет и количество часов, и количество минут. Каждый полный час будет добавлять 360 / 12 = 30 градусов, а каждая минута - (360 / 12) / 60 = 0.5 градусов.

Таким образом, нужно суметь вырезать из первоначальной записи HH:MM количество часов и количество минут, после чего применить описанные выше формулы для нахождения ответа.

Также нужно обратить внимание, что аналоговые часы не различают время до полудня и после полудня, поэтому ответы для 08:15 и 20:15 будут совпадать.

 

 

Асимптотическая сложность решения - O(1).

Если вы не знаете, почему ваше решение получает вердикт "wrong answer", то возможно, вам стоит проверить своё решение на тестах "20:15" и "00:00".

 

 

Герои (задача C, 2-ой дивизион; задача A, 1-ый дивизион). Автор задачи - Alex_KPR

 

 

Поскольку героев всего k = 7, а групп три, то задачу можно решать полным перебором. Для этого рассмотрим все случаи размещения героев в каждой из трёх групп и выкинем из рассмотрения некорректные разбиения - такие, при которых хотя бы одна группа оказывается пустой.

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

Из всех этих способов осталось выбрать наилучший и выдать в качестве ответа.

 

Сложность алгоритма - O(3k· k2).

 

 

Сброс наковальни (задача D, 2-ой дивизион; задача B, 1-ый дивизион). Автор задачи - dagon

 

 

В этой задаче нужно было определить вероятность того, что уравнение имеет хотя бы один действительный корень, при условии что величины p и q выбирались равновероятно и независимо в своих интервалах [0;a] и [ - b;b].

Для этого необходимо и достаточно чтобы дискриминант D = p - 4q был не меньше нуля. Для решения этой задачи можно было нарисовать на плоскости (p, q) прямоугольник с вершинами в точках (0,  - b), (a,  - b), (a, b) и (0, b) и линию p = 4q. Каждая точка прямоугольника соответствует возможным значениям p и q, а линия делит всю плоскость на две части - где уравнение имеет действительные корни, и где оно их не имеет. Тогда вследствие равновероятности и независимости выбора p и q ответ есть площадь пересечения прямоугольника с областью p ≥ 4q, отнесенная к площади самого прямоугольника, в случае его невырожденности (a, b ≠ 0).

Если ровно одно из чисел a или b равно нулю, прямоугольник вырождается в отрезок, и искомая вероятность равна отношению длины пересечения отрезка с областью p ≥ 4q и всего отрезка. В случае a = b = 0 ответ на задачу, очевидно, равен 1.

 

Асимптотическая сложность решения - O(t).

Если вы не знаете, почему ваше решение получает вердикт "wrong answer", то возможно, вам стоит проверить своё решение на мини-тестах "0 1", "1 0" и "0 0".

 

 

Боброжуй-0xFF (задача E, 2-ой дивизион; задача C, 1-ый дивизион). Автор задачи - Marishka

 

 

Допустим, что, находясь в вершине v, можно для каждого её прямого потомка vi найти пару значений  < xi, yi > , где xi - максимальное количество бобров, которое может съесть боброжуй, стартуя из вершины vi и возвращаясь в неё же, а yi - количество бобров, которое останется в вершине vi после того, как её посетил боброжуй.

Отсортируем всех потомков vi по убыванию значения xi и будем посещать этих потомков vi в отсортированном порядке, пока гарантированно сможем вернуться к корню. Если же после посещения всех поддеревьев в вершине v ещё остались несъеденные бобры, то будем продолжать поедание по следующему принципу: выберем потомка с ненулевым значением yj, сделаем прыжок в эту вершину vj и сразу же вернёмся обратно. Такую операцию нужно повторить максимальное количество раз. Естественно, процесс нужно не эмулировать, а осуществить min(b, yj) раз, где b - оставшееся количество бобров в вершине v.

Таким образом сформирована пара  < x, y >  для вершины v по известным значениям  < xi, yi >  для её непосредственных потомков, где x - количество бобров, которое удалось съесть, а y - это b, количество оставшихся бобров в вершине v.

Ответ - это значение x для стартовой вершины s.

 

Асимптотическая сложность решения - O(n· logn).

Если вы не знаете, почему ваше решение получает вердикт "wrong answer", то возможно, вам стоит проверить своё решение на тесте, в котором дерево состоит всего из одной вершины.

 

 

Ковёр-из-домино (задача D, 1-ый дивизион). Автор задачи - Alex_KPR

 

 

Заметим, что каждая клеточка ковра-из-домино находится в одном из трёх состояний:

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

2. На неё можно поставить только горизонтальную кость домино

3. На неё можно поставить только вертикальную кость домино

Неважно, какие значения записаны в каждой клеточке, важны только их состояния.

Теперь заметим, что если в какой-то паре соседних столбцов j и j + 1 горизонтально расположена кость домино, то эту пару столбцов размера n × 2 можно вырезать из общего ковра, не побоясь разрезать какие-либо другие кости домино. То есть, эта пара столбцов может заполняться фишками домино независимо от других столбцов.

Если n чётно, то могут заполняться независимо не только пары соседних столбцов, но и столбцы единичной ширины, причём единственным способом - размещением всех костей домино в них вертикально.

Получаем следующую формулу: dj = (dj - 2· qj - 2) + (dj - 1· pj - 1), где j - количество обработанных столбцов, pj - количество всех возможных способов заполнить костями домино только j-ый столбец (это значение будет равно нулю или единице), а qj - количество всех возможных способов заполнить только j-ый и j + 1-ый столбцы.

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

Получаем: dj = (dj - 2· qj - 2) + (dj - 1· pj - 1) - (dj - 2· pj - 2· pj - 1). В dm будет находиться искомый ответ.

Осталось посчтитать значения pj и qj. pj находится достаточно просто: если n чётно и в столбце j нет клеточек, находящихся в состоянии "сюда можно ставить только горизонтальную кость домино", то ответ 1, иначе 0.

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

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

 

Асимптотическая сложность решения - O(n· m).

 

 

Марсианская кухня (задача E, 1-ый дивизион). Автор задачи - dagon

 

 

Задача решалась с помощью преобразования инверсии.

Инверсия - это преобразование, переводящее точку с полярными координатами (r, φ) в точку . Утверждается, что инверсия переводит прямые или окружности в прямые либо окружности. Причем образом может быть прямая тогда и только тогда, когда исходная прямая или окружность проходила через начало координат (центр инверсии).

Пусть тарелка является кругом с координатами центра (R, 0) и радиусом R, а Гондурас - кругом с центром в (r, 0) и радиусом r. Тогда Гваделупа и Бультерьеры будут расположены так, как показано рисунке слева:

Рисунок 1. Первоначальное изображение

Рисунок 2. После преобразования

Применим преобразование инверсии. Тогда край тарелки перейдет в прямую , а край Гондураса , Гваделупа и Бультерьеры станут окружностями, как показано на другом рисунке. На картинке, получающейся после инверсии, найти образ k-го Бультерьера не составляет никакого труда, координаты его центра равны . Чтобы найти радиус Бультерьера, проведем прямую, проходящую через начало координат и центр его образа, найдем две точки пересечения. Можно показать, что прообразы этих точек есть диаметрально противоположные точки на бультерьере. Соответственно, ответ есть половина расстояния между прообразами найденных точек.

 

Асимптотическая сложность решения - O(t).

 
Разбор задач Codeforces Beta Round 69 (Div. 1 Only)
Разбор задач Codeforces Beta Round 69 (Div. 2 Only)
  • Проголосовать: нравится
  • +41
  • Проголосовать: не нравится

13 лет назад, # |
Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится
Красивый, удобочитаемый пост.
Автору спасибо за задачи и разбор!
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Для задачи про "Боброжуя" написано:
Асимптотическая сложность решения - O(n).
Мое решение в задаче про "Боброжуя" в точности совпадает с решением жюри, но почему-то мне сдается, что асимптотика там далеко не O(N)... Там все-таки для каждой вершины производится сортировка всех потомков. Так как значения могут приниматься достаточно большие, то сортировка подсчетом явно тут не поможет. Лучше указать асимптотику O(NlogN). Только не говорите про radix-sort, с его-то константой лучше STL-евским sort'ом посортить :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    спасибо, Паш, копипастил снизу и написал фигню :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    Простой заменой stl'евского sort'а на не менее stl'евский nth_element получаем уже что-то близкое к O(N).
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
> Боброжуй-0xFF (задача E, 2-ой дивизион; задача C, 1-ый дивизион).
> Отсортируем всех потомков vi по убыванию значения xi
> Асимптотическая сложность решения - O(n).
Вы умеете сортировать за O(n)?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ну вообще можно, но в этой задаче не нужно :)

    исправлено
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Как? У упомянутой Павлом radix-sort сложность всё равно O(n*log(n)) - пускай и логарифм берется по большому основанию. Сортировка подсчетом тут не подходит, т.к. диапазон ключа слишком большой. Просто интересно ;)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        гм, хотел написать "заведём массив z длины 105, для каждого элемента ai сделаем z[ai]++, а потом пройдёмся по массиву z", но сразу не учёл, что сортировка происходит много раз

        ну нет, так нет =)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я по-моему писал, что значения там могут быть далеко не 105. И писал, что сортировка подсчетом здесь явно не в тему :)
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Cделайте, пожалуйста, координатную сетку почётче. Я секунд 40 думал, где же центр инверсии.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    постараемся сделать

    пока что можешь нажать на картинку и увидеть её в увеличенном размере
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Извиняюсь, невнимательно прочёл условие задачи, вопрос снят.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Разбор задачи B  360/60 = 5 :D  

Дальше читать разбор задачи B не стал) 

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

    не мудрено ошибиться в трёх страницах текста A4 =)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Где можно больше почитать о методе решения задачи E?
13 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится
Почему край тарелки перейдет в прямую x=2/R, а не x=1/(2*R)?
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Ни у кого ни возникало проблемы с задачей Боброжуй-0xFF ?
Сколько ни пытаюсь решить, схватываю TLE or MLE на 52 тесте. До него все проходит на ура.
Если кто-нибудь сталкивался с подобной проблемой, пожалуйста отпишитесь !
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    (йес! я горжусь своими тестами! =))

    тест 52 представляет собой "солнышко" - есть вершина-центр, из которой выходит 99999 лучей

    возможно, это информация будет полезной
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хе-хе..
      Что-то я окончательно запутался.
      Пересматривал свое решение целый день, никаких ошибок не нашел)
      Возможно, конечно, что это тонкость дельф. Косяки с динамической памятью(
      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        может какой-нибудь setlength за линию работает?

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

        ну и конечно тебе поможет локально сгенерённый тест; можешь тогда посмотреть, что именно долго работает
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Спасибо, помогло !
          Сначала считал все и выделил память, а потом пробежался по считанному массиву и построил граф. Решение конечно кривое, зато Ac))
          • 13 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
            Ещё есть такой вариант: делать setlength только когда размер равен kx и увеличивать его в k раз.
            Вроде асимптотически получается O(n· logk(n)) времени и O(n· k) памяти.
            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
              Например если взять k=2, то время будет (на самом деле с 0, а не с 1, не могу подредактировать, но сути не меняет). Для больших k будет еще меньше. Поэтому памяти и времени будет одинаково и ровно nk. В частности, насколько я знаю, так работает std::vector.
13 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится
Саш, объясни мне одну вещь. Зачем на соревнованиях по ПРОГРАММИРОВАНИЮ давать последнюю задачу на чистую математику с одной формулой? Ты на NEERC хоть раз такое видел?

  • 13 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится
    Причем математику совсем не общеизвестную. То есть, как уже упоминалось, "кто знает, тот решит, а для остальных гроб".
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Позволю с Вами не согласиться, если речь идет про студентов. Наверное, у многих есть в программе курсов ТФКП, где преобразование инверсии проходится в достаточной мере для того, чтобы это запомнить и додуматься, как применить.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится
        Так и хочется устроить дискриминацию по цвету штанов.
        А если серьезно, то ни на одном серьезном соревновании такие задачи давать нельзя. 
        Например, варианты:
        1. Х знает эту задачу. Время ее решения будет практически 0.
        2. Х пришел первый раз на соревнования по программированию с межнара по математике и читает эту задачу первой. Он набирает баллов примерно как решивший А+В+С (потому что А+В+С надо еще написать же, не забыв аккуратно посмотреть ограничения в В). Смешно, не так ли? За одну строку кода.
        и т. д.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +2 Проголосовать: не нравится
          Ну почему вы так уверены, что это очень дикая математика?
          Точно так же можно сказать про любой серьезный алгоритм, будь то алгоритм Эдмондса за куб, будь то Диниц за VElogV, и так далее. 
          Здесь требуется лишь базовое понимание полярной системы координат (а сортировать по полярному углу умеют наверное все) (или комплексных чисел), и полчаса времени, чтобы разобраться в этом. Возможно, проблема в том, что это не рассматривается при подготовке к олимпиадам?

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Сколько тебе нужно времени, чтобы написать решение на задачу о назначениях? А сколько надо времени, чтобы НАПИСАТЬ решение этой задачи?
            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Решение этой задачи - укладывается в строчек 15.
              Решение задачи о назначениях я умею решать только с помощью мин-кост, и по времени это у меня займет дольше. 
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Решение этой задачи укладывается в одну формулу. Смотри, например, решение участника Sergey.Bankevich на самом туре.

      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, еще немного уточнения моей позиции.
        Я бы ни слова не возразил против этой задачи, не будь в ней количества тестов - если бы в ней можно было бы просто применять численные методы для построения цепочки окружностей.
        • 13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Не знаю, согласитесь ли Вы со мной, но в моем понимании, если решать такую задачу обычными численными методами - это некий аналог подхода "в лоб", естесвенно заоптимайзить и аккуратно закодить. Применение подхода  с инверсией - это уже надо подумать. Я уверен, что Вы не с рождения знали про потоки, про дп по маскам, к примеру.  На мой взгляд, данный подход стоит включить в программу подготовки к олимпиадам, он гораздо легче многих базисных алгоритмов (то же Диница, к примеру).
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Ну, соревнование все-таки по алгоритмическому именно программированию, и преобразование инверсии - не просто одинокая формула, а достаточно идейный и общий подход, это развивает мышление, почему бы и нет?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Я Вас ещё поддержу, добавив, что иной раз в задачах по спортивному программированию приходилось даже аналитически брать интегралы или же определять сходимость бесконечных рядов. А кое-кто из адептов дискретной математики непрерывную, даже с первого курса, не помнил совсем, вот и жаловались...
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        Никто не против брать интегралы и прочее, конечно.
        Я против того, чтобы задача на математику в одну формулу стоила 1/3 соревнования.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну, я в таком случае против того, чтобы считать такие задачи задачами на треть соревнования. 
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            Да-да, тут как-то вообще не поймёшь, сколько баллов за такую задачу давать. Много - возмутятся те, кто не знают такого метода (он ведь редко используется в спортивном программировании!); мало - возмутятся те, кто знают такой метод (его ведь проходят в любом вузе на практически любой специальности, откуда люди идут в спортивное программирование!). И даже какое-то среднее количество баллов не выверишь...
            Поэтому, ИМХО, такие задачи лучше всего давать на ACM.
            • 13 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится
              Вы очень верно подметили насчет универа. Вообще говоря, да, такие задачи лучше всего давать на АСМ. Даже на ТС почти никогда не встретишь ничего подобного
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Неверно подметили насчет универа, как минимум у нас не проходят, а у нас все-таки не самый последний вуз
                • 13 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                  Тогда, если не секрет, как называется ваш факультет и специальность?

                  Ну, просто у нас на этот метод ушли 2 лекции матанализа в 4 семестре (ну не только на этот, а вообще, на подобную теорию в ТФКП)
                  • 13 лет назад, # ^ |
                    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                    СГАУ, факультет информатики, специальность "прикладная математика и информатика"

                    А хотя кто знает, может это на старших курсах будет. Но я сомневаюсь
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      Забавно)
                      У меня факультет прикладной математики и информатики, специальность "Компьютерная безопасность". Видимо, у нас в странах различаются программы для таких специальностей. (я студент Белорусского ГУ).
                    • 13 лет назад, # ^ |
                        Проголосовать: нравится 0 Проголосовать: не нравится
                      Вот так вот и живём. Вы прикладной математик, а я бывший физик, однако у меня был курс ТФКП - вот сейчас раскопал старый конспект, там слова инверсия вроде не встречается, однако вообще параграф про свойства дробно-линейных отображений есть.
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится 0 Проголосовать: не нравится
                        Забавно, что у меня даже были все эти свойства, что во что переходит. Даже отдельно функция Жуковского проходилась позже)
                      • 13 лет назад, # ^ |
                          Проголосовать: нравится 0 Проголосовать: не нравится
                        У меня было ТФКП, но инверсия там не изучалась
  • 13 лет назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится
    ну во-первых, где-то было сказано, что codeforces - это тоже учебные соревнования; благодаря этой задаче многие участники узнали о новом методе решения некоторых задач на геометрию

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

    в-третьих, на последнем NEERC была очень классная задача с игрой в квадрате 4 × 4, над которой нужно было думать полчаса, а потом писать десять строк

    конечно, соглашусь, что это не самая лучшая задача для codeforces, но её наличие не сломало баланс раунда
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      Полностью поддерживаю. В этой задаче можно было не зная данного метода, попробовать его вывести. Эта задача - из разряда идейных, где нету какого-то конкретного алгоритма (тот же максфлоу), а есть какая-то идея, которую мы развиваем и адаптируем. Имхо именно такие задачи должны быть на финалах.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Я далеко не уверен сейчас, что это пройдёт и по времени, и по точности, но всё-таки эту задачу ещё можно пытаться решать численно, рискованно, с большим объёмом кода, но зато безыдейно: каждый следующий Бультерьер подбирается бинпоиском по радиусу Rk - в смысле, ищем такой радиус, чтобы окружности тарелки, Гондураса и предыдущего Бультерьера (а для k = 1 - Гваделупы), будучи надлежащим образом с этим радиусом сплюсованы и сминусованы, пересекались в одной точке. Вообще-то я это и имел в виду, когда вопил: "Подстава!", - мне раньше метод инверсии никогда не встречался на контестах, а ТФКП у меня было четыре года назад - немудрено забыть всё неюзабельное :-[
        Upd. Нет, пожалуй, я уверен, что не пройдёт. Возможно, даже если свернуть мозг и вывести аналитическую формулу, то всё равно не пройдёт.
        • 13 лет назад, # ^ |
            Проголосовать: нравится -7 Проголосовать: не нравится
          Есть решение за О(N), но при N = 10^4 и количестве тестов 10^4 по времени оно не проходит (константа большая, что обычно для геометрии).
          Будь ограничения поменьше, то и претензий бы к задаче не было: знаешь математический факт - решаешь быстро, не знаешь - решаешь долго, но решить можешь. А здесь ограничения как специально подобраны против "не формульных" решений.
          А вообще, по-моему, задачи со сложностью О(1) на соревнованиях по программированию даваться не должны. Или хотя бы автор должен быть уверен, что, кроме чисто математического, есть еще и алгоритмическое решение.
          Ну, может быть исключение - задачи на подбор закономерности, но там сначала что-то закодировать нужно.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Так ведь задачи вычислительной геометрии чаще всего хоть и за O(1), но там требуется не столько выводить формулы, сколько проводить построения - а вот это уже и алгоритм (какие), и техника (как).
            А про подбор закономерности - вообще сомнительно, что такие задачи допустимы. Я, возможно, неправ, но я придерживаюсь мнения, что любая задача на контесте по правилам ACM или вроде того должна быть такой, что человек с мозгом, калькулятором и набором шпаргалок может полностью придумать и доказать её решение столь же быстро, сколь и тот же человек с мозгом, компьютером и Интернетом. Конкретно - я изменю своё мнение (и буду благодарен за информацию), если мне кто-нибудь покажет задачу на подбор закономерности с финала ACM. То, что на последних четырёх полуфиналах NEERC таких задач не было, - это я знаю точно.
            • 13 лет назад, # ^ |
                Проголосовать: нравится +6 Проголосовать: не нравится
              По-поводу задач на вычислительную геометрию, я считаю, что, если человек с мозгом и калькулятором по известным входным данным может посчитать ответ, то эту задачу надо давать на олимпиадах по математике. Если же такие задачи даются на соревнованиях по программированию, то что ж, значит надо уметь их решать...
              По-поводу подбора закономерности.
              Во-первых, я не писал о соревнованиях высокого уровня. Естественно, что там особые требования к задачам.
              Во-вторых, если Вы считаете, что такие задачи не допустимы, то я готов охотно с Вами согласиться. Это просто был пример, когда основное решение за О(1), но в процессе решения задачи программировать все-таки надо.
              • 13 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Всё-таки хочется доразобраться с задачами со сложностью O(1), и не только с геометрическими, хоть это уже и оффтоп :) Тут же дело в том, что идеальная задача ещё и возникает не из пустых фантазий, а из реальных производственных проблем, что и отражается иной раз в легенде. И ведь написать небольшую софтинку для обработки 100500 экземпляров задачи - это вполне адекватно. Такие задачи актуальны, другое дело, что для соревнований по программированию они довольно просты, поэтому и идут зачастую в качестве утешительных. Разумеется, всё вышесказанное относится только к задачам, где требуется лишь аккуратная реализация, в том числе и разбор некоторых особых случаев, а не сложнейший вывод формулы с использованием теорем, на доказательствах которых защищают кандидатские.
                • 13 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Прочитал, перечитал, не понял.
                  Я не знаю, что такое идеальная задача в спортивном программировании, тем более не знаю из чего они возникают, но точно никогда не ассоциировал задачи с контестов с какими-то производственными  или другими реальными процессами.
                  Конечно, задача может быть из реальной жизни, но на её качество, по-моему, это никак не влияет.
                  • 13 лет назад, # ^ |
                    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
                    =============================
                    Ну, я рассуждал по аналогии. Просто помню, что в знаменитой в некоторых кругах книжечке Козела, где рассказаны все гласные и негласные правила проведения всероссийских олимпиад по физике, было написано, что задачи берутся изначально реальные, а не просто головоломки. Типа так олимпиада куда больше соответствует своей миссии. Было бы логично предположить, что у ACM (у IBM) такие же идеи.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Вы серьёзно считаете, что можно было взять бумагу, ручку и за время контеста вывести метод инверсии? По-моему, "кому дана такая сила, тот небывалый человек".
        Математика, конечно, должна быть на контестах, но она должна быть именно такой. чтобы надо было посидеть и подумать. А здесь же, если ты знаешь метод, то дальше все элементарно, не знаешь - извини, иди учись.
        Хотя да,  образовательную ценность у этой задачи отрицать нельзя =)
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
          Ну, студентам, которые ТФКП проходили  - это несложно все-таки, на мой взгляд. Да и вообще, можно хотя бы попробовать посидеть и повыводить такие вещи.
          • 13 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится
            Тут же дело было не в "вывести". Здесь человеку, не знакомому с ТФКП, в процессе обдумывания задачи должна была прийти в голову мысль: а может попробовать сделать "преобразование, переводящее точку с полярными координатами (r, φ) в точку ", вот интересно, что тогда получится? Именно появление такой идеи я считаю почти невероятным.
            Но мораль-то понятна: учиться, учиться и учиться...
             
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            "Ну, студентам, которые ТФКП проходили..."
            А. Далеко не все студенты это проходили.
            В. Далеко не все люди, участвующие в Codeforces, вообще студенты. 
            Вообще во всей дискуссии по поводу этой задачи грех не согласиться с k-va
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Тарас, ну вот что ты заладил =)

            Ты ещё скажи, что можно рассказать человеку понятие графа (вершины, рёбра, веса рёбер), а потом дать задачу на алгоритм Дейкстры =) Ну а чего, пусть "попробует посидеть и повыводить" -- он же знаком с понятиями =)

            В том-то как раз и соль, что преобразование инверсии -- это тоже в некоторой степени метод. Идея метода Дейкстры -- брать вершины в определённом порядке и релаксировать дуги, выходящие из них; идея инверсии -- преобразовать комплексную плоскость. А придумывание таких методов дорогого стоит =)

            А задачи в стиле "если ты знаешь метод, то дальше все элементарно, не знаешь - извини, иди учись (с)" очень огорчают. Креативность же должна быть: у авторов при составлении, у участников при решении.

            • 13 лет назад, # ^ |
                Проголосовать: нравится +21 Проголосовать: не нравится
              Да, если бы я писал контест и добрался бы до задачи E, она бы меня тоже огорчила :) Задача, конечно, не идеальная в плане недовольства многих участников. Однако, скажу несколько слов в защиту допустимости такого рода задач:

              1). Как уже говорилось, от задачи есть польза в плане обучения. Конечно, не стоит давать такие задачи на ACM ICPC или IPSC и т.п., но на соревнованиях, ориентированных на тренировку (Codeforces, TopCoder, сборы в Петрозаводске), мне кажется вполне уместно дать что-то подобное. Заодно и небольшое разнообразие в раундах :)

              2). По поводу сложности и формулы, стоимостью "1/3 соревнования". Да, она очень сильно варьируется в зависимости от знаний участника (поэтому я против таких задач на ACM ICPC). Но всё-таки участников, решивших эту задачу, гораздо меньше, чем для остальных задач, поэтому, видимо, буква E для этой задачи наиболее подходящая.

              3). Программирование очень сильно связано с математикой. Допустим, один человек изучает STL, а другой в это время читает про геометрические преобразования. Почему же тогда нужно всегда давать преимущество именно первому участнику? Я считаю вполне допустимым дать второму участнику применить свои знания, в разумных пределах, конечно (не стоит увлекаться и давать возможность проявить свои познания обществознания или мировой художественной культуры :) )

              Разумеется, бывают и более красивые и "правильные" задачи, но и эту не стоит сильно осуждать.
            • 13 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится
              Ну, возможно я немного субъективен, потому как мне больше нравятся такие задачи, идейные, чем задачи в стиле "давайте посчитаем сначала минкост, потом запустим еще суфмас, а потом еще 4мерное дп, при этом в 80 случаях из 100 вы влезете либо в TL либо в ML"
              Да и тем более, если знаком с математикой комплексной, то вот это как раз можно вывести, если посидеть и подумать. Не говорю про другие методы и идеи, кое-где самому почти нереально додуматься до чего-то, кое-где можно придумать самому на ходу, это зависит от метода.
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
мы 2 года назад на математическом кружке проходили инверсию
жаль что в 69 раунде в див2 был :(
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

To problem E — Martian Food, I suggest to watch the video "Epic Circles" of Numberphile in youtube in order to get a better explanation and concepts about inverse circles

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

242986607 I solved the A problem like that. I hope it might help someone one day.