Во время решения задачи С со 119 раунда я столкнулся с невозможностью запихать в ТЛ решение на Java, де-факто аналогичное авторскому: бинпоиск + БФС с СНМом. В чем причина столь маленького ТЛа? Команда Codeforces не переписала авторское решение на Java? Или я не прав? В любом случае, я считаю, что это ненормально, когда на жабе заходит решение только у 14 человек (включая дорешивание).
P.S. Решение через построение "диаграммы Вороного" и последующий запуск алгоритма Крускала у меня зашло за 840мс.
UPD. Под выражением "построение "диаграммы Вороного"" я подразумевал разбиение вершин на множества в соответствии с тем, какой из волонтеров (или точка назначения) находится ближе всех, делал я это БФСом. Можно сказать, что я неявно построил граф с этими множествами в качестве вершин, и объединял их до тех пор, пока s и t не окажутся в одном множестве (как в алгоритме Крускала).
У меня вопрос похожий:
есть решение на C++, заходит за ~700 мс при TL = 2 секунды. Аналогичное решение на Java работает 1.8 секунды. Стоит ли при подобных ситуациях устанавливать различный TL для решений на разных языках?
Или просто увеличить TL для всех, например, 3 секунды? (в этом случае на C++ за 2.78 проходит асимптотически неверное решение с парой оптимайзов).
Кстати, дополнение к моему и Вашему вопросу: почему на ту задачу, про которую я написал, проходили квадратичные решения с отсечением?
Ну, некоторые авторы контестов могут просто не знать яву, чтобы на ней прорешивать. Например, когда я готовил контесты — на яве никто не прорешивал. Вообще же у меня всегда была жесткая позиция по данному вопросу: если есть решение, с большим гаком (3-5 раз) вписывающееся в ТЛ на чем-нибудь типа C/C++, то увеличивать его отдельно для пишущих на чем-то другом — это неправильно. Вы бы еще пожаловались, что на Python'е в ТЛ не влазите =) В свою очередь, в качестве доказательства справедливости бытия, могу привести в пример, что на АСМ-контестах авторы обычно не заботятся о пишущих на Сях, давая задачи на длинную арифметику (иногда довольно адскую), что тоже не есть справедливо. Как итог — у каждого языка есть свои преимущества и недостатки, если они вас очень добивают — пишите на другом языке. Ведь очевидно, что писать на Яве задачи, в которых есть вероятность схлопотать ТЛ — не самое разумное решение.
В свою очередь, в качестве доказательства справедливости бытия, могу привести в пример, что на АСМ-контестах авторы обычно не заботятся о пишущих на Сях, давая задачи на длинную арифметику
По-моему, это ложное утверждение. Обычно как раз таки ограничения подбираются, чтобы все влезало в по крайней мере в 64 бита. Гораздо реже можно встретить простейшую длинку, типа посчитать длинное по модулю короткого, или сложить два длинных. И чрезвычайно редко бывают случаи когда дается жесткая длинка (я таких даже не припомню).
Достаточно открыть OpenCup'ы прошлых лет (про этот год сказать не могу, ибо не следил), чтобы понять, что мое утверждение истинно. Я даже специально учил Яву на базовом уровне, чтобы не мучиться с длинкой, зачастую в задачах, где она совсем лишняя.
P.S. Хе-хе, не любит народ правды в лицо =) Читайте-читайте!
А еще помню на каком-то опенкапе была задачка решавшаяся примерно в одну строчку на Java:
System.out.println(Math.IsProbablePrime(x));А уж сколько надо было бы на c++ для этого написать -- страшно подумать.
Тест Миллера-Рабина это совсем чуть чуть кода.
О, может я чего-то не понимаю. А расскажите, как писать Миллера-Рабина без длинной арифметики для чисел порядка
10^18.Я так понимаю проблема в том, как умножать два числа порядка 10^18 по модулю 10^18, но это уже кучу раз обсуждалось... Но ссылки я не помню поэтому повторю снова: 1)написать умножение на число, как бинарное возведение в степень заменив все * на +
2)
В тесте Миллера-Рабина переполнение может быть только когда мы считаем что-то вроде (a*b)%c. Для этого можно без проблем использовать алгоритм бинарного умножения.
Насчет некоторых авторов, не знающих яву: подавляющее большинство авторов ее знают :).
Насчет Вашей "жесткой позиции": она имеет право на существование, но если на Java то самое решение, которое у Вас заходит на C++ с большим запасом, ТЛится без столь же жесткой, как и Ваша позиция, неасимптотической оптимизации, Вас, как автора контеста, жабокодеры будут в душе справедливо материть непечатными словами.
Насчет довольно адской длинной арифметики: на Java в таких случаях BigInteger тупо валится по ТЛу, так что обе стороны оказываются в равных условиях. А задач на обычную длинку, где BigInteger заходит, на нормально подготовленных контестах (вроде полуфиналов NEERC'а) практически не бывает.
Насчет задач, где есть вероятность получить ТЛ: на нормально подготовленных контестах вероятность получить ТЛ есть тогда, когда решение или асимптотически неправильное, или написано ну явно через энное место.
Насчет довольно адской длинной арифметики: на Java в таких случаях BigInteger тупо валится по ТЛу, так что обе стороны оказываются в равных условиях.
Под адской я подразумевал реализацию: помнится, встречал задачи, где нужно было реализовывать длинное GCD. Очевидно, у пишущих на Яве в таких случаях явное преимущество по времени.
А задач на обычную длинку, где BigInteger заходит, на нормально подготовленных контестах (вроде полуфиналов NEERC’а) практически не бывает. Насчет задач, где есть вероятность получить ТЛ: на нормально подготовленных контестах вероятность получить ТЛ есть тогда, когда решение или асимптотически неправильное, или написано ну явно через энное место.
Вы все время упоминаете какой-то абстрактный объект "нормально подготовленный контест". Они нечасто встречаются в природе (ну, разве что полуфинал NEERC), в основном же в 95% случаев приходится участвовать в контестах, которые не принадлежат этому классу, и там попадается И техничная длинка, ворующая время у пишущих на Сях, И неадекватные для Яверов таймлимиты. Именно к этому и относился мой вывод:
Как итог — у каждого языка есть свои преимущества и недостатки, если они вас очень добивают — пишите на другом языке.
Длинное GCD входит в разряд вещей, которые легко пишутся на С++. К сложным я бы отнес только длинное деление.
В сколько строк уложишься? ;)
Умножение на короткое, вычитание, деление пополам пишутся в сумме минут за 10-15. И это скорее оценка сверху.
[Здесь был какой-то бред]
Да и итого все равно гораздо дольше, чем просто BigInteger.gcd() на Яве
Может, просто двоичный gcd? Писать его бинпоиском я не умею.
А что за двоичный gcd? Я всегда думал, что бинпоиск используется в gcd только в процессе нахождения остатка от деления длинного на длинное
gcd(2a,2b) = 2gcd(a,b)
gcd(2a+1,2b) = gcd(2*a+1,b)
gcd(2a,2b+1) = gcd(a,2b+1)
gcd(2a+1,2b+1) = gcd(2a+1,2(b-a)) или gcd(2(a-b),2b+1)
Спасибо! Не знал о существовании такого изящного подхода.
Это в течении нескольких лет давали на пробник РОИ.
Достаточно было и БФС + СНМ, бинпоиск не нужен. 330 мс на c++, вряд ли больше секунды на Java. Вы уверены, что в авторском решении есть бинпоиск?
Да, уверен. А про решение через БФС + СНМ я как раз и помянул, именно оно у меня зашло за 840мс. UPD. Подредактировал основной пост.
Ну вообще codeforces.ru/profile/yaro сдал много решений на JAVA, там все разные вариации бинпоиск + БФС + СНМ. Мне кажется, то, что не всякое решение укладывается по времени, скорее положительный момент: умение писать оптимально столь же прекрасно, как и умение придумывать решения. Мне кажется, можно не винить авторов, а искать, что можно сделать, чтобы никогда не было проблем со сдачей задач на JAVA, вне зависимости от того, злые авторы или добрые.