Доброго времени суток, дорогой CF! Меня зовут Егор и я представляю Samara SAU 1 (Petruchcho, Sinner, Slamur). По старой доброй традиции каждый год участники из нашего универа пишут посты на CF про поездки на четвертьфиналы в Саратов. В этом году я решил совместить этот увлекательный рассказ с рассказом о нашем выступлении в Новосибирске на Всесибирской олимпиаде.
Саратов в этом году не сказать, что смог нас чем-то удивить/порадовать. В прошлом году наша команда в упорной борьбе с Саратовскими командами вырвала 4 место. Как и Teddy Bears в позапрошлом году. Да, да, как и в этом году (Монитор). При этом я бы не стал говорить, что мы были недовольны результатом или организацией. Но вы дочитали до интересного: на контесте у нас возникли java проблемы. А именно мы написали решение с авторской асимптотикой, ухудшив константу примерно в два раза. Получили заслуженный (???) TL, а точнее -16 с TL. Ничего, собственно, необычного для нас не произошло, но, поговорив после контеста с I_love_natalia, мы почувствовали, что не все так очевидно. На разборе MikeMirzayanov прогнал наше решение и сказал, что оно отработало за 8.8с вместо 6. Стоит сказать, что хотя эта задача фактически ничего для нас не решала, но неприятное ощущение осталось.
Через неделю мы полетели в Новосибирск. Если кто-то не знает, Всесибирская олимпиада состоит из двух пятичасовых контестов: по АСМ правилам и некое подобие марафонной задачи. Для любителей поностальгировать /blog/entry/5807 (не, у нас в этом плане все отлично).
В первый день мы вновь столкнулись с java проблемами, причем гораздо более серьезными. Вы не поверите, но на java решения с асимптотикой порядка O(6*10^8) по одной из задач или даже O(8*10^7) по другой не очень хорошо упихиваются. При условии, что это авторские решения! Мы за счет огромного опыта и высокого рейтинга все-таки справились с этим и вылетелиушли с контеста с 5 сданными задачами. А хотите узнать, как хорошо прошел второй день, когда надо было заоптимизировать перебор по игре "Балда"? К сожалению, нам для тестирования был выдан слишком мощный (???) комп, на котором наше решение укладывалось в отведенные ограничения на макстестах. Это ввело нас в некоторое заблуждение относительно возможностей нашей программы, что само собой привело к проблемам в конце соревнования, а так же к веселому подгону констант MAGIC, MAGIC2, MAGIC3... К слову, мы проиграли лидерам примерно в 10 раз, да.
Собственно, подвожу к главному. lperovskaya, скинь, пожалуйста, фотографии Sinner в майке Саратовского ГУ.
А если серьезно, в последнее время проблем с java все больше. Отписывайтесь в комментах, если у вас есть подобные истории или вы хотите обвинить нашу команду в кривожнеспособности писать хороший код. Спасибо за внимание!
Замечу, что на CF, где у вас 2.5 секунды, у нас решение работает за 3.3, так что это не совсем корректное сравнение по ТЛ.
Ну тогда остается только попросить MikeMirzayanov прогнать наше, ваше и авторское решения на том компьютере, на котором тестились решения во время четвертьфинала. Со скринкастом.
Java поддерживается почти на всех крупных контестах, ставить TL не менее 2x от решения на Java — всеобщая практика.
О не "чф-пф-ф": я знаю людей, которые готовили местный отбор на ВКОШП, и по всем задачам (кроме, видимо, A+B) у них были решения на Java. И это несмотря на то, что большая часть участников вообще пишет на паскале.
эм... на TC и CF лимиты одинаковые? где они разные? Я составлял список, но нашёл не много https://en.wikipedia.org/wiki/Java_performance#In_programming_contests
Небольшой оффтопик: кто-нибудь знает, что это такое?
Не знаю, как другие, а я предпочту использовать это приспособление в качестве тренажера для пальцев (типа эспандера наоборот). Надеваешь на пальцы и раздвигаешь.
Хотя я слышал также предложение о штуке, которую надеваешь на руку и вставляешь туда ручки.
По поводу эспандера — еще можно надевать на пальцы почти до конца и кодить:) Но к этому нужно некоторое время привыкать.
Мыши плакали и кололись
Могу сказать то же самое про C++ с его многочисленными возможностями выстрелить себе в ногу.
Все языки по-своему ущербны :(.
Честно говоря, всегда не очень понимал, как люди стреляют себе в ногу на С++, решая олимпиадные задачи. В промышленном программировании -- да, верю, 314159 типов умных указателей и неочевидных вещей everywhere, но на контестах всё это ж [почти] не используется, разве нет? На олимпиадах ну за пределы массива можно выйти и не заметить, а что ещё?
И ты ни разу не выходил за пределы массива?
Нет, конечно, я ж синий.
Из того, что сразу вспомнилось с контестов:
И последнее, которое ловится warning-ами, но все равно напарывались на это:
Добро пожаловать в мир С++!
Зато благодаря восклицаниям "да как оно вообще скомплировалось?!" тренировки становятся не такими скучными:)
Но все эти примеры на int <--> bool conversion, разве это не ловится ворнингами?
Я помню, как случайно передали вектор в функцию по значению, а не по ссылке. А этот вектор на случайных тестах был маленького размера. Первый тест, который это валил, кажется, имел номер 51. Никто не догадался посмотреть заголовок функции, поэтому весело провели время за оптимизацией довольно объемного кода.
Java: String/StringBuilder Integer/int (сравнение == по ссылке)
Не ну если вы не отличаете ссылку на объект от примитивного типа ... Вообще тут ранее была вообще речь об ошибках, которые позволяет вам допустить сам язык. В Java единственная "проблема" если только с generics. Никаких UB, арифметики с указателями, не очевидных приведений типов.
Так по сути про generics и речь. Авторы языка сделали для сравнения значений и сравнений ссылок -- РАЗНЫХ по сути операций один символ -- что позволяет допустить ошибку.
Кое-где кто-то юзал String где надо StringBuilder, такие случаи тоже были
Я про generics имеют ввиду намного более коварные случаи (но не будем сейчас об этом). А вам не кажется, что ссылка в нативе это фактически адрес в памяти, что есть число? Как его ещё сравнивать c другой ссылкой? А вот если хотите сравнивать объекты по этим ссылкам — equals для вас и придумывали. Иногда можно даже объекты сравнивать на == вместо вызова equals, если вы полностью управляете генерацией объектов. Это даёт хороший буст. Ну и меньше работайте с boxed типами, конвертируйте их при первой возможности в примитивы и будет вам счастье, если не хотите учить правила приведения типов в Java.
StringBuilder ... вы ещё вспомните про Scanner. Речь о том — насколько легко не заметить ошибку в коде, а не сколько есть не оптимизированных вещей в готовой библиотеке. Последние тупо заучиваются и в случае проблем с TL на Java идёт проверка — а не использую ли я что-то медленное.
Я понимаю еще, когда красные начинают меня учить, но вы? :)))))
Конечно, кажется. Но еще больше мне кажется, что Java как раз создана для того, чтобы абстрагироваться от таких деталей. Вы про такую вещь, как например, меченые указатели не слышали? Упакованные указатели? Мало ли кто какую JVM юзает? Сравнение ссылок и значений по сути разные операции. В Питоне операция сравнения ссылок называется is, и нет никакой путаницы.
Почему ж тогда нельзя и в С++ "тупо заучить" и глупых ошибок не делать?
В Jave косяков нет! Она дана Б-гом через Моисея!
приведение типа long => double теряет точность и как бы некомильфо(впрочем, в С/С++ тоже так). у double мантисса короче.
Нормальные IDE это подсвечивают желтым.
На последнем opencup раунде ( GP of Siberia) (Я так понимаю, он совпадает с финалом всесибирской олимпиады) задача 8(Colonization) на jave за O(N^2*logN) у меня не проходила (TL),а переписанная на С++ проходила.
Java: http://pastie.org/private/kfkqtsht6ucyhpqofihiag
C++: http://pastie.org/private/c226fxlretljj56q7tsxg
И случай, когда переписать на С++ помогает, у меня не первый.
На Кыргызстанском четвертьфинале мы по крайней мере пытаемся делать, чтобы авторские решения на Jave проходили примерно за половину TL. А есть ли такая практика на других олимпиадах?
Два совета:
1) Пишите аккуратнее :)
Достаточно поправить компаратор на однострочный.
2) Пишите на Яндекс.Контесте
Вот такой код уже заходит на всех компиляторах на Яндекс.Контесте с запасом в ~1 секунду: http://pastie.org/private/hggubfrboyesui0g1inzsw
И не заходит ни на каком на ejudge.
Спасибо! Мне почему-то нравится писать компаратор, который возвращает 0 для равных (согласно equals) объектов. Оказывается, это только рекомендуется, но не требуется в данном случае.
На топкодере, вроде бы, есть правило, что авторское решение на Java должно работать не более 1 секунды. Возможно, именно наличие этого правила объясняет то, что у Petr на TC рейтинг выше, чем у tourist, а на Codeforces, где такого правила нет, наоборот.
а что, на CF есть такое правило? Или у вас есть другая гипотеза про разницу в местах Petr/tourist?
Такое правило есть на CF, да
Вообще-то, у нас тоже есть решения на Java для всех задач, в которых TL критичен. И вроде TL не выставляется меньше, чем удвоенное время работы решения на Java. Однако надо понимать, как пишутся эти java-решения.
У нас нет ни одного человека, который бы реально писал олимпиадные задачи на Java: все пишут на C++. Поэтому авторские решения спокойно, попивая чаёк, сначала пишутся на C++. Потом этот код копипастится в какое-нибудь java-решение задачи прошлых лет и портируется ручками на java. Иногда бывает такое, что человек сразу пишет второе решение на java, однако таких людей недостаточно на все задачи. Естественно, в условиях "попивая чаёк" решение оказывается существенно эффективнее среднего решения участника...
Typical Java
Проблемы с Java — это проблемы самих участников. Каждый себе выбирает инструмент исходя из своих пожеланий — если предпочитаете удобство (удобная среда разработки, приятный длинный синтаксис) и надежность (сложно "выстрелить себе в ногу"), то пишите на Java, а если предпочитаете скорость, пишите на C++.
А умные люди в такой ситуации комбинируют оба подхода — например, спросите yarrr — он раньше писал почти все задачи на Java, но критичные по времени решения писал на C++.
А жаловаться на злых авторов — это отмазка для бедных.
я попрошу, в посте нет ни слова жалобы на авторов. Цель поста — внезапно — указать на существование таких проблем и попросить организаторов больших олимпиад относиться к решениям на официальном языке чемпионата мира чуть ответственнее.
С того момента, как полная поддержка некоторого языка заявлена (или предполагается "по умолчанию") на соревновании — это и проблема авторов / организаторов.
В давнем комментарии andrewzta приводится ссылка на правила подготовки командных школьных олимпиад. Кажется, что правила подготовки к студенческим не должны кардинально отличаться. Особое внимание хочется обратить на раздел "Выбор ограничений и написание решений" и слово "естественно" в первом пункте.
Понятно, что среди авторов может не оказаться человека, пишущего (олимпиадные задачи) на Java. Но представляется, что можно организовать прорешивание задач; да и пробный тур может содержать информативные (как для участников, так и для жюри) задачи (при наличии отборочного тура, вероятно, можно даже провести некоторый анализ решений).
Кажется также, что версия компилятора, используемая в тестирующей системе, нередко является маркёром потенциальных проблем. Если она далеко не последняя — то, скорее всего, Java-решения подготовлены способом, подобным описанному чуть выше stgatilov.
Конечно, есть ещё один путь — например, в школьных олимпиадах есть "дополнительная группа языков", для которой не гарантируется полной поддержки. Но, кажется, по этому пути по отношению к одному из языков официальных ACM-соревнований идти всё-таки странно (даже на турнире ICL с относительно недавних пор поддерживается Java, хотя и 1.6...)
Умные люди комбинируют оба подхода, но при этом задачи, в которых приходится заниматься пиханием, вызывают у них поток нецензурных слов в адрес авторов.
Другой вопрос: а что мешает людям, занимающимся подготовкой задач, выучить Java на уровне естественного для этого языка написания кода?
а почему только Java? Почему не хаскель, или там, D?
Ой, пожалуйста, не надо так писать, не путайте асимптотику с количеством операций.
My bad, Petruchcho не виноват)
У меня подобных проблем было оргомное количество (с тех пор как перешёл на Java). В основном причина простая: авторы пишут решение на C++, а потом поднимают ограничения, чтобы их решение влезало с запасом 2-3x; зачастую этого недостаточно даже для менее оптимально написанных решений на C++, не говоря уж о Java.
Проблема решается очень просто — надо не ставить ограничения и ТЛ впритык по авторскому решению, а пытаться отделить правильное решение от неправильных. Обычно зазор 100x и больше, и отделяется легко (ставим ТЛ 10x от авторского решения, тогда неоптимально написанные правильные решения заходят, а оптимально написанные неправильные — не заходят).
Если же зазор между правильным и неправильным решениями меньше 4x — то стоит задуматься, давать ли вообще такую задачу. Лажу с адскими оптимизациями почти наверняка загонят, а вот у многих участников с нормальным решением будет адское упихивание в ТЛ; такая задача только добавит рандома в результаты и испортит многим участникам впечатление от контеста.