А вот и не динамика! 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.

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