Блог пользователя goo.gl_SsAhv

Автор goo.gl_SsAhv, 12 лет назад, По-русски

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

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

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

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

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

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

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

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

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

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

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

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

Доколе?

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

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

  • Проголосовать: нравится
  • -175
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Ну поток на миллион вершин - это всегда много. Даже Диниц будет делать порядка Msqrt(N) операций, что больше миллиарда при данных ограничениях.
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +80 Проголосовать: не нравится
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

А если решение потоком автором не рассматривалось? Какой поток, когда можно dfs?

Ну участники зря писали сложные формулы с кучей частных случаев. Я всегда стараюсь избежать такого, особенно когда это просто. Вот недавно необходимо было решить систему из 3-х уравнений с двумя переменными, но при этом одно из уравнений могло быть вырожденное. По-этому я написал Гаусса за 5 минут и не думал вообще. Сегодня над математическим решением в B я вообще не думал и даже не думал, что его можно придумать.

»
12 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится
"В пример можно взять SRM'ы, вы видели, где у участников 19 челенжей по одной задаче?"
На топкодере в руме 20-25 человек? А тут?
»
12 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится
Задача как задача. Я бы например побоялся бы поток писать на 1000 * 1000 вершин. Попробуй на spoj.pl http://www.spoj.pl/problems/MATCHING/ например попихать Динницей. У меня прошло только после того как я дооптимизировал до алгоритма Хопрофта-Карпа.
Вот больше не нравится, что задача, мягко сказать, баян. Можно много разных частных случаев и разновидностей понаходить, если погуглить "количество коней не бьющих друг другу" или что-нибудь в таком духе. Когда-то давно видел такую задачу на каком-то джудже.
»
12 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
Я долго и позорно тупил над задачей A. Потом написал тупое переборное решение и оно получило Accepted. При этом я еще забыл поставить самое главное отсечение. С ним бы вообще задача пулей залетела. Не думаю, что автором задумывалось такое решение. С ним задача - говно. Без него, я бы даже может и не решил. Деградирую, господа.
Когда я открыл вторую задачу, я чуть со стула не упал. Это же адовый баян. Причем вместо того, чтобы написать "расставьте наибольшее число коней на доске N x M", Сергей написал какой-то изврат, который даже читать сложно. В общем-то даже зная решение, я умудрился неправильно написать ифик. Спасибо Гене Короткевичу, который это заметил. Задачу эту я видел еще в далеком 2006 году. Причем на ACM-Style контесте и там еще и расстановку надо было вывести. Загуглить такое - нефиг делать.
Пара моих знакомых, которые делали раунды на CF, говорили, что Артём Рахов не пускает баяны на CF. Видимо, что-то изменилось в его принципах. Если добавить к этому тот факт, что многие узнали задачу A, то мы получаем два баяна на пять задач.
Что еще можно сказать...
TopCoder 3:0 Codeforces
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -70 Проголосовать: не нравится
    Ага, при таком кривом условии, палености задачи, дерьмовости ограничений, они еще пытаются мазаться что все ОК, это вы идиоты.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится
      Условие помоему вполне четкое. Все ясно расписано. Другое дело непонятно зачем маскировать коней под этих солдат, но это не относится к нормальности условия.
      По ограничениям тоже не согласен - вполне нормальные ограничения. Если бы написал Хопрофта-Карпа, то думаю никаких проблем вообще с ML не возникло. Тут уже ССЗБ.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -22 Проголосовать: не нравится
        Ничего подобного, тупо граф в память плохо влазит.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

          Вот, кстати, сейчас заслал, вставленный в твой код, мой Хопрофт-Карп адаптированный под эту задачу: http://codeforces.com/contest/142/submission/1041614

          230 ms 32 метра памяти.

          UPD: кстати, что на студии, что на гну получил примерно одинаковый результат.
          UPD2: http://codeforces.com/contest/142/submission/1041629 - с векторами 690 ms ~40 метров, на msvc работает в два раза дольше, но по памяти также ~40 метров.
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Результат одинаковый, потому что граф не в векторах хранится. Просто в студии вектор каждый раз расширяется в 1.5 раз, а в gcc в 2 раза. Отсюда и разное потребление памяти.
            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +3 Проголосовать: не нравится
              Это понятно.
              Я вообще хотел привести к тому, что его представление графа в данном случае не единственное верное и именно оно приводит к оверхеду, а не то, что в gcc и msvc по разному выделяется память для векторов.
              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится -8 Проголосовать: не нравится
                в этом то и суть, что ограничения должны быть лояльны, и задача проходить при обоих подходах к хранению графа. будь это задача на тупо дейкстру, вы бы также дико меня минусовали? 
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится +6 Проголосовать: не нравится
                  Суть в том, что надо разумно подходить к выбору реализации. Невозможно предусмотреть все возможные решения. К тому же в этой задаче, которую можно решить вообще за O(1), либо как Fefer_Ivan.
                  И в случае с Динницей в этой задаче, тут не просто разность в представлении, а еще имеет место быть избыточная информация.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится +2 Проголосовать: не нравится
                Кроме того асимптотика у обоих алгоритмов совпадает.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится +3 Проголосовать: не нравится
                  Совпадает, и потребление памяти совпадает с точностью до константы. Но не всегда следует закрывать глаза на константу.

                  P.S. твои комменты я не минусую, если что.
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится +41 Проголосовать: не нравится
                  Не раз встречал задачи на Фурье, где проходило либо шаманство с ручными битсетами, либо какие-то ассемблерные ставки в решении за квадрат. Так что, автору надо было уменьшать ограничения чтобы любое решение за квадрат прошло?

                  То что решение идейно верное еще не значит, что его стоит начинать писать. Если вы не умеете на глаз оценивать, сколько памяти занимает ваше решение и насколько оно эффективное при решении данной задачи, то уделяйте больше времени тестированию. Запустите на вкладке "Запуск", посчитайте МЛ на калькуляторе с учетом всех оверхедов. Нужно уметь не только скопипастить готовый код потока, а еще и правильно его применить. Тем более, что реализация неэффективная по памяти и времени (константа плохая). А то что оно запихивается после некоторых усилий - ну хорошо, можно было либо писать такое решение, которое потом скорее всего упадет, либо подумать чуть больше и сдать что-то нормальное.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Если не нравится КФ, вас в принципе тут никто не держит. А фэйлы у всех бывают, нужно уметь их принимать.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -50 Проголосовать: не нравится

        +1

        авторы пофейлились с ограничениями и не признают этого.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Под тупым переборным решением ты имеешь в видуперебрать все тройки чисел, что А*B*C = n?

    Так вот. Количество делителей числа примерно кубический корень, а значит, если перебрать А и В, а С - вычислить, то получится решение за квадрат кубического корня из 10^9, то есть за O(10^6).

    Условия понятные, но с кучей воды от которых хочется убить автора. Начиная с С, я читал условия со второго, а то и с третьего абзаца.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Когда я перебирал A, то забывал проверить, является ли это число делителем N. В результате чего получился код, который тупо перебирал число A до корня третей степени, а число B до корня второй степени. Асимптотика, прости Господи, O(N5/6). Код отработал за 880мс.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +56 Проголосовать: не нравится
        Возведи 10^9 в степень 5/6. Получается 3*10^7. О БОЖЕ КАК МНОГО КАК ЭТО ВООБЩЕ ПРОШЛО.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится -10 Проголосовать: не нравится
          Учитывая, что это операции взятия по модулю и умножения на long long, это реально немало. Неспроста на звероинвокерах CF это решение работало около секунды.
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
             мне кажется, что это ааторское решение. Для задачи А вполне нормально написать несоько вложенных циклов. вон в раунде 100 надо было 2*PI разделить на x  исравнить с n. еще тупее чем циклы.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Кстати, если в таком решении оптимально поставить границы циклов, то оно делает не более полутора миллионов итераций и сдаётся за 60 миллисекунд.
