Осталась одна минута, не забудьте принять участие! :)
http://code.google.com/codejam/
UPD: Результаты: http://code.google.com/codejam/contest/1645485/scoreboard?c=1645485#
Первые 1000 участников проходят в следующий раунд.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 20:26:09 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Как решать С?
Извините, это не ошибка в Java. Это я идиот, выводил ответ в русской локали.
Я использовал метод
printf(), и все отлично зашло. А что, 9.99999999995449E-6 не принимается их чекером?Я слил... Целый час тупил, что надо проходить easy-уровень, где b[i] максимально, а a[i] <= stars, а не a[i] == stars. В итоге сдал эту задачу за 5 минут до конца, чего не хватило.
Ухаха, оказывается, это надо было за O(n) делать.
С такими ограничениями как там, можно было даже O(N^4) запихнуть
Там же вроде 1000 было ограничение на n? n^4 то многовато вроде, даже для 8 минут.
Современные процессоры имеют частоту порядка 2.2-2.8 GHz, т.е. 2.2 * 10^9 тактов в секунду
2.2*8*60*10^9 > 10^12
Любопытно даже стало :) То что 10^12 уложится в 8 минут я очень хочу проверить на практике, так что вечером посмотрю, если так, то надо пересматривать отношения к решению задач gcj :) Но Вы забываете одну маленькую деталь :) тест там не один, так что 2.2*8*60*10^9 << 10^12 * 100
Ах, ну да :) Не такая уж и маленькая. Я был неправ насчет того что N4 уложиться
Я идиот >.< Решил оба теста А, написал верное решение по B — fail из-за вывода "Too bad" вместо "Too Bad"... Угробил кучу времени, осознал только через 10 минут после конца.
Слил. Зафэйлил В.large. На мой взгляд, раунд был полным УГ, и такого плохого первого (именно первого, то есть с катоффом в 1000 человек) раунда в codejam я не видел давно.
Объясняю почему. А и В решали все кому не лень, а вот С была значительно сложнее. К чему это привело? Первые две задачи были обязательными — а C.small решило только 65 человек. Хорошая градация. Мало того, авторы решили поприкалываться и дали за B.large больше чем за C.small, а C.large решило только 22 человека. Для всех остальных А и В надо было сделать безошибочно (ну или зафэйлить не B.large и сделать C.small, что опять же немногочисленно) и то не за очень долго, потому что есть люди не прошедшие с А и В по времени. Вот и получается, что отбор тысячи (кроме 22 человек, но не слишком ли малая часть из 1000?) был не потому, сколько задач ты решил; а по тому, не затупишь ли ты. И при всём при этом B.small был очен слабым: мой фэйл в В он не словил, а у меня был чистый идейный фэйл — если я в какой-то момент не мог взять ни один уровень на 2 звезды, то я брал не тот уровень, что я могу пройти на 1 звезду и с максимально сложной 2й звездой; а просто следующий уровень из отсорченного списка по возрастанию сложности 1го уровня а потом по убыванию сложности 2го. Для N <= 10 тест ловящий это прекрасно можно построить: (0,5),(0,2),(1,4) например. Всё-таки я привык что эпичные идейные фэйлы small ловит. Возможно зря, кажется теперь я на small буду расчитывать гораздо меньше.
Опять же, всё ИМХО, и буду рад выслушать мнения других.
Я вначале написал именно такое решение, но 2 раза получал WA на small. Если оно на некоторых инпутах проходит, а на некоторых — нет, это большой фейл организаторов.
Задачи сами по себе были интересные, а по поводу немного неправильного баланса согласен: в B-large надо было n <= 100000 поставить, и не было бы такой толпы решивших ее.
Квадрат бы все равно прошел — 8 минут же дается.
А я вот не соглашусь с Вами. Я тупил очень много по обеим задачам, даже написал разные решения на B-small и B-large (не умею я решить в 7 утра :)), однако прошел. С не дописал совсем чуть чуть, и если бы не ужасная сонливость, не то что я начал писать на 30 минут позже, то возможно она бы прошла. (по крайней мере я получил ответы которые были в инпуте, но время закончилось). Она была прикольная и можно было писать отдельно решение для small.
Решать 2 обязательно. А что такого? Заметь, что надо было решать быстро и чисто. То, что решение прошло small и не прошло large — ну авторы не обязаны давать все случаи. А то, что у кого — то поймалось решение — авторы не могут написать все неверные решения.
По баллам на С и В, сумма по В и по С вроде бы различная. А вроде бы сдать large без small нельзя, так что, сдав С без В, все равно будешь выше. Так что все нормально.
Конечно, в том что надо обязательно писать две из трёх, проблем нет. Когда третья задача решаема не 22 людьми. Вот и получается: при отборе в 1000, 62е-1221е место получило одинаковое количество очков. На мой взгляд, это не нормально. Как не нормально и то, что не прошли 2 человек с A, B.small и C.small. А ведь B.large решило 1617 человек, а C.small — 65. Впрочем, по количеству минусов я начинаю подозревать, что большинству это нравится.
Про задачи уже конечно взгляд более личный, потому что всё написанное ранее не зависит от моего выступления на этом раунде. На мой взгляд, тесты такого типа должны придумываться без придумывания всех плохих решений. Но такого видимо не было, и остался рандом. И некоторым такой тест попался и они исправили баг, некоторым нет. Одно это, конечно не делает раунд плохим, но учитывая то, что практически В надо было сдавать безошибочно, это было очень неприятно. Впрочем, урок понят, теперь лично я буду гораздо меньше опираться на small.
P.S. Спасибо, что оставили своё мнение. Неприятно, когда у коммента -8, а почему он не согласен со мной объяснил только один. Кажется надо завести себе правило — ставишь минус, объясни почему.
Ну я бы на Вашем месте не обращал внимание на минусы :) В Вашей позиции есть доля истины, и я соглашусь, с тем, что C.small должно было стоить дороже B.large. Однако, стратегия раунда выстраивается из того, что дано. Я и например, опирался на то, что В.large стоит больше, когда выбирал, бросать В или нет, когда первое решение не прошло и пришлось сдавать 2^n :)
На самом деле, 1 раунд может себе позволить быть несбалансированным (разные причины могут быть, впомним hacker cup, qual этого года), будут еще 2 попытки. Вот если будет так во 2 раунде, то это уже будет не приятно.
Позволю себе не согласиться — мне раунд понравился. Но это, наверное, потому, что я нигде не затупил и сдал C.small ;) Но и объективно — баланс задач не был неадекватным. B.large решили не все поголовно, а 1617 участников, две задачи полностью решили всего 1220 человек. Поэтому выбор был — либо относительно быстро сдавать простые задачи (из 1159 человек, сдавших только две задачи, не прошли во второй тур только 220, то есть нижние 20% по времени), либо сдать еще что-нибудь (третья, имхо, была хороша). Вы попробуйте встать и на сторону организаторов — у вас бы получилось так рассчитать сложность задач, чтобы все, кто сдал 2, прошли, а все, кто меньше — нет? Я вот сомневаюсь в своих силах. Здесь же большинство (>80%), кто сдали две — прошли. По-моему, гут! P.S. Единственный существенный косяк, с которым я согласен — это что за C.small давали больше чем за B.large. Хотя тут может найтись своя логика — например, что придумать чуть нетривиальную жадину авторы ценят больше, чем написание тупого перебора.
А Вы решали С small как? Просто я решал так: построил все времена, когда что — то меняется: то есть машина догоняет другую или полностью обгоняет. Для каждого времени строил все маски машин по полосам (0-бит — машина в левой полосе, 1-бит — в правой) и находил момент, когда set масок становился пустым или все ок и possible. Просто отладил семплы через минуту после конца :( а в дорешке не слал, так как на работу убежал, так что интересно, правильная ли идея для small. И еще более интересно, как ее довести до large
Я, решал тупым перебором — запихал все машины в 2 вектора, потом находил пару, которая столкнется не раньше текущего времени, потом для двух вариантов перестройки машин этой пары перестраивал вектора и рекурсивно продолжал в том же духе. Самый тупой bruteforce.
Верно или нет ваше решение — можете потестировать сами, объяснение идеи на large уже появилось во вкладке "Contest analysis"
Сейчас погляжу, спасибо
Я говорил чуть о другом. Задачи, как мне кажется, также были интересными. На мой взгляд разница между сложностью С и В была слишком велика. В итоге почти нельзя было выполнить довольно обычную тактику на codejam (имхо) — сдать больше чем надо, и даже если что-то зафэйлит и не пройдёт, всё равно пройти дальше. Здесь так было нельзя. Вы сдали C.small, например. Но и у Вас не было права на ошибку — если бы у Вас упал B.large — Вы бы не попали в 1000. Не думаю что это было бы честно — даже C.small был намного сложнее B.large. А про поголовное решение задач я имел ввиду только первую 1000, а там её решили поголовно все.
С другой стороны, конечно, в случае фэйла виноват сам, иди писать другой раунд 1 — не отрицаю. Просто обычно первые раунды были ненастолько жестоки, это и было очень необычно, и не думаю что это очень хорошо.
По мне логика того, что Сsmall стоит меньше, чем Blarge в том, что Csmall можно сдавать все 2,5 часа и знать вердикт по решению, а Blarge хоть и легче, но сдается вслепую...
А у меня B-large не прошёл по совершенно неожиданной причине: я пользовался Google Chrome, т.е. с его помощью скачивал B-large.in. После контеста выяснилось, что решение не прошло по той и только той причине, что Chrome скачал в районе 30000 строк входного файла из где-то 50000... Не знаю, как бы я в будущем мог убедиться в том, что файл действительно скачался полностью? Chrome никаких сообщений не выдавал... версия у меня последняя... В общем, причина того, что мой B-large не прошёл, только в баге самого браузера, а С++ код верный и работает корректно (если подать корректный файл).
Как быть в таких случаях? На страницах помощи GCJ такой сценарий не описан =(
Странно что система не ругнулась. Вроде бы она должна была посмотреть что строчек слишком мало и сказать это. Во всяком случае, это было бы логично. Во-вторых, можно было бы насторожится из-за "в районе". Вряд ли кто-нибудь собирается давать 34242 теста, а не максимальные ограничения или хотя бы круглое число.
Второй комментарий не понял. Дело было так: Хром скачал ровно 37185 строчек из текстового файла B-large.in, в котором на самом деле (как я потом узнал) должно было быть 53360 строчек.
Все данные были корректными, но просто несколько последних тестов оказались сокращёнными, из-за чего моя программа выдала ответ "Too Bad" на последние 8-10 тестов (что, ИМХО, не обязательно о чём-либо должно свидетельствовать).
Что имелось в виду под "хотя бы круглое число"?
"Хотя бы круглое число" — в выводе. Но да, пожалуй, всё корректно — просто прога не закончила работу, а продолжила вычислять. Тогда бы не помешал CRC.
Первый опыт ночного спортивного программирования =) В принципе интересно =) Минут 15-20 тупил по началу ибо спросонья + вчитаться в английское условие на предмет нюансов... Затем все таки сдал А и Б. Прошел с 531 места =)
P.S. Задачи понравились, хотя да, градация наверное плоховата =) А почему не приходит письмо на почтовый ящик типа Congratulations ?)