Задача с собеседования в лабу СБЕРа

Даны два мультимножества, c одним из них вы можете проводить следующие операции:
1. Выбрать элемент и заменить его на  x * 2.
2. Выбрать элемент и заменить его на  x // 2  (округление вниз).
У вас есть неограниченное количество операций, ваша задача определить возможно ли приравнять второе мультимножество к первому.

Решение:

Обозначим мультимножества как A и B.
1. Для начала заметим выгодное разбиение A на классы эквивалентности x ~ y <=> \exist k >= 0: min(x, y) * 2^k = max(x, y) (иначе говоря если больший элемент может быть получен путём умножения меньшего на степень двойку (т е проводения некоторого количества операций первого типа), то мы будем эти два элемента считать за эквивалентные). То есть нам достаточно проверить множества на равенства меньших элементов из каждого класса (просто каждый элемент множества A будем делить до того момента, пока он делится). Таким образом мы свели задачу к использованию лишь второй операции.

2. Заметим что каждый элемент из множества b порождает с помощью операции 2 ряд различных классов эквивалентности (можно кстати оценить количество этих классов как O(log(x))), тогда нам остаётся лишь распределить выгодно эти классы по элементам из A. Воспользуемся жадным подходом отсортируем множество B, и будем идти от меньшего к большему по элементам и последовательно для каждого элемента перебирать эти классы (то есть просто делить на 2 с округлением и проверять наличие текущего элемента класса в множестве А), в случае если мы нашли элемент совпадающий с элементом из A просто удалим его и закончим перебор классов.

Пример кода (здесь даны множества уже в отсортированном порядке) уже в нашем чате.

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

@algoses