»
12 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится
По моему, то что вы не запустили ваше решение на очевидно макс. тесте во вкладке запуск - исключительно ваша проблема. А обвинять авторов в любом своем фейле как минимум не продуктивно. 
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -33 Проголосовать: не нравится
    Ты все задачи запускаешь во вкладке запуск? У меня и сомнений небыло что такое решение пройдет, при том что у меня еще достаточно оптимальный поток я вообще не сомневался в ТЛ/ML. Но авторы хреново ограничения поставили, кто же знал.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      Нет. Только те в которых много памяти времени. Например 50002 памяти обязательно. 1000^2 менее очевидно. Но тут 8*1000^2 да еще и чего-то нетривиального. 
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -17 Проголосовать: не нравится
        на макстесте на моем компе сработало за 1.3 секунды, вы бы не сочли этого достаточным? 
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Я конечно извиняюсь, но можно подумать, что ваш код работает медленно из-за неправильных ограничений
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится -6 Проголосовать: не нравится
        он быстро работает, граф в память не влазит на GNU C++
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          Ну ок, ваше решение съедает много памяти (я невнимательно прочитал). Сути дела это не меняет
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится -13 Проголосовать: не нравится

            Смотри. Дана задача найти кратчайший путь в графе с ребрами положительного веса n <= 1000, m <= n^2. Ты пишешь дейкстру (без всяких исхищрений, а так, как обычно её пишешь) и вдруг получаешь MLE на этапе системных тестов, ты скажешь это нормально?

            Если такое случается, то либо алгоритм крайне не оптимален, либо автор неправильно выставил ограничения.

            Я уже сотню раз объяснил почему тут второе. все. достали уже. хватит.

