Я увидел халявную задачу: дан двудольный граф, найдите мощность максимального множества вершин, между любыми двумя вершинами которого нет ребер.
Мне давно известно, что ответ равен (число вершин в графе) - (размер максимального паросочетания). Ограничения на n <= 1000 * 1000, рёбер O(n) время 2 секунды. Я знаю что в таких условиях алгоритм Динница легко найдет поток.
Моё решение, посланное под GNU C++ получило MLE, однако перепослав его в MSVC я получил AC, прога отъела 245 мб памяти.
Автор контеста считает, что все впорядке.
Ок, полагаю у автора есть решение O(1) времени и памяти, поэтому типа все ок.
Но давайте обратим внимание на ограничения еще раз.
Если бы n и m были до 5000 стал бы я писать поток? - Нет.
Если памяти было 64 мб? - Тоже нет.
И что, я должен был воспользоваться экстрасенсорными способностями, чтобы понять хитроумный замысел автора?
Если ограничения предполагют решение потоком, то эти ограничения должны быть лояльны к участникам, и превосходить показатели авторского решения в несколько раз.
Если вы не предполагаете таких решений, так ставьте человеческие ограничения, которые их исключают.
Я считаю автор задачи и команда готовившая контест облажались, а расплачиваюсь я.
Доколе?
UPD: Кроме того, получилась задача на тупую формулу, которую придумывали всяко-разно, а другие ломали. Контест, где 20+ взломов у одного участника, ИМХО не очень правильно подготовлен.
В пример можно взять SRM'ы, вы видели, где у участников 19 челенжей по одной задаче? как правило такие ситуации связаны с кривыми чекерами, или неточностью условия, и большинство таких контестов стали нерейтинговыми, из-за факапа, который авторы признали, не прикрываясь тупыми отмазками.