Я увидел халявную задачу: дан двудольный граф, найдите мощность максимального множества вершин, между любыми двумя вершинами которого нет ребер.
Мне давно известно, что ответ равен (число вершин в графе) - (размер максимального паросочетания). Ограничения на n <= 1000 * 1000, рёбер O(n) время 2 секунды. Я знаю что в таких условиях алгоритм Динница легко найдет поток.
Моё решение, посланное под GNU C++ получило MLE, однако перепослав его в MSVC я получил AC, прога отъела 245 мб памяти.
Автор контеста считает, что все впорядке.
Ок, полагаю у автора есть решение O(1) времени и памяти, поэтому типа все ок.
Но давайте обратим внимание на ограничения еще раз.
Если бы n и m были до 5000 стал бы я писать поток? - Нет.
Если памяти было 64 мб? - Тоже нет.
И что, я должен был воспользоваться экстрасенсорными способностями, чтобы понять хитроумный замысел автора?
Если ограничения предполагют решение потоком, то эти ограничения должны быть лояльны к участникам, и превосходить показатели авторского решения в несколько раз.
Если вы не предполагаете таких решений, так ставьте человеческие ограничения, которые их исключают.
Я считаю автор задачи и команда готовившая контест облажались, а расплачиваюсь я.
Доколе?
UPD: Кроме того, получилась задача на тупую формулу, которую придумывали всяко-разно, а другие ломали. Контест, где 20+ взломов у одного участника, ИМХО не очень правильно подготовлен.
В пример можно взять SRM'ы, вы видели, где у участников 19 челенжей по одной задаче? как правило такие ситуации связаны с кривыми чекерами, или неточностью условия, и большинство таких контестов стали нерейтинговыми, из-за факапа, который авторы признали, не прикрываясь тупыми отмазками.
http://goo.gl/9EPuI
А если решение потоком автором не рассматривалось? Какой поток, когда можно dfs?
Ну участники зря писали сложные формулы с кучей частных случаев. Я всегда стараюсь избежать такого, особенно когда это просто. Вот недавно необходимо было решить систему из 3-х уравнений с двумя переменными, но при этом одно из уравнений могло быть вырожденное. По-этому я написал Гаусса за 5 минут и не думал вообще. Сегодня над математическим решением в B я вообще не думал и даже не думал, что его можно придумать.
На топкодере в руме 20-25 человек? А тут?
Вот, кстати, сейчас заслал, вставленный в твой код, мой Хопрофт-Карп адаптированный под эту задачу: http://codeforces.net/contest/142/submission/1041614
+1
авторы пофейлились с ограничениями и не признают этого.
Под тупым переборным решением ты имеешь в видуперебрать все тройки чисел, что А*B*C = n?
Смотри. Дана задача найти кратчайший путь в графе с ребрами положительного веса n <= 1000, m <= n^2. Ты пишешь дейкстру (без всяких исхищрений, а так, как обычно её пишешь) и вдруг получаешь MLE на этапе системных тестов, ты скажешь это нормально?
Если такое случается, то либо алгоритм крайне не оптимален, либо автор неправильно выставил ограничения.
Я уже сотню раз объяснил почему тут второе. все. достали уже. хватит.
Поздравляю вас, вы смогли найти в этой задаче, как в ней можно использовать поток. Вы его даже умудрились запихать. Казалось бы, претензий к автору быть не должно никаких? Всё в задаче намекает на то, что она не на поток - её позиция в контесте, то, как её сдают, общая (даже не знаю) боянистость и очевидность идеи задачи. Всё-таки соревнования по программированию - они и на здравый смысл тоже.
А то, что под MSVC зашло, а под g++ - нет, это претензии к производителям микроскопов - такое бывает часто, разные компиляторы компилируют по-разному.
1) прочитал задачу
2) понял, что знаю к ней решение
3) решение подходит под ограничения
4) пишу и сдаю
такого алгоритма придерживался бы каждый, при соблюдении условий (умеет читать, знает решение, умеет оценить ограничения к алгоритму, может написать решение быстро).
И 500 из 1000 таких участников получили бы АЦ, другая половина ML/TL
Из этого я заключаю что ограничения гавно.
Какое же "подходит под ограничения", если 245 мб на одном компиляторе и ML на другом? Это значит вы оценивать затраты памяти не умеете, либо код пишете неоптимальный.
И повторюсь - такой алгоритм работает не всегда верно. Сегодняшний контест тому доказательство. Здравый смысл рулит. Иногда стоит пять минут подумать и за пять минут написать нормальное решение, чем придумать за первую минуту какую-нибудь гоморихню и писать её два часа.
По теме: автор считает контест кривым потому что его решение не прошло. Толсто, очень толсто с его стороны :)
"Я думаю, что автор не должен был задумываться о решениях потоком в такой задаче, потому что его придумает 10%, а пойдёт писать - 1%."
А я думаю, что если автор тырит задачу из другого источника, он должен понимать, что знакомые с этим бояном будут решать его именно так, как предполагалось в первоисточнике. Первоисточник это задача с acm.sgu.ru, который порядочные acmщики прорешивали в стародавние времена. Задачка была на укладку доминошек по полю, некоторые клетки выжжены.
upd: возможно, я путаю задачу. но то что это боян - факт.
То есть если в первоисточнике решено вообще неправильно, то никто не имеет права дать задачу с тем же или почти тем же условием, но правильными тестами ??? ??? ???
А я вот люблю давать именно такие подлянки! (Участники харьковской Зимней школы--2010 и NetOI подтвердят...) И что, тут я чем-то категорически неправ?
Я писАл исключительно о том, что считаю совершенно абсурдным довод "если задача откуда-то взята, то нельзя менять ограничения".
А насчёт того, является ли именно эта задача именно Вашей или откуда-то взятой -- я ничего не_знаю и тем более ничего не_говорил. Прошу прощения, если мой текст действительно можно так понять.
Вы обвиняете автора контеста в том что заданные ограничения(в которые Вы не уложились) заставили Вас подумать не о том решении. Отлично! А 245мб на MSVC - это скорее просто везение для данного компилятора. Половина решений получат АС - да, половина людей с мл'ным решением удачно напишут контест, значит они просто лакеры, можете порадоваться за них.
Я не говорил "Я красавчег" в чем кривизна, косяки, и неправильность ограничений тебе убогому снова рассказать? ты только с 115-го раза понимаешь? Не согласен со мной, я понял уже. Здесь много не согласных, и да мне насрать что вы так думаете. У меня другие взгляды на задачи. Мне многое уже сказали здесь, что-то я принял, что-то нет. Но это не твое дело блеать.
Вот каждый хочет ляпнуть что-то. Уже много сказали, хватит переливать из пустого в порожнее, о всем уже упомянули. Прежде чем снова сюда писать прорешай прежде пару тысяч задач, как те, к чему мнению в этой теме я прислушался. А твое следующее сообщение и читать не стану.
Выжигание клеток, если не ошибаюсь, идею решения с BFS не портит.
P.S. А, нет, ошибаюсь.
Да хоть -100 сделайте к каждому коментарию - мне насрать.
Я решил множество задач, обсуждал их с другими участниками сообщества, и не того сообщество что собралось здесь (здесь очень много новичков, флудеров, школьников, на этот счет существует занимательная статья, не лишенная смысла). Я знаю какими ограничения не должны быть.
Если вы(большинство из вас) как-то по другому смотрят на этот вопрос - ваше право.
Если вы довольны таким качеством задач, таким оно и останется.
Я умываю руки, больше в этой теме не пишу.
Я проанализировал, ограничения позволяли мое решение, как я прикинул.
И прикинул я правильно, об этом говорит AC на другом компиляторе.
Авторы виноваты в кривых ограничениях. Если у них такое офигенное решение, почему вершин так мало? Зачем так много памяти? Исходя из того что есть быстрое ограничения "нормальные", в том плане что хватает. Но так "от балды "ограничения не делают.
Ну здесь я может промахнулся, но вообще какой только лажи тут небыло в качестве B. И в качестве А тоже.
Ты для себя как хочешь считай, я проталкивал поток в Петрозаводске на 10^4 вершин и 10^5 ребер. Я тогда еще не умел динниц писать. И про хопкрофта-карпа не слышал до сего дня.
upd: В авторском решении был динниц
Здесь граф специального вида, видимо поэтому ваш алгоритм проходит.
В общем случае, на произвольном графе паросочетание потоком быстрее работает, чем не потоком. Считать ли потоком Хопрофт-Карп, я не знаю, давайте забудем про него пока.
Да поправит меня AlexSkidanov, он всегда писал паросочетание потоком. Я вначале писал потоком, потом узнав приведенный факт стал писать более крутым "Скидановским" потоком. И только потом в научных целях изучил и потестил на разных задачах этот самый метод дфсом и чередующихся цепочек. Поток победил.
По сути, паросочетание дфсом, это и есть проталкивание потока поиском дополняющей цепи(пути), так что спор ниочем. Как мы видим, алгоритм Хопрофта-Карпа вообще сложно отнести к одной из двух категорий. Но думаю придумывался он в терминах потока. Ну и мне проще так размышлять. Ограничения делаются так, чтобы проходили неоптимальные решения, и решения на жаве, поэтому я всегда пишу поток и не парюсь.
Другое дело, что бывают плохие ограничения.Это не так. Ограничения должны выставляться так, чтобы асимптотически верные решения, с константой не сильно отличающейся от авторского проходили. Обычно ставят ТЛ удвоенный от авторского. Не правильно ставить ТЛ 1 сек, если заоптимизированное авторское решение работает 0.9 сек. Я сейчас говорю не относительно данной задачи, а вообще. Это общепринятая норма, минусани сообщение если ты идиот.
Кстати, по поводу векторов - если Вы собрались их использовать, будьте готовы к тому, что они потребляют в 1.5-2 раза больше памяти, это существенно. Самому иногда приходится переписывать решения чтобы прошли, я считаю, что это из той же серии, что поднимать ограничения в 10 раз для Scala, Haskell и пр. небыстрых языков.
Давайте попросим администрацию сделать галочку в интерфейсе участника "не умею оценивать время работы программы и объём памяти, который она использует".
Если участник поставил эту галочку, то для него TL и ML увеличиваются, например, в 2 раза.
Такой бонус новичкам :)
Ты тупой? Я же сказал что это утверждение не относится данной задачи. Спроси у Снарка, как ставят ограничения. Вот как раз для векторов и ставят нормальные ограничения на память. Это не про эту задачу я говорю, а вообще.
Для тупых, снова оговорюсь, что в сообщении выше, и в данном речь не идет о какой-либо конкретной задаче. Речь идет о задачах вообще, за исключением специальных, где суть задачи в какой-то хитрости навроде прочитать инпут два раза.
Вы какой-то больно агрессивный.
Я хочу сказать, что ограничения неправильные.
Либо маленький ML, либо большие n и m, будь они до 700, все бы было нормально. Можно сделать n и m до 10000, тогда тоже адекватные ограничения будут.
Одна всего идея была, с которой могли бы согласиться. А именно:
Автор задачи должен минимизировать матожидание количества посылок, которые на грани TL/ML. Всеми разумными способами. Если таких решений много, это вносит в результаты элемент случайности, не очень явно зависящей от участников. Если же их одно-два — ну, бывает. Всякий раз кто-нибудь да умудрится.
Например, автор может придумать как можно больше решений и по каждому определиться, должно ли оно проходить с запасом или не проходить с запасом. Далеко не всегда, конечно, это возможно.
Но ты и этот пункт продолбал глупой руганью и отношением к собеседникам. Ну, кому что.
Спасибо, ты более понятно сформулировал мою мысль.
Я не хочу писать уже, достало. Но и не писать ответы на эти %№;;"№; комментарии тоже невыносимо, они все извращают и переиначивают, противоречат простым истинам.
По поводу ругани, ты посмотри сколько дерьма на меня тут вылили, ты бы себя хорошо при этом чувствовал?
И ниакой путиницы нет, просто этот коментрий является ответом на вопрос про суть поста, в ответе на это я снова вернулся к задаче, а как иначе то?
Детсад какой-то. Хорошо, я идиот.
Лампочка нормальная.
Рот кривой :)