»
12 лет назад, # |
  Проголосовать: нравится +60 Проголосовать: не нравится
Хм. Мне одному кажется, что если вы забиваете гвозди микроскопом, жаловаться, что микроскопом тяжело размахиваться - по меньшей мере странно? Я думаю, что автор не должен был задумываться о решениях потоком в такой задаче, потому что его придумает 10%, а пойдёт писать - 1%.
Поздравляю вас, вы смогли найти в этой задаче, как в ней можно использовать поток. Вы его даже умудрились запихать. Казалось бы, претензий к автору быть не должно никаких? Всё в задаче намекает на то, что она не на поток - её позиция в контесте, то, как её сдают, общая (даже не знаю) боянистость и очевидность идеи задачи. Всё-таки соревнования по программированию - они и на здравый смысл тоже.
А то, что под MSVC зашло, а под g++ - нет, это претензии к производителям микроскопов - такое бывает часто, разные компиляторы компилируют по-разному.
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -34 Проголосовать: не нравится

    1) прочитал задачу

    2) понял, что знаю к ней решение

    3) решение подходит под ограничения

    4) пишу и сдаю

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

    И 500 из 1000 таких участников получили бы АЦ, другая половина ML/TL

    Из этого я заключаю что ограничения гавно.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

      Какое же "подходит под ограничения", если 245 мб на одном компиляторе и ML на другом? Это значит вы оценивать затраты памяти не умеете, либо код пишете неоптимальный.

      И повторюсь - такой алгоритм работает не всегда верно. Сегодняшний контест тому доказательство. Здравый смысл рулит. Иногда стоит пять минут подумать и за пять минут написать нормальное решение, чем придумать за первую минуту какую-нибудь гоморихню и писать её два часа.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +18 Проголосовать: не нравится
        А при чем здесь гомори-ху? Легко и недолго пишется же.

        По теме: автор считает контест кривым потому что его решение не прошло. Толсто, очень толсто с его стороны :)
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        смотри в графе 1000 * 1000 + 2 вершин, из каждой вершины 8 рёбер, раз это поток рёбра удваиваются. раз я строю 8 рёбер только из черных клеток шахматной доски количество рёбер делится пополам. каждое ребро весит 12 байт имеем 12 * 2 / 2 * 1000 * 1000 * 8 ~ 96 mb под граф +  перерасход из-за векторов + доп массивы + стек, казалось бы всё влазит, да нет.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +16 Проголосовать: не нравится
          Однако мы имеем почему-то ML и дохрена памяти. Хм, в чём же проблема... Наверное, остаётся только второй вариант, который я описал.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится
          Только еще есть 2 миллиона ребер от истока и к стоку. Это уже 10 миллионов ребер. А главное, почти все вершины будут иметь степень 9, а это значит что почти все векторы будут содержать по 16 элементов. И плюс еще 4 вектора по миллиону элементов и очередь на миллион элементов. Это еще повезло, что оно на студии влезло.
  • »
    »
    12 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    "Я думаю, что автор не должен был задумываться о решениях потоком в такой задаче, потому что его придумает 10%, а пойдёт писать - 1%."

    А я думаю, что если автор тырит задачу из другого источника, он должен понимать, что знакомые с этим бояном будут решать его именно так, как предполагалось в первоисточнике. Первоисточник это задача с acm.sgu.ru, который порядочные acmщики прорешивали в стародавние времена. Задачка была на укладку доминошек по полю, некоторые клетки выжжены.

    upd: возможно, я путаю задачу. но то что это боян - факт.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +20 Проголосовать: не нравится
      Да так рассуждать - все задачи баяны выходят, причём решающиеся исключительно потоками...
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      "если автор тырит задачу из другого источника, он должен понимать, что знакомые с этим бояном будут решать его именно так, как предполагалось в первоисточнике"

      То есть если в первоисточнике решено вообще неправильно, то никто не имеет права дать задачу с тем же или почти тем же условием, но правильными тестами ??? ??? ???

      А я вот люблю давать именно такие подлянки! (Участники харьковской Зимней школы--2010 и NetOI подтвердят...) И что, тут я чем-то категорически неправ?
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +14 Проголосовать: не нравится
        Извините, кто-нибудь может мне дать ссылку на источник, с которого я ее "стырил"? Это, конечно, старый фольклор со школьных мат. олимпиад, но там всегда дается в качестве решения только общий случай, а задача была как раз разобраться с частными. Где-то на солверах/контестах есть/была такая задача?
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится
          Да не парьтесь вы. Если и есть какие претензии к вашему контесту, то они явно не в лимите к B заключаются :-)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +10 Проголосовать: не нравится
            Да я не парюсь, всегда есть те, кому что-то не нравится. А уж париться о попросту неадекватных людях - вообще грех.

            Я просто не люблю пустой болтовни. Кругом орут, что чуть ли не все задачи откуда-то стырены. Но никто не дал ни одной ссылки, только упомянули IPSC'10, где была задача на ту же теорию. Но здесь я как раз спокоен - повально ее не сдавали, так что теорию знало не много народу, и как раз хорошо что узнают.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          минутку... это Вы случайно ответили не_туда или это написано таки мне???

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

          А насчёт того, является ли именно эта задача именно Вашей или откуда-то взятой -- я ничего не_знаю и тем более ничего не_говорил. Прошу прощения, если мой текст действительно можно так понять.
