Задачка о товарах.

Не так часто в работе можно встретить интересные задачки. А два года назад во времена работы в логистике, мне одна такая попалась. Фактически, заказчик описал алгоритм, и его надо было реализовать:
Пусть есть Q единиц товара. Есть k точек, по которым необходимо распределить товар. При этом точка i может принять не более qi товара. Также заданы пропорции p1, ..pk, по которым необходимо распределить товар. То есть, если нет ограничения qi, то точка i получает (pi * Q)/(p1 + ...+pk) товара(забудем на время об округлении).

Алгоритм распределения товара таков:

1. Найдем одну из точек таких, что qi <= (pi * Q)/(p1 + ... + pk). Тогда положим точке i товара qi и вычеркнем ее из дальнейшей работы (положим k = k -1, Q = Q — qi, удалим qi и pi).


2. Продолжаем шаг 1 до тех пор, пока не перестанем находить такую точку.


3. Каждой из оставшихся точек положим (pi * Q)/(p1 + ... + pk) товара.


3. *. На самом деле в пункте 3 есть проблема с округлением, которую я опустил. Реально же алгоритм может выглядеть так. Положим m = Q mod k. Отсортируем точки по qi. И первые k - m точек получат [(pi * Q) /(p1 + ... + pk)], оставшиеся же ](pi * Q) / (p1 + ... + pk)[. Где [] - округление вниз, а ][ - вверх.

Если реализовывать такой алгоритм, то шаг 1 может повториться k раз (например у точек большой излишек товара). Тогда итоговая сложность такого алгоритма O(k^2).

Можно придумать эквивалентный алгоритм со сложностью O(k * logk). А именно, отсортируем все точки по отношению qi / pi.
Тогда, все точки, которые мы находили на шаге 1, фактически окажутся в начале. И алгоритм привратиться в следующий:

1. Пока qi <= (pi * Q) / (p1 + ... + pk) , аналогично первому шагу пред. алгоритма полагаем товара qi...


2. .Для оставшихся точек выполняем пункт 3*.

Во-первых, несколько слов о корректности исходного алгоритма.

Верно следующее утверждение.

Если точка j подходит под вычеркивание, а вычеркнута точка i, то после этого точка j все равно подходит.
Докажу.
Не умаляя общности пусть i = 1, а j = 2.
Фактически дано q1 <= Q * p1 / P(можем выбрать точку 1), и q2 <= Q * p2 / P (можем выбрать точку 2), надо доказать, что q2 <= p2 * (Q - q1) / (P - p1) (т.е. , что можем выбрать точку 2, после того, как выбрали точку 1).
Действительно, покажем, что Q*p2 / P <= p2 * (Q - q1) / (P - p1). После преобразований получается P * Q - Q * p1 - P * Q + P * q1 = P * q1 - Q * p1 <= 0 (из первого нер-ва).

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

Также верно следующее утверждение.

Пусть точки упорядочены по qi/pi. Тогда если точка i+1 может быть вычеркнута, то и точка i также может быть вычеркнута. Не ограничивая общности, положим i равной 1, а P = p1 + ... pk.

Докажу это простенькое утверждение.
Фактически, дано q1/p1 <= q2/p2 (условие упорядоченности) и q2 <= (p2 * Q) / P (можем вычеркнуть точку 2).
Необходимо показать, что q1 <= (p1 * Q ) / P, то есть что можем вычеркнуть и точку 1.

1. q1 <= q2 * p1 / p2.


2. q1 <= (p1 * p2 * Q) /(P * p2).
   То есть q1 <= (p1 * Q) / P, что доказать и требовалось.

Еще нужно итоговое утверждение об одиноковости вычеркнутых точек.
Утверждение.
Из последнего утверждения и следует эквивалентность алгоритмов.

Интересно, что решение очень простое, а анализ и доказательство заставляют немного подумать.:). Аналитики местные говорили, что пользователи не понимают сложных алгоритмов. И я её когда-то сделал на интуиции(то есть не доказал, но почти понял, что это так).

А вот и не динамика! SRM 453 Div 1 500.

Прикольную задачку решил на днях.
Спортивный турнир, играют N команд. За победу команда получает w очков, за ничью d. Дано, какая команда сколько набрала очков в конце турнира(Points[i]).
Требуется подсчитать минимальное суммарное количество игр, которое должны сыграть команды, чтобы получить такие очки, либо вывести, что такая комбинация очков не возможна.

Обозначим максимально число очков S(в условии задачи не превосходило 10000). Кстати, N по условию не превосходило 50.

Сразу в голову приходит динамика, но я не смог придумать лучше, чем O(N * S * S), что понятно не успевает.
Однако, есть довольно простое и интересное решение.
Наблюдения:
1. Нужно либо максимизировать, либо минимизировать суммарное число ничьих.
2. Пусть D[i] число ничьих, которые сыграла команда i. Тогда конфигурация D[1], ...D[N} ничьих описывает корректный турнир, тогда и только тогда, когда сумма всех элементов четна, и удвоенные максимальный элемент не должен превосходить сумму всех элементов.

Пусть gcd = GCD(d, w); -- GCD = наибольший общий делитель.

Таким образом нам достаточно на начальном шаге D[i] максимально возможным, так что существует число побед W[i] i-й команды, что D[i] * d + W[i] * w == Points[i];

А затем производить итерации, каждый раз делая, пока возможно:
1. Проверяем корректность текущей конфигурации пункты (1 и 2). Если корректна, то обновляем минимально число матчей.
2. Полагаем D[i] = D[i] - w / gcd;

Если каждый раз максимальный элемент выбирать за O(N), то сложность получается O(N * N * S). Что достаточно для решения задачи. Однако, можно поддерживать очередь с приоритетами, и сложность падает до O(N * Log(N) * S). А с помощью двух списков вообще можно сделать за O(N * S).

Как уменьшить число ошибок в программе

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

Меня достали ошибки, которые я делаю в программах. Причем я делаю их и в олимпиадных задачах и в промышленных.

Наиболее известные способы борьбы с ошибками в промышленно программировании:
1. Тестирование (Unit-тесты).
2. Взгляд со стороны (либо сам через какое-то время, либо Code review). Парное программирование сюда же.
3 Знание системы и понимание прикладной области.

Но как быть, если они не спасают? Что, если ошибки проходят? Можно увеличивать качество исполнения этих практик, но важно пытаться уменьшить, а лучше вообще избавиться от ошибок. В олимпиадном же программировании использовать эти практики почти не возможно(первую и вторую в ACM можно, но лучше бы без них).

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

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

2. Въедливость. Очень важное качество, так нелюбимое слабым полом. Всегда должна быть мысль: "а что, если?". Все краевые и нестандартные случаи должны быть продуманы. Иначе, очень обидно, написав сложный функционал, сделать ляп в проходном месте.

3. Вообще, кодерский опыт(то есть те самые ошибки и работа над ними). Ты должен знать свои слабые стороны. Типа забываю проверить на null, деление на ноль, выход за пределы массива, переполнение, опечатки, дублирование и долго-долго продолжаем. Может вести табличку допущенных ошибок?

Вообще, эти же факторы отвечают за качество и тестирования, и code review.

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