For problem 1241C. Legacy tut.

Here's another idea to solve it in linear time. Whole idea is to become a thug seller, haha! You sell ticket, but you can take it back! Any time! But respect police, ah? So whenever you take ticket back, you return funds. Otherwise you'll never reach k.

Idea

This is how whole thing works. OK, we also swap x and y, so x is always better.

1. All non-x and non-y buyers should wait. You respect their.. booking, but kindly ask them to quit the line. They will get their tickets after you deal with X and Y. Besides those guys will get best price.
2. So, you start selling X, or Y. Whatever it is, you sell most expensive remaining ticket. AND.. if at some point you've just realized, that you could sell even more expensive ticket, but it is sold with lower profit, you just take it back, (give money back) and sell it again with better profit. Buyer who just suffered lose of ticket is to be calmed by buying another (probably cheaper) one.

Здесь пара комментариев (для себя и других) касательно разбора задачи 1238E сделанного пользователями awoo и Roms. Я там не сразу понял — как получается конечная формула для перебора символа.

( заморочился и написал код с трассировкой (см. под катом) )

Давайте вначале придумаем общую суммарную формулу, которая отразит количество всех перемещений, и потом, используя нисходящий подход прийдем к решению.

Двигаясь вправо, для каждого символа $$$s$$$, имеющего на клавиатуре позицию $$$x$$$ будем учитывать все перемещения между ним и символами слева.

Disclaimer: Решение не мое! Я просто разжевал его для себя. Ну и выложил еще здесь.

Недавно я разбирал решение задачи "1221G — Граф и числа"

И самой сложной и непонятной частью для меня был подсчет независимых множеств. Именно сам способ объединения двух под-решений в конечное.

Hi folks!

I think most of you are cool programmers and know several programming languages. Below are some thoughts (and one open-source project) regarding to C++.

Disclaimber

(below is not some super cool algorithm, neither problem solution, rather thoughts, and some may be off-topic proposal, so sorry for that)

Stake

I love the performance you can get by means of C++. If you know what are you doing, you can get awesome results. But syntax... well, I'd like to make it better.

At least following things:

• modularity
• reflection
• set of syntactic sugars.

A. Давид и мешки с конфетами

Сгодится наивное решение, поскольку всего имеется 4 мешка. И по сути нужно сделать неупорядоченные выборки из 4-х, вначале по 1-му, затем по 2 и затем по 3 мешка. Если для какой-то выборки получается, что сумма конфет равна половине сумме всех конфет, то решение найдено, пишем YES. Иначе, если ни одна выборка не подошла, пишем NO.

Мое решение

B. Аня и минимизация

Если k==0, выводим само число.

Если у нас число состоит из 1-го символа.

В этом случае, если k == 1 (а теперь оно точно равно 1), то мы можем заменить это число на 0 (пишем "0"), а иначе — не можем (но в эту ветвь мы никогда не попадем).

Если число многозначное (n>1).

1. Если первая цифра не 1, то меняем ее на '1' и делаем --k.
2. Идем от второй цифры и до тех пор пока не закончится либо k, либо сами цифры. Если мы встречаем цифру отличную от 0, заменяем ее на 0, и делаем --k.
3. Выводим измененную строку.

Мое решение

C. Анади и домино

Ну во-первых. Что такое сам по себе набор домино? Это полный граф из 6 вершин, у которого вдобавок на каждой вершине есть петля. Ребрами такого графа и будут костяшки домино. Т.е. если бы можно было класть костяшки домино на такой граф, то можно было бы на каждое ребро положить по штуке, и это с учетом всех оговоренных в задаче ограничений.

Нам же дается граф в котором количество вершин не более 7-ми.

Если число вершин данного графа 6 и меньше.

То это подграф графа домино. В этом случае на все его ребра также можно положить по костяшке. Поэтому мы просто возвращаем число m (количество данных ребер).

Если число вершин данного графа равно 7.

Надо свести задачу к первому типу. Помните анекдот про программиста и чайник?

Поэтому надо объединить какие-то две вершины в одну. При объединении у пары вершин A и B, с количеством ребер E(A) и E(B) найдутся общие ребра, обозначим их количество C. В этом случае после объединения мы получим граф из 6 вершин с количеством ребер равным m2(A, B) = m — C. В общем надо выполнить полный перебор всех пар вершин и найти такую пару, для которой m2 будем максимальным, и в качестве результата нужно вывести это значение m2 = max(by(A, B), m2(A, B)).

Да, еще один момент, когда мы выполняем слияние двух вершин А и В, что произойдет с ребром, которое соединяет сами эти вершины? Оно превратиться в петлю. Это допустимо, поскольку граф домино допускает по одной петле на каждой вершине. Если такого ребра нет — то соответственно и результирующий граф будет без петель. Это тоже нормально.

Мое решение

D. Марчин и сборы

Вначале давайте рассмотрим пару человек. Они смогут поехать вместе только если маски их знаний полностью совпадают.

Теперь можно расширить это понятие до группы человек. Группа человек с одинаковой маской знаний может спокойно ехать на сборы. С группой мы также можем связать эту маску G. После разбиения на группы останутся одиночки, с оригинальным набором знаний.

Кого может еще взять с собой группа?

• Любого одиночку, чья маска B будет подмаской группы: G or B == G.
• Абсолютно любую группу.

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

UPD: Я нашел косяк в своем решении. Что неверно в предыдущем утверждении?

Если групп нет, то значит никто в этой компании не сможет поехать на сборы, поскольку с ним нет другого полностью совместимого студента.

Алгоритм

1. Выполняем сортировку на группы. С каждой группой связываем маску и суммарный опыт.
2. Проходимся по оставшимся одиночкам. Если для одиночки А, находится подходящая группа G, то включаем его в эту группу (увеличиваем опыт группы на опыт A).
3. Считаем суммарный опыт всех групп. Выводим его в качестве ответа.

Мое решение