Topcoder SRM 600 пройдет в ближайшую субботу в 21:00 MSK
На раунде обещают 120 футболок для Div.1 и 40 футболок для Div.2, из которых половина раздается топу, а половина случайным участникам набравшим больше нуля баллов.
Но это еще не все. В воскресенье в 21:00 MSK будет нерейтинговый SRM 600.5 (Special Round Match). На котором раздадут еще 40 футболок и приз в 600$ для первого места. Раунд обещают веселым - с длительностью в 4 часа и состоящим из двух задач, которые не дали на онсайт TCO как слишком сложные и одной уровня Div1-Hard. Кроме топ-40 с ненулевым счетом обещают 10 футболок для случайных болельщиков (людей, кто был залогинен в арену больше 3 часов из 4-ех, но не открывал задачи).
Так же напоминаю про этап OpenCup утром в воскресенье и очередной раунд FaceBook Hacker Cup ночью с субботы на воскресенье. Всем удачных выходных :)
UPD: Также появилось новость, что начиная с этого матча TL и ML будут явно указаны в условии. Авторы говорят, что будут стараться во всех задачах использовать TL 2 секунды и ML 256 MB. (раньше было 64MB)
Где можно было посмотреть время начала FBHC до того, как я задал вопрос о том, когда он начинается? На страничке hackercup-а как-то не удалось найти.
Я умею находить только на clist.by Поэтому ссылки и нет.
Здесь вот даже ссылки на timeanddate.com есть
Лимит регистраций 2600... Сразу почему-то вспомнились древние времена, когда TC писало намного больше людей, чем СF. А теперь даже наличие футболок за юбилейные раунды не меняет баланс)
Может быть, поэтому там какие-либо фейлы случаются раз в пол года, а на CF раз в два-три раунда. Правда последнее время на CF уровень фейлов — сервер был не доступен пару минут или страницы грузились секунд по тридцать.
Для спектаторов сняли ограничение на "не открывать задачи", чтобы побольше народу поучаствовало
.
Во-первых, почему "спектаторы", а не зрители?
Во-вторых, ограничение наоборот сняли, то есть можно пытаться решать задачи и сабмитить и по-прежнему претендовать на халявную футболку.
Регистрация открывается завтра в 18:00 MSK. В прошлый раз слоты кончились за полтора часа с момента открытия регистрации, поэтому желающим попасть на раунд лучше бежать регаться пораньше, а не как обычно за десять минут до раунда.
по результатам проведенного на topcoder исследования участники из РФ читают правила быстрее всех
Небольшая проблема. Что бы писать контесты на ТС, надо скачать джаву. И когда ее предлагают скачать требуется зарегистрироваться на https://login.oracle.com/mysso/signon.jsp . Это так и должно быть?
У меня в первый раз получались где-то без регистрации скачать. Второй раз не нашел эту ссылку, поэтому пришлось регистрировться. На linux можно из репозитория легко загрузить, тогда искать ничего не придется.
http://www.oracle.com/technetwork/java/javase/downloads/jdk7-downloads-1880260.html
А почему в посте написано 21:00 MSK? Мне арена говорит, что начало через полчаса, то есть 20:00 MSK.
По ссылке в календаре на timeanddate 21-00, Вероятно у вас в Арене время неправильное стоит
Интересненько...
У меня у одного арена не работает? В логе выводит кучу ошибок вида
Missing Application-Name: manifest attribute for: http://www.topcoder.com/contest/classes/7.0/arena-client-7.0.8.jar Missing Permissions manifest attribute for: http://www.topcoder.com/contest/classes/7.0/arena-client-7.0.8.jar Missing Codebase manifest attribute for: http://www.topcoder.com/contest/classes/7.0/arena-client-7.0.8.jar
Как ни странно, потолок регистраций не достигнут. 2467 человек за минуту до конца регистрации.
Слабеет TC, слабеет...
Как решается div2 1000-point problem?
Каким же надо быть идиотом, чтобы в 600 начать писать решение за O(C(n, n / 2) * C(m, m / 2) * n * m)...
Или все-таки есть те, кто подобное пропихали?
А сколько это, если по-честному перемножить?
Больше 2 * 10**9:
(factorial(14)/factorial(7)**2)**2*14**2
2308610304
Пара миллиардов. И TL в две секунды.
А как нормально решать?
Перебрали маску по столбцам.
Идем по строчкам парами (0, n — 1), (1, n — 2) и т. д.
Для каждой пары считаем 4 величины: [не делаем палиндромами никакую строчку, делаем верхнюю, делаем нижнюю, делаем обе], при этом поддерживаем палиндромность столбцов.
Ну и добавляем это всё в простенькую динамику.
O((2^n)*n*m)
Ну, я по столбцам перебирал маску, а по строкам шёл динамикой. Динамика: прошли i строк снизу и i строк сверху, набрав среди них t (0 <= t <= 2i) палиндромов. Пересчёт можно делать почти что за сколько угодно.
Всё, как выше написал yarrr
Если по-честному, то 3432^2 * 7 * 7 = 577152576. У меня на ноуте далеко не первой свежести на макстесте отрабатывало за 3 секунды, при том решение на Java.
Да вот и исходник.
Или перепутать n и m в одном месте =(
UPD: даааа, слабые тесты!
Когда у меня что-то такое отработало локально за 3 минуты — я понял, что упихать будет трудно.
Но у меня там вообще какая-то фигня с DSU)
"Каким же надо быть идиотом"
Ну все стерва, аккуратно теперь по переулкам темным ходи ^_^
UPD: Решение "от идиота" получило AC =)
Поздравляю!
Не зря я чувствовал, что на C++ такое решение должно заходить :).
А каким нужно быть идиотом, чтобы полтора часа решать 250 для операции XOR ?)
Know that feel bro... И зачем они назвали ту переменную X, мозги сразу пропарсили X OR :D
Почему system testing уже 88,62%, а никаких резов в таблице нет?
А как 900 решается?
Во-первых, если бы у нас было просто A групп по B параллельных прямых, такие, что ни в какой точке не сходится больше двух прямых, то ответ бы был
.
Во-вторых, утверждается, что точка кратности k (через которую проходит k прямых) из ответа вычитает
.
Как посчитать количество точек каждой кратности? Сделаем полярное преобразование: заменим каждую прямую y = ax + b на точку (a, b). Тогда если прямые пересекались на исходной картинке, то соответствующие им точки на новой будут лежать на одной прямой. Осталась задача — по всем k, по всем прямым, проходящим через k точек в табличке A × B вычесть (k - 2)(k - 1) из ответа. Это делается перебором вектора прямой со взаимно простыми координатами и нетрудной арифметикой.
UPD: =( что-то моё такое решение упало, видимо, где-то баг.
Разве (a,b)? Там же инверсия, вроде как (a/sqrt(a*a+b*b),b/sqrt(a*a+b*b)).
Не-а, проверь сам. Здесь же (a, b) это один из линейных коэффициентов и свободный, поэтому правила чуть-чуть другие. Легко понять, что это значит в терминах линейной зависимости уравнений, задающих прямые.
Да, согласен, фигню сказал. Коэффициенты уравнения ни одно и то же что ближайшая к началу координат точка...
Решение за четвёртую степень должно быть очевидно: для каждой прямой прошлись по остальным, посчитали x-координату точки пересечения, сложили в вектор, посчитали количество различных k, прибавили к ответу k+1.
Теперь оптимизируем. Можно не складывать в вектор, а посчитать НОД числителя и знаменателя x-координаты и добавить к ответу 1 плюс количество других прямых таких, что этот НОД равен единице (это можно делать из-за структуры множества прямых).
Теперь смотрим внимательно на получившийся цикл и видим предподсчёт. Сначала вида "для a количество меньших b и взаимно простых". Потом сумму этой штуки для всех 1 ≤ a ≤ A1. Получился квадрат.
Шестьдесят второй. Неудача.
Ровно шестьдесятый. Удача :)
Ну у тебя ещё есть
-й шанс на рандомную футболочку =)
Надо их было раздавать с весами — чем больше счет, тем больше шансов)
ребят а если на арене вылезло такое сообщение
"The preliminary list of members who won t-shirts in this match is available at ссылка. Congratulations"
это значит что я получил футболку или всем такое приходило?
Не всем :)
Всем. Нужно смотреть список. Ссылка сейчас лично у меня не работает.
черт( Я уже думал что я везучий=(
Я конечно не уверен, но мне пришло, и мне тут говорят, что меня в спсике нет:)
я уже увидел что меня нет в списках(
На случай если ссылка всё ещё не работает (у меня открылось через 5 минут).
Ага, спасибо.
Не ну вы гляньте кто на последнем месте, ржунимагу
Красавец, поздравляю!
спс, что самое прикольно как раз давно хотел какую-нибудь майку) Теперь тот еще квест как ее от них получить.
Сегодня хотя бы ещё за участие, а завтра есть шанс на футболку за открыть арену и пойти спать/по делам/за пивом/...
Странная фигня — человек получил футболку без участия.
Would you say how did you get these informations , because i couldn't find anything about there are two problems.
An e-mail have been sent, to those requesting frequent e-mails with news about SRMs and so. Not sure where is it present on the Website or not!
странное решение, на мой взгляд, давать футболку рандомным людям. казалось бы логичным дать просто топу, а так получил футболку рандомно, какой-то соревновательный момент пропадает. тот кто 61, например, и не получил футболку, а тот кто 100500 хоп — и ни за что на тебе футболку от ТС. понимаю, что это just fun, но все же.
просто так наверное привлекается как можно больше народу, что бы у всех участником была хоть какая то интрига:)
да, наверное, но кажется, это единичное привлечение, т.е. в следующий раунд будет столько же человек участвовать, как и в предыдущий
Ирония в том, что 61 получил футболку по списку random selection.
What's the idea of 500 (Div. 1, SRM 600) ?
Are the problems gonna be as difficult as div1 hard or not ?
Я так и не понял, действует еще правило "10 футболок для случайных болельщиков (людей, кто был залогинен в арену больше 3 часов из 4-ех, но не открывал задачи"
Походу если не мог принять участие в контесте, правильная тактика была зарегаться на матч, прийти на чалы, почалить всех рандомными тестами и c большой вероятностью получить майку. 50 очков уже 40-е место.
Я так и планировал! К сожалению, дабл-клик по решению почему-то не работал. Оказывается, надо было перезайти в комнату, чтобы он заработал. Topcoder fix it please! Ну а к тому времени, как я догадался перезайти, решение уже взломали.
Правда, Alex_2oo8 заметил, что в случае tie'в, майки не дадут всем, а будут давать рандомно. То есть на данный момент, шансы получить майку с 50 очками: 4/34.
Вот 2 чала уже дают майку, но для этого надо было иметь хотя бы 2 сабмита в комнате, что было далеко не у всех. :D
Сейчас эти шансы повысились до 23/39.
Upd. Появились результаты (см. ссылку ниже). Я немного пролетел.
кто знает где посмотреть кого наградили футболками ТС 600.5?
http://apps.topcoder.com/forums/?module=Thread&threadID=806914
"The handles of 10 spectators who also won t-shirts will be announced shortly."<--эта фраза оставляет маленькую, но надежду:)
SRM 600 editorial