TopCoder(R) Single Round Match 504.5 is scheduled for Tuesday, May 17, 2011 at 11:00 UTC -4 hours.
Please be sure to check here for the start time in your time zone:
http://www.timeanddate.com/worldclock/fixedtime.html?iso=20110517T11&p1=179
* Registration will begin at 8:00 and will end at 10:55 UTC -4 hours
* Allowable programming languages are Java, C++, Microsoft(R) Visual
C#(R) .NET, and Microsoft Visual Basic(R) .NET
* TopCoder Administrators will be available in the Admin Lobby Room to answer questions
* For more details click here:
http://www.topcoder.com/tc?module=MatchDetails&rd=14514
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | jiangly | 3578 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | tourist | 3565 |
| 8 | maroonrk | 3531 |
| 9 | Radewoosh | 3521 |
| 10 | Um_nik | 3482 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 28.04.2024 19:01:56 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
Возможно, вопрос немного не по теме, но он связан с ТС на прямую.
Как запустить арену через прокси в Убунту 11.04? То есть да, там при входе можно прописать настройки, но у меня арена даже не запускается, когда я запускаю jnlp файл, javaws что-то пытается скачать с ТС и фейлится с кучей ошибок. В stderr пишет следущее:
javaws TopCoder.jnlp
Unable to use Firefox's proxy settings. Using "DIRECT" as proxy type.
deployment.proxy.type=1
deployment.proxy.http.host=<адрес твоего прокси>
deployment.proxy.http.port=<порт>
Описание этих и других параметров можно посмотреть здесь:
http://download.oracle.com/javase/6/docs/technotes/guides/deployment/deployment-guide/properties.html
javaws -Ddeployment.proxy.type=1 -Ddeployment.proxy.http.host=<адрес твоего прокси> -Ddeployment.proxy.http.port=<порт> TopCoder.jnlp
Я в 900 считал подобие динамики - состояние (i,j) - это "перед нашим героем осталось i, после него уже стоит j". Прошли все начало - разбираемся с героем - снова по кругу.
Соответственно, мотал круги до тех пор, пока вероятности не станут достаточно маленькими.
Благо они быстро убывают, так как вероятность захода на новый круг 0.5 (когда очередь доходит до героя, в 2 из 6 наш герой пойдет гулять, еще в одном из 6 станет победителем)
Что-то там выдает:) Прошло, словом.
У такого решения сложность получается n*n*c, где c - константа, логарифм необходимой точности в минус первом.
Но спасибо, в свободное время попробую чистый квадрат сделать.
550 - ну вообще заметим, что у нас возможны 2 варианта либо в какой-то момент они все станут равны, либо максимальный никогда не изменится.
(если все равны, то ответ я думаю очевиден).
Если же максимальный не меняется, то значит у нас будет не слишком много итераций сделанно, пока не закончатся деньги.
900 - Введем n*n состояний, где [i][j] будет говорить вероятность, того что выйграет jый человек в очереди из i человек. Тогда заметим, что у нас возможны следующей ситуации:
1) i == 1, тогда ответ 1 из условия
2) i != 1, j != 1, тогда можно записать что он с вероятностью 1/3 попадет в [i-1][j-1], 1/2 [i][j-1].
3) i != 1, j == 1, тогда с вероятностью 1/6 мы выйграли, а иначе с вероятностью 1/2 мы переходим в [i][i].
Хорошо, а теперь научимся считать [i][1] если мы умеем считать [i-1][x], где x - любое.
Пусть x - вероятность, того что нас выберут, тогда если пройти 1 круг по цепочке мы получим что
x = p * x + sum,
где p - вероятностью прохода по кругу, а sum - вероятность того, что мы будем выбраны перейдя к меньшему числу человек.
Решая это уравнение и находим [i][1], ну а далее уже можно спокойно посчитать [i][x] и считать следующее число человек.
К сожалению 900 не успел сдать, из-за того что медлил с 550.
Для количества лет существования проекта это неверно.
Конкретно TopCoder, насколько я понимаю, подзабил активно поддерживать алгоритмические соревнования в последние несколько лет, работает — и ладно. Арена хорошо работала и развивалась первые несколько лет. Тогда алгоритмы были гораздо более важны для привлечения кодеров в другие ветки (Design, Development, ...). А сейчас Algorithm Track держится не на политике компании, а на энтузиазме отдельных людей.
А CodeForces — кто знает, как будет развиваться ;) .
Во-первых, делать задачи на переполнение long long --- не лучшая практика, как минимум это ставит в неравное положение плюсовиков и яверов (да, конечно эти проблемы обойти не очень сложно, но все равно, на мой взгляд -- fail)
Во-вторых, делать третью задачу на столь простую динамику --- тоже не айс, ведь в топкодере время начинает тикать с момента открытия задачи и рассчитывать на то, что участники прочтут все и начнут решать самое простое --- не хорошо. (Третью задачу сдало больше народу, чем вторую)
В-третьих, вторая задача - роскошная задача на математическую олимпиаду, но не на прогерскую. Ведь некоторые участники могли написать верное решение просто не задумываясь о ТЛ, в то время, как более опытные тратили время на доказывание временных оценок.
Итого - с моей точки зрения контест очень неудачный.
Особенно если при этом решение задач не вызывает удовольствие. А вторая задача, на мой взгляд, могла порадовать только мазохиста=)
P.s. Наконец-то я и на топкодере покраснел))).
По-моему, это скучно.
Переполнение в задаче 2 --- вопрос не принципиальный(как во многих задачах на длинку), задача была бы столь же интересна и с ограничениями 10^16. Оно не особо спрятано, т.е. не нужно задумываться переполнится или нет. И оно не добавляет задаче ничего, кроме необходимости написать арифметику в двух лонгах.
Т.ч. я не скажу, что о чем-то тут надо думать, просто писать лишние 10 неинтересных строк кода, если вы не выбрали Яву.
Нетривиально оцениваемая сложность --- тоже не минус(да и не сказал бы, что она столь уж нетривиальна). Но мне не нравятся задачи, где идея очевидна, а корректность решения --- нет. Может быть я слишком строг, но я считаю, что не должно быть людей, которые задачу сдали, а объяснить почему работает --- не могут.
Интуиция это конечно здорово, если она подкреплена знаниями. А писать коды на авось --- на мой взгляд, зло.
каждое число можно представить так: a[i]=b[i]*n+c[i], 0<=c[i]<n
сложим все b[i] и прибавим сумму всех c[i], деленную на n c округлением вниз
Я не читал задачу и могу ошибаться, но ведь если у нас например 5 чисел: 4 4 4 4 4, то их среднее арифметическое - 4, а ты выведешь 0. Разве нет?UPD. да, не так прочитал, извиняюсь. Сначала складывать, потом делить, не наоборот.
Нет, ну это уже тоже... не совсем...
На АСМ-олимпиаде, тогда, тоже неравные условия - кто-то решил писать скучную геометрию, кто-то задачу, которая кажется простой, но там куча камней, а кто-то все это отложил, или же не заметил сначала, а нашел одну-две тупизны, которые требуют немного подумать, но легко и без проблем сдаются.
Открыл задачу - так кто тебе запрещает ее делать? Тут нету "дальнейшего влияния штрафов", так что от того, сдать сначала 250, а потом открыть и сдать 900, или же наоборот, мало что зависит.
В том, что человек, который открыл задачу, не может ее решить, слабо заметно вину автора задачи.
Хотя для тех, кто решил все --- порядок, разумеется, не важен.
Понял мысль. Все равно, правду уже было сказано выше, скучно, когда все "правильно".
Я вообще в последних матчах редко открываю задачи с самого начала, а жду, чтоб понять сложность 250 по монитору:) А когда сдаю 250, уже видно, какой сложности вторая, и есть ли подводные камни в первой.
Если серьезно, я считаю, что если прошло 100 контестов и выработалась некоторая система общего среди этих контестов (типа задачи стоят 250*(1<<i)+eps, для первых двух достаточно базовых алгоритмов, в первой ~15 строк кода и т.п.), и перед 101 контестом ничего особенного сказано не было - он должен соответствовать всему, что общее для первых 100.
А для тех, кому скучно, вот abbyy провела кубок. Ни нормальных правил, ни пробного тура вовремя, ни интересных задач, зачем то 8 часов, выпендреж с символом олимпиады, разводилово с призами, даже свой ящик и тот защищен от спама (причем методами, которым лет 10-15), чего я еще нигде не видел.
Задач всего три. Обычно, если ты крут, ты сам придумаешь, в каком порядке открывать. А если нет, после сдачи предыдущей задачи помогает посмотреть в монитор на следующие.
Ну и ещё. Если считать, что успеешь не более чем одну из оставшихся, можно открыть одну, а затем выбрать, не забить ли на неё и не открыть ли другую. Если считаешь, что успеешь обе, вроде бы всё равно, в каком порядке открывать.
Но во-первых, к счатью, обычно задачи все-таки расположены по сложности и такое поведение бессмысленно, а во вторых, процесс подобного выбора задачи для решения без сомнения увлекательный, но какое он имеет отношение к Algorithm Competition?
Во-первых, если мне не понравился один тур из 504,5, то могу предположить, что следующий мне все-таки понравится.
Во-вторых, как раз из любви к олимпиадному программированию и топ кодеру, в частности, я и написал здесь (как я надеюсь) конструктивную критику.
Если найдется хотя бы один человек, который составляя задачи к какому-нибудь контесту, впомнит хотя бы одно из моих замечаний, то я писал их не зря.
Мы ведь хотим изменить мир к лучшему, правда?=)
У кого-то рейтинг вырос, кто-то впервый раз хард сдал --- на радостях идем и голосуем за
единую россиюконтест.Я постарался высказать, какие именно моменты в этом контесте мне показались неудачными.
Написал, почему я считаю их такими. Если вы считаете, что мои высказывания не разумны --- попробуйте высказать свою точку зрения.
Кроме всего прочего вы видимо не достаточно подробно читали дискуссию, которую решили откомментировать.
Неверный порядок задач --- лишь один из трех моментов, которые меня в этом контесте не устроили.
Какого порядка выгоднее придерживаться --- вообще отдельная тема и повод многих холиваров людей, не способных решить все три.
Мне не нравится, что в этот раз порядок не соответствовал сложности, и я попытался обратить внимание на то, что в отличие от всех остальных контестов --- для топкодера это принципиально.
Ваши сообщения:
Ну так никто ж не заставляет учавствовать.
А персональная обида...
Больше всего это походе на неприкрытый троллинг и переход на личности. Если вы с чем-то не согласны, попробуйте оставить более содержательный комментарий.
Если бы авторы системы считали так, Medium можно было бы открыть только после Easy, а Hard только после Medium.
А раз нет, значит, авторы системы предполагали, что бывают и другие стратегии... И авторы проблемсетов вполне могут это использовать.
О, сдал первую, осталось 30 минут...
Две задачи решить не успеваю...
Открою пожалуй третью, хоть она и посложнее, но время еще есть, а баллов за нее дадут больше...
А угадывать, которая из трех задач сеголня easy - это по-моему для соревнования экстрасенсов, а не программистов.
Лично я стараюсь не холиварить, а аргументированно высказывать свою позицию. Не секрет, что авторы многих контестов (бывает, что даже контестов на топкодере) бывают на этом сайте.
Вполне возможно, что при составлении задач некоторые из них учитывают мнение сообщества.
Во-вторых, проблемма с челенджами действительно имеется, так, например, на втором яндекс квале я собрал все челенджи в своей комнате, что позволило относительно компенсировать слив контеста. Едва ли я смог бы повторить такое выступление окажись в моей комнате Егор, например.
Эта проблемма неоднократно обсуждалась, в том числе здесь (кстати влияние хаков на кодфорсесе в среднем гораздо выше, чем челенджей на топкодере), но никакого удовлетворительного решения никто так и не предложил. (Отмена челенджей как таковых гораздо большее зло, чем некоторая доля рандома)
Однако вы ушли от темы. Проблема с челенджами и варианты ее решения никак не связаны с тем вопросом, который мы обсуждали.
Некоторая доля рандома всегда будет --- у кого интернет неожиданно вылетит, кто в пробке застрянет, у кого еще какие-нибудь проблеммы возникнут. Так что же, раз не можем избавиться от рандома везде --- не будем избавляться нигде?
Тогда действительно кости можно покидать, а задачи решать отдельно от контеста, чтобы не мешать сладкое с круглым.
Стратегия --- это действительно проблема участника, но есть определенные традиции (писанные и неписанные)
Так на контесте топкодера люди привыкли видеть три задачи на английском языке, ввода-вывода нет, все тесты --- обращения к методу, задачи расположены в порядке сложности. Это даже породило устоявшийся сленг, такой как изи, медиум, хард.
Говорить о разумной стратегии решения можно на контестах, где все условия доступны изначально. Если ты не можешь прочитать условия в начале контеста, то выбор стратегии --- во многом угадай-ка. Ведь даже статистика сдач по дивизиону может быть неверной --- неизвестно сколько задач упадет на челенджах. Кроме того, если задачи решать умеренно быстро, то решив первую вы сталкнетесь с проблеммой: никто второй и третей пока не порешал. И как же работает ваша стратегия? Сходить минут на 10 покурить?
единую россиюконтест.""Отсутствие элементов случайности и постановка всех игроков в равные условия --- абсолютно разные вещи." - у тебя задачи другие были? или отобрали сотню-другую баллов ни с того, ни с сего? не верю :)
---
Вы читали текст выше, или просто решили прокомментировать?
С чего вы взяли, что я считаю, что кто либо был в неравных условиях?
Никого обидеть я не хотел, просто опрос - очень специфическая форма сбора информации. Ведь с вас не просят никакой аргументации.
Если вы мне не верите, можно где-нибудь организовать эксперементы выявляющие такие явления, например, как зависимость результата опроса от того, какой пункт голосования стоял выше, или от постановки вопроса.
---
остальное - разговор о том, какие хреновые у TC правила и как всё несправедливо для тех, кто не угадал с порядком задач
---
Я хотя бы раз высказал неодобрение правилами ТС?
Все, что я говорил --- формат правил топкодера плохо совместим с нестандартной разбаловкой задач.
И даже попытался объяснить почему.
Но я на самом деле не думаю, что это была идея авторов(скорее случайность --- вряд ли они ожидали, что так получится)
Я не думаю, что кто-то из авторов специально делает третью задачу проще первой, а если такая тенденция появится, то наверняка организаторы попытаются что-то предпринять.
(я не хочу сказать, что на этом контесте третья задаче проще первой)
Что касается позиции freopenа --- я ее разделяю, но не вижу, почему ты считаешь, что он сомневался в равенстве всех участников?
Моя позиция изначально была именно такой --- Топкодер, это (видимо единственное) соревнование, где неверная разбаловка ведет к неоправдано большому влиянию случайности на результаты людей, не способных решить три задачи.
900я в среднем занимала у людей меньше времени, чем 550.
900я короче по коду.
в 900й - известная идея, которую надо просто реализовать, тогда как 550я - на подумать.
Лично для меня 900 - гораздо проще.
Как-то так.
А определить, какая задача проще --- не так уж и сложно.
По крайне мере третья задача, в которой нужно 15 строчек кода --- это уже редкость, и должно было заставить задуматься.
Разумеется точно определить сложность --- не просто, но понять, что сегодняшняя 900я - не хард, вполне реально.
UPD. не успел :)
Но, к сожалению, конкретно этот механизм очень чувствителен к правильному сложностному порядку.
В топкодере же приходится либо действовать вслепую(не зная условий) либо
прочесть условия в начале, смирившись с запуском таймера, и заработать совершенно смешные баллы по каждой из задач.
Решения примерно такие:
не давать лишних сложностей, с переполнениями там, где они не интересны.
Уделять больше времени на тестирование относительной сложности задач, при подготовке задач для топкодера, т.к. это единственный из популярных сегодня контестов, где порядок действительно значим.
Не давать задач, где правильное решение пишется "случайно".
Последний пункт, конечно субъективен, но на мой взгляд в идеальном контесте в ваакуме ни один участник ничего случайно решить не должен.
Еще раз повторяю. Отсутствие порядка задач мешает строить стратегию. А именно, если я собираюсь решить первую и третью задачу, т.к. после первой и второй в среднем остается достаточно времени (но слишком мало, чтоб сдать все три), я расчитываю на то, что вторую писать ну минимум минут 20-25. И тут я в середине контеста вижу большое количество 490+ баллов по второй задаче и понимаю, что она совсем халява. Если я увидел это достаточно рано, мне придется бросить третью, чтоб не рисковать и потом к ней вернуться (с перспективой потери баллов). Если поздно, я не успеваю ее закодить и сдаю третью задачу, которая стоит меньше, чем вторая, т.к. ее дольше кодить.
Такие же рассуждения можно привести для любой стратегии, не только для вашей.
Рекомендую на эту тему: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=integersReals (обе части).
http://en.wikipedia.org/wiki/Extended_precision
Гугл подсказывает, что это из-за выравнивания переменных по 4-байтным границам, и что на 64-битном процессоре вообще 16 байт вместо 10.
Странно, я думал, что с появлением процессора Athlon проблемы с выравниванием перестали всех так волновать.
Upd. Хотя, впрочем, ладно. Понять можно, если знать, что оно выравнивается, а sizeof чаще используется для заполнения массивов, чем для проверки диапазона значений типа. Но за то, что про это большими буквами не написано в первой ссылке в "Гугле", кому-то всё-таки минус в карму.
За одну итерацию васиного алгоритма разница между самым бедным и самым богатым другом уменьшится как минимум в n/(n-1) раз (худший случай для каждой итерации - все друзья, кроме одного, самые бедные). Такая оценка говорит, что гарантированно хватит 91 000 итераций, но достаточно и 40000 (30000 уже мало). Тем не менее, достаточно точно, разница всего в 2 раза.
1 1 3 3 -- разница 2
3 1 3 3 -- разница 2 - не уменьшилась.
Надо рассматривать более долгие итерации - например, взяв за "итерацию" период между получения бонуса одним и тем же человеком.
Но суть от этого не меняется. Конкретный друг гарантированно сравняется с самым богатым за 2000 итераций, примененных именно к нему.