goo.gl_SsAhv's blog

By goo.gl_SsAhv, 12 years ago, In Russian

Я увидел халявную задачу: дан двудольный граф, найдите мощность максимального множества вершин, между любыми двумя вершинами которого нет ребер.

Мне давно известно, что ответ равен (число вершин в графе) - (размер максимального паросочетания). Ограничения на n <= 1000 * 1000, рёбер O(n) время 2 секунды. Я знаю что в таких условиях алгоритм Динница легко найдет поток.

Моё решение, посланное под GNU C++ получило MLE, однако перепослав его в MSVC я получил AC, прога отъела 245 мб памяти.

Автор контеста считает, что все впорядке.

Ок, полагаю у автора есть решение O(1) времени и памяти, поэтому типа все ок.

Но давайте обратим внимание на ограничения еще раз.

Если бы n и m были до 5000 стал бы я писать поток? - Нет.

Если памяти было 64 мб? - Тоже нет.

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

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

Если вы не предполагаете таких решений, так ставьте человеческие ограничения, которые их исключают.

Я считаю автор задачи и команда готовившая контест облажались, а расплачиваюсь я.

Доколе?

UPD: Кроме того, получилась задача на тупую формулу, которую придумывали всяко-разно, а другие ломали. Контест, где 20+ взломов у одного участника, ИМХО не очень правильно подготовлен.

В пример можно взять SRM'ы, вы видели, где у участников 19 челенжей по одной задаче? как правило такие ситуации связаны с кривыми чекерами, или неточностью условия, и большинство таких контестов стали нерейтинговыми, из-за факапа, который авторы признали, не прикрываясь тупыми отмазками.

  • Vote: I like it
  • -175
  • Vote: I do not like it