»
12 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится
По-моему вполне нормально:

Либо подумали и написали нормально,
Либо не подумали и попихали.
»
12 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится
Я Вас совершенно не понимаю.
Конечно, на всяких школьных олимпиадах и тру АСМ соревнованиях пытаются сделать так, чтобы только решения с требуемой асимптотикой заходили, но очень много соревнований, где надо впихнуть, то есть написать грамотный код с точки зрения констант. Это такая же важная составляющая в спортивном программировании, как и придумывание решений. Встает вопрос, конечно, о том, что на Java практически невозможно впихнуть поток, но те, кто пишут на этом языке,сами понимают на что шли.
На самом деле, на мой взгляд, автор все сделал нормально - не стал "заставлять" всех придумывать свою идею в этой несложной задаче, а дал возможность посдавать альтернативные "технические" решения.
»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

Вы обвиняете автора контеста в том что заданные ограничения(в которые Вы не уложились) заставили Вас подумать не о том решении. Отлично! А 245мб на MSVC - это скорее просто везение для данного компилятора. Половина решений получат АС - да, половина людей с мл'ным решением удачно напишут контест, значит они просто лакеры, можете порадоваться за них.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    еще раз говорю, по расчетам памяти нужно 96 мб. это какая-то дикая фигня с компилятором GNU  (видимо на стек больше расходуется).
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится
      По расчетам или на практике? Вы сами признались что неверно оценили затраты памяти. Ваша программа тратит очень много памяти, ни g++, ни автор в этом не виноваты, это целиком Ваша проблема. А если программа тратит много памяти, то очевидно что либо Вы отправляете ее на свой страх и риск, либо придумываете решение получше.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а с компилятором VS тоже какая-то фигня, что вместо "теоретических" 96мб тратится 245мб?
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -28 Проголосовать: не нравится
      Да, только мнения вас двоих мне еще не хватало по этому вопросу. Что с вами (и вам со мной) спорить? Отвалите.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится
        забавная у вас позиция: "компиляторы gnu и VS - кривые, ограничения - кривые, задача - кривая, автор - накосячил, все вокруг - неправы, но вот я - красавчеГ"...
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится -24 Проголосовать: не нравится
          Иди убейся. Я так не говорил, я высказал свое мнение много раз. Перечитай мои сообщения. Я говорю о неправильных ограничениях.
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            *сходил убился*
            чего не говорил то? О кривости компиляторов говорил? Говорил. О кривости ограничений говорил? Говорил, прямо в этом сообщении. Кривая задача - дык название топика такое. Автор накосячил, т.к. подобрал кривые ограничения. Ну может насчет ВСЕ(нужно было добавить почти, ибо некоторые может быть с тобой согласны) я погорячился. Выше(или ниже) было что-то вроде если кто-то думает иначе - его право. Т.е. мнение отличное от твоего - не правильное. А, ну и еще мнение нас 2х тебя тоже не интересует(видимо оно априори не правильное). Так чего не говорил то, чего не так?
            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится -7 Проголосовать: не нравится

              Я не говорил "Я красавчег" в чем кривизна, косяки, и неправильность ограничений тебе убогому снова рассказать? ты только с 115-го раза понимаешь? Не согласен со мной, я понял уже. Здесь много не согласных, и да мне насрать что вы так думаете. У меня другие взгляды на задачи. Мне многое уже сказали здесь, что-то я принял, что-то нет. Но это не твое дело блеать.

              Вот каждый хочет ляпнуть что-то. Уже много сказали, хватит переливать из пустого в порожнее, о всем уже упомянули. Прежде чем снова сюда писать прорешай прежде пару тысяч задач, как те, к чему мнению в этой теме я прислушался. А твое следующее сообщение и читать не стану.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится +22 Проголосовать: не нравится
                еще раз подтверждаешь, что ты неадекватен :))

                ладно еще непоследовательность в высказываниях, но вот это: "Здесь много не согласных, и да мне насрать что вы так думаете." А на кой хрен, красавчег, было создавать этот топик?

                ах да, ты забыл добавить: "фиолетовые повылазили"
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится
        Измеряем правильность мнения рейтингом, да? А чего ты стоишь по сравнению с такими как Egor, kuniavski, KADR, yeputons и др. которые здесь отписались?
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Чем так ругаться, можно было бы просто сделать для себя некоторые выводы: например, не искать трудных путей там, где есть простые

