Относительный порядок символов должен совпадать в обоих множествах, поскольку мы не переставляем эти символы. Поэтому множества должны соответствовать общей подпоследовательности исходной и финальной строк. Если какое-то решение сделало k операций, то наша общая подпоследовательность будет иметь длину n - k.

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

Мы можем видеть, что минимальное количество действий равно в точности n - k, где k -- длина наибольшей общей подпоследовательности

По ссылке выше можно прочитать про алгоритм решения задачи НОП за время O(n²) при помощи ДП.

Ясно, что количество вхождений каждого символа все еще должно быть одним и тем же в обеих строках. Кроме того, никакой символ не имеет смысл трогать больше одного раза, а неподвижные символы все еще образуют общую подпоследовательность. Тем не менее, из второго примера ясно, что теперь ответ может быть больше, чем n - LCS(s, t) (здесь LCS(s, t) -- длина наибольшей общей подпоследовательности s и t).

Посмотрим на неподвижный символ s_i и его финальное положение t_j во второй строке. Относительно s_i мы можем только перемещать символы из правой части s в левую.

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

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

Задача тесно связана с задачей нахождения НОП. Что известно науке о сложности НОП? Как показать, что наша задача не проще, чем НОП?

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

Если d' > x, то мы можем продолжить число до конца (можно применить такое же правило, что и для постановки первой цифры). Если d' < x, то число достроить нельзя, значит, мы должны вернуться назад и уменьшить какие-то из более ранних цифр.

Мы можем только уменьшать y до x, поэтому надо найти самый правый y, сделать его x-ом, а потом максимизировать остаток числа (потому что к этому моменту мы уже поставили меньшую цифру, чем на том же месте в n).

Это значит, что n начинается с нескольких цифр x, а потом идет цифра меньше x. Получается, что ответа такой же длины не существует, поэтому надо искать среди чисел меньшей длины.

Это уже несложно самому понять (или посмотреть в спойлерах выше). Ну серьезно.

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

времени, если отсортировать все участки и делать проверки только для соседних,

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

Пускай мы хотим тратить только i-ый товар, тогда нам надо заплатить ε / d_i единиц, так что с нашей точки зрения стоимость будет равна ε·c_i / d_i. Поэтому лучше всего тратить товар с наименьшим значением c_i / d_i.

Разобьем x на маленькие кусочки размера ε и будем выкупать их по очереди. Согласно предыдущему рассуждению, в оптимальном решении мы должны постепенно тратить товары по мере возрастания их значения c_i / d_i до тех пор, пока продавцу не хватит. Товары с одинаковым c_i / d_i можно тратить в любом порядке.

Важно заметить, что нам не надо знать конкретные значения c_i / d_i, если мы научимся их корректно сравнивать для разных товаров. Останется всего лишь применить любимый алгоритм сортировки.

Возможности наши запросов довольно ограничены: ответ -- это просто "да" или "нет", и нам надо научиться сравнивать отношения при помощи таких запросов. Делать это можно так: сперва найдем конфигурацию чисел a_i, при которой с хорошей точностью достигается равенство , после чего будем делать небольшие изменения относительно этой конфигурации таким образом, чтобы равновесие зависело от результатов сравнения c_i / d_i.

Мы знаем порядок, в котором надо тратить товары. Теперь сделаем бинпоиск по тому, какой суммарный объем товаров мы заплатим. Из жадных соображений следует, что любой объем надо тратить, начиная с товаров с маленьким c_i / d_i.

Единственная проблема с выбором Δ в том, что если выбрать слишком большое значение, при сравнении отношений измененные значения a_i могут выходить за допустимые границы [0, 1]. Мы знаем, что в равновесной конфигурации значение всех a_i будет как минимум на 0.1 отстоять от границ. Чтобы изменения не могли вывести нас за границы, достаточно потребовать неравенство Δ max(c_i) ≤ 0.1, поэтому подойдет Δ ≤ 10^- 5.

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

Печальная ситуация. Такое требование может возникать, например, если сортировать отношения при помощи std::sort с кастомным компаратором, который сам делает необходимые запросы по ходу дела. std::sort делает дополнительные запросы к компаратору, чтобы проверить его корректность, например, транзитивность. Это не только тратит запросы, но и может привести к ошибке выполнения, если компаратор плохо сравнивает равные объекты: на равных объектах компаратор всегда должен возвращать false.

Наше сравнение для равных дробей работает плохо. Дело в следующем: в теории при сравнении значение не должно поменяться совсем, а на самом деле из-за погрешностей вещественных чисел оно меняется на очень маленькую величину. В результате, значение может непредсказуемо плясать вокруг x, и сравнения будут возвращать случайные результаты (напомним, что в запросе ? никакие погрешности не учитываются!).

Одно из возможых решений: сделать значение чуть-чуть больше, чем x, чтобы не пострадать от случайных микроошибок.

Также отметим, что многим алгоритмам сортировки (например, слиянием или вставками) вообще не важно, как сравнивать равные элементы, поэтому там такой проблемы нет.

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

.

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

С одной стороны, ясно, что это равно (сумма степеней красных вершин) — (сумма степеней синих вершин).

С другой стороны, на красном ребре (у которого оба конца красные) написано +2, а на синем -2. На нейтральном ребре написано 0. Поэтому сумма счетчиков равна 2(e_R - e_B).

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