Перечитав по второму разу правила региональных соревнований, так и не понял, какие вариации могут быть в составе команд и как пользоваться заменами. С финалом все понятно, никаких замен, кто вышел из 1/2, те втроем и едут без изменений. А вот для простых смертных правила так четко не прописаны.

Был бы благодарен сообществу за прояснение 2ух вопросов

1. может ли изменяться состав команды от 1/4 к 1/2 и как?

2. возможно ли, что запасной на полуфинал будет одним из участников другой команды на 1/4?

UPD: 1/2 NEERC, СПб. 1/4 южный подрегион, Саратов.

Думаю почти каждый участник олимпиад хорошо знаком с алгоритмом нахождения подотрезка массива с наибольшей(наименьшей) суммой элементов за O(n).

Просматривая список задач по универским лабам, увидел в одном номере под разными буквами три, вроде бы схожие задачки. а)/b) классика — найти подотрезок с max/min суммой. А вот с) — найти подотрезок массива с суммой, наиболее близкой к нулю. Подумал немного и осознал, что не вижу решения ни за O(n), ни за n*log(n). То ли меня клинит и не вижу чего-то простого, то ли составитель методички отнесся халатно к расположению задач и оформлению требований к ним.

Собственно вопрос к сообществу CF — есть ли решение этой задачи с асимптотикой лучшей, чем квадратичная?

UPD за предложенное решение n*log(n) спасибо I_love_Tanya_Romanova. Остается вопрос о существовании линейного решения...

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

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

В процессе обдумывания задачи была отброшена идея постепенного построения эллипса по 4ем опорным точкам. Контр-пример: (0 41) (10 40) (-10 -40) (0 -41). Через данные точки можно единственным образом построить эллипс, но он не будет искомым. На момент сдачи решений осталось две идеи: копать в сторону преобразований системы координат, или работать в текущей, отталкиваясь от того, что в границу искомого эллипса обязательно войдут 2 точки. Количество точек позволяет перебрать все пары, не придумал как найти минимальный эллипс, проходящий через 2, и покрывающий остальные.

Тип bool (boolean итп в различных языках программирования) требует по сути 8 бит на одно значение. Соответственно и время работы с таким массивом неоправданно возрастает. В делфи проблема решалась например так type MyBoolean = array [0 .. (maxn div 256)] of set of byte; с последующей проверкой (i mod 256) in (MyBoolVAR[i div 256]) . Все это работает за приемлемое время и расходует нужный объем памяти. Вопрос в следующем: как реализовать что-либо подобное в с/с++ ? Пробовал bitset, set, просто работал с побитовыми сдвигами над unsigned char. Добивался желаемого расхода памяти (~ 1 бит / логическое значение), но время работы оставляло желать лучшего...