Да и откуда вообще авторы задачи могли знать, что кто-то поток в неё попытается пихать?
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Это стандартная задача. вот что бы вы вгоняли, если бы было задано поле с выжжеными/невыжжеными клетками? я бы добавил пару строк кода в свое решение. Если есть более крутой алгоритм, предоставьте его пожалуйста, буду знать. Я другого метода решения не знаю.
»
12 лет назад, # |
Rev. 3   Проголосовать: нравится -38 Проголосовать: не нравится

Да хоть -100 сделайте к каждому коментарию - мне насрать.

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

Если вы(большинство из вас) как-то по другому смотрят на этот вопрос - ваше право.

Если вы довольны таким качеством задач, таким оно и останется.

Я умываю руки, больше в этой теме не пишу.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Я ставлю минус каждому комментарию с которым не согласен. Также я не согласен, что задача B плохая. Нормальная простая задача.
    Давай рассмотрим такую ситуацию. Тебе дали задачу умножить А на B. И ты не перемножил их, а B раз прибавил к ответу А, причем не в long long, а в написанной тобой на vector<int> длинной арифметике. И у тебя не прошло. Задача плохая?
»
12 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится
Я вот одного не понимаю - Вы не проанализировали свой алгоритм, а виноваты авторы. Как так получилось?
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я проанализировал, ограничения позволяли мое решение, как я прикинул.

    И прикинул я правильно, об этом говорит AC на другом компиляторе.

    Авторы виноваты в кривых ограничениях. Если у них такое офигенное решение, почему вершин так мало? Зачем так много памяти? Исходя из того что есть быстрое ограничения "нормальные", в том плане что хватает. Но так "от балды "ограничения не делают.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Память - стандартная. Я не уверен, что на CF есть возможность ее поменять
      "Я прикинул" - при наличии опции запуска не вариант
      Мне кажется, что проблему Вы ищите не там. Да, раунд не из лучших, но именно ограничения по этой задаче не являются проблемой этого раунда. Очевидно, что авторы хотели прохода решения за 8n2, соответственно и подобраны ограничения. Все-таки думать прежде чем писать - полезное занятие. Например - это задача B, вы реально думаете, что дадут в качестве B паросочетание с миллионом вершин?
      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Ну здесь я может промахнулся, но вообще какой только лажи тут небыло в качестве B. И в качестве А тоже.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Вот как меня раздражает, что люди минусуют не зная толком ничего. Вот вам в пример контест, где была эпическая задача A, которую на контесте сдавали вдвое хуже чем B. Круто да?
»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Я для себя считаю, что максимум вершин в графе, когда поток пройдет в ТЛ, это 10000 если двудольный граф и ну 500 если произвольный. А у вас какие подобные константы?
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    там от количества рёбер зависит на самом деле

    если их порядка O(n), то поток на 105 вершин просто летает
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

    Ты для себя как хочешь считай, я проталкивал поток в Петрозаводске на 10^4 вершин и 10^5 ребер. Я тогда еще не умел динниц писать. И про хопкрофта-карпа не слышал до сего дня.

    upd: В авторском решении был динниц

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится
    Кроме того здесь не поток, а паросочетание потоком.
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится
      Всегда удивлялся людям, которые паросочетание пишут потоком. Ладно еще, если не видели что там паросочетание и решали сразу в терминах потока. Но зачем это делать, если уже знаете что в задаче паросочетание?

      Только что ради интереса сдал паросочетанием. На написание самого алгоритма с нуля ушло минуты полторы, еще минуты 2 на объявление массивов, ввод и построение графа. Решение прошло за 0.84 и с использованием 64 мегабайт памяти на gcc. Причем это никакой не Хопрофт-Карп, а обычное паросочетание с дфсом, только прямо написанное.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Здесь граф специального вида, видимо поэтому ваш алгоритм проходит.

        В общем случае, на произвольном графе паросочетание потоком быстрее работает, чем не потоком. Считать ли потоком  Хопрофт-Карп, я не знаю, давайте забудем про него пока.

        Да поправит меня AlexSkidanov, он всегда писал паросочетание потоком. Я вначале писал потоком, потом узнав приведенный факт стал писать более крутым "Скидановским" потоком. И только потом в научных целях изучил и потестил на разных задачах этот самый метод дфсом и чередующихся цепочек. Поток победил.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +7 Проголосовать: не нравится
          Видимо, плохо вы писали паросочетание дфсом :)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            Видимо, плохо вы пишете паросочетание потоком :)
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

            По сути, паросочетание дфсом, это и есть проталкивание потока поиском дополняющей цепи(пути), так что спор ниочем. Как мы видим, алгоритм Хопрофта-Карпа вообще сложно отнести к одной из двух категорий. Но думаю придумывался он в терминах потока. Ну и мне проще так размышлять. Ограничения делаются так, чтобы проходили неоптимальные решения, и решения на жаве, поэтому я всегда пишу поток и не парюсь. Другое дело, что бывают плохие ограничения.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Вот какого хрена минусов понаставили, вы затестируйте сначала, потом минусуйте. KADR, подтверди скорость.
      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
        А Вы специально подбирали значения в массивах di и dj? Если поменять порядок, то TLE на 10-ом тесте (#)
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Неа, ввел как это делаю обычно.
»
12 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
А я вообще не понимаю о чём спор. Ограничения -- это такая же часть задачи, как, например, собственно условие. Автор хочет, чтобы решение юзало не более 256mb -- его право.
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -33 Проголосовать: не нравится

    Это не так. Ограничения должны выставляться так, чтобы асимптотически верные решения, с константой не сильно отличающейся от авторского проходили. Обычно ставят ТЛ удвоенный от авторского. Не правильно ставить ТЛ 1 сек, если заоптимизированное авторское решение работает 0.9 сек. Я сейчас говорю не относительно данной задачи, а вообще. Это общепринятая норма, минусани сообщение если ты идиот.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Есть авторские решения за O(1) и за O(E). Думаю, что они работают быстрее, чем секунда и потребляют меньше, чем 128 МБ.

      Кстати, по поводу векторов - если Вы собрались их использовать, будьте готовы к тому, что они потребляют в 1.5-2 раза больше памяти, это существенно. Самому иногда приходится переписывать решения чтобы прошли, я считаю, что это из той же серии, что поднимать ограничения в 10 раз для Scala, Haskell и пр. небыстрых языков.
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +67 Проголосовать: не нравится

        Давайте попросим администрацию сделать галочку в интерфейсе участника "не умею оценивать время работы программы и объём памяти, который она использует".

        Если участник поставил эту галочку, то для него TL и ML увеличиваются, например, в 2 раза.

        Такой бонус новичкам :)

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -74 Проголосовать: не нравится

        Ты тупой? Я же сказал что это утверждение не относится данной задачи. Спроси у Снарка, как ставят ограничения. Вот как раз для векторов и ставят нормальные ограничения на память. Это не про эту задачу я говорю, а вообще.
        Для тупых, снова оговорюсь, что в сообщении выше, и в данном речь не идет о какой-либо конкретной задаче. Речь идет о задачах вообще, за исключением специальных, где суть задачи в какой-то хитрости навроде прочитать инпут два раза.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +32 Проголосовать: не нравится

          Вы какой-то больно агрессивный.


          Я просто основную целью поста не понял.
          Вы хотите сказать, что из-за маленьких ограничений ваше решение не влезло в МЛ. Не смешно самому то?
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

            Я хочу сказать, что ограничения неправильные.

            Либо маленький ML, либо большие n и m, будь они до 700, все бы было нормально. Можно сделать n и m до 10000, тогда тоже адекватные ограничения будут.

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится
              Если n и m до 10000, то может так получиться, что квадратичные решения перестанут заходить, а автору видимо хотелось, чтобы они заходили.

              Вообще мне кажется, что нормальные ограничения это когда:
              1) Те кто пишет асимптотически оптимальное (или предполагаемое авторами) решение - не имеют проблем с тем чтобы запихать
              2) И что нет такого, что люди придумавшие нормальное решение (асимптотически оптимальное или предполагаемое авторами) были в худшем положении, чем те кто по каким-то причинам загнал то, что не должно было зайти в принципе (например по причине слабых тестов).

              Твой же случай не относится ни к 1, ни к 2. В этой задаче вообще не может быть слабых тестов. Поэтому если ты пишешь решение, которое на грани, то можешь запросто его проверить.
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +52 Проголосовать: не нравится
          Путаешься в показаниях. То в чётных комментариях про эту задачу, то в нечётных не про эту. То не будешь больше писать, то опять десять комментариев. Определись уже.

          Одна всего идея была, с которой могли бы согласиться. А именно:

          Автор задачи должен минимизировать матожидание количества посылок, которые на грани TL/ML. Всеми разумными способами. Если таких решений много, это вносит в результаты элемент случайности, не очень явно зависящей от участников. Если же их одно-два — ну, бывает. Всякий раз кто-нибудь да умудрится.

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

          Но ты и этот пункт продолбал глупой руганью и отношением к собеседникам. Ну, кому что.
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится -16 Проголосовать: не нравится

            Спасибо, ты более понятно сформулировал мою мысль.

            Я не хочу писать уже, достало. Но и не писать ответы на эти %№;;"№; комментарии тоже невыносимо, они все извращают и переиначивают, противоречат простым истинам.

            По поводу ругани, ты посмотри сколько дерьма на меня тут вылили, ты бы себя хорошо при этом чувствовал?

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

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится
      Асимптотически верное решение может иметь произвольно большую аддитивную константу, так что формальную дискуссию вам не выиграть.
      А для неформальной в этой теме уже достаточно постов :)
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится -7 Проголосовать: не нравится
      >минусани сообщение если ты идиот.
      Детсад какой-то. Хорошо, я идиот.
»
12 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится
Лампочка застряла во рту. Причина? Безусловно неправильный размер лампочки.
»
12 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
Перемудрил ты, братец. 
Это задача под буквой "B", понятно что поток дать не могут. Если решение не придумывается, то можно было написать тот же поток, чтобы увидеть зависимость на мелких n,m.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится
    Ой, сейчас снова потоки говна пойдут. Знаешь, сколько человек ему уже эту мысль твердит? :-)
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Нет, в этом комментарии течёт тоненький ручеёк тёплого молока. Я сам в таких ситуациях много раз оказывался.