Блог пользователя PavelKunyavskiy

Автор PavelKunyavskiy, 11 лет назад, По-русски

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)

  • Проголосовать: нравится
  • +205
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

Где можно было посмотреть время начала FBHC до того, как я задал вопрос о том, когда он начинается? На страничке hackercup-а как-то не удалось найти.

»
11 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Лимит регистраций 2600... Сразу почему-то вспомнились древние времена, когда TC писало намного больше людей, чем СF. А теперь даже наличие футболок за юбилейные раунды не меняет баланс)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    Может быть, поэтому там какие-либо фейлы случаются раз в пол года, а на CF раз в два-три раунда. Правда последнее время на CF уровень фейлов — сервер был не доступен пару минут или страницы грузились секунд по тридцать.

»
11 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Для спектаторов сняли ограничение на "не открывать задачи", чтобы побольше народу поучаствовало

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

    .

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Во-первых, почему "спектаторы", а не зрители?

      Во-вторых, ограничение наоборот сняли, то есть можно пытаться решать задачи и сабмитить и по-прежнему претендовать на халявную футболку.

»
11 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Регистрация открывается завтра в 18:00 MSK. В прошлый раз слоты кончились за полтора часа с момента открытия регистрации, поэтому желающим попасть на раунд лучше бежать регаться пораньше, а не как обычно за десять минут до раунда.

»
11 лет назад, # |
  Проголосовать: нравится +52 Проголосовать: не нравится

по результатам проведенного на topcoder исследования участники из РФ читают правила быстрее всех

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Небольшая проблема. Что бы писать контесты на ТС, надо скачать джаву. И когда ее предлагают скачать требуется зарегистрироваться на https://login.oracle.com/mysso/signon.jsp . Это так и должно быть?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А почему в посте написано 21:00 MSK? Мне арена говорит, что начало через полчаса, то есть 20:00 MSK.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    По ссылке в календаре на timeanddate 21-00, Вероятно у вас в Арене время неправильное стоит

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

У меня у одного арена не работает? В логе выводит кучу ошибок вида

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

»
11 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Как ни странно, потолок регистраций не достигнут. 2467 человек за минуту до конца регистрации.

»
11 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Как решается div2 1000-point problem?

»
11 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Каким же надо быть идиотом, чтобы в 600 начать писать решение за O(C(n, n / 2) * C(m, m / 2) * n * m)...

Или все-таки есть те, кто подобное пропихали?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А сколько это, если по-честному перемножить?

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      Больше 2 * 10**9:

      (factorial(14)/factorial(7)**2)**2*14**2

      2308610304

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Пара миллиардов. И TL в две секунды.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        А как нормально решать?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

          Перебрали маску по столбцам.

          Идем по строчкам парами (0, n — 1), (1, n — 2) и т. д.

          Для каждой пары считаем 4 величины: [не делаем палиндромами никакую строчку, делаем верхнюю, делаем нижнюю, делаем обе], при этом поддерживаем палиндромность столбцов.

          Ну и добавляем это всё в простенькую динамику.

          O((2^n)*n*m)

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

          Ну, я по столбцам перебирал маску, а по строкам шёл динамикой. Динамика: прошли i строк снизу и i строк сверху, набрав среди них t (0 <= t <= 2i) палиндромов. Пересчёт можно делать почти что за сколько угодно.

          Всё, как выше написал yarrr

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Если по-честному, то 3432^2 * 7 * 7 = 577152576. У меня на ноуте далеко не первой свежести на макстесте отрабатывало за 3 секунды, при том решение на Java.

      Да вот и исходник.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    Или перепутать n и m в одном месте =(

    UPD: даааа, слабые тесты!

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Когда у меня что-то такое отработало локально за 3 минуты — я понял, что упихать будет трудно.

    Но у меня там вообще какая-то фигня с DSU)

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +205 Проголосовать: не нравится

    "Каким же надо быть идиотом"

    Ну все стерва, аккуратно теперь по переулкам темным ходи ^_^

    UPD: Решение "от идиота" получило AC =)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      Решение "от идиота" получило AC =)

      Поздравляю!

      Не зря я чувствовал, что на C++ такое решение должно заходить :).

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +41 Проголосовать: не нравится

    А каким нужно быть идиотом, чтобы полтора часа решать 250 для операции XOR ?)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +27 Проголосовать: не нравится

      Know that feel bro... И зачем они назвали ту переменную X, мозги сразу пропарсили X OR :D

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Почему system testing уже 88,62%, а никаких резов в таблице нет?

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

А как 900 решается?

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Во-первых, если бы у нас было просто A групп по B параллельных прямых, такие, что ни в какой точке не сходится больше двух прямых, то ответ бы был .

    Во-вторых, утверждается, что точка кратности k (через которую проходит k прямых) из ответа вычитает .

    Как посчитать количество точек каждой кратности? Сделаем полярное преобразование: заменим каждую прямую y = ax + b на точку (a, b). Тогда если прямые пересекались на исходной картинке, то соответствующие им точки на новой будут лежать на одной прямой. Осталась задача — по всем k, по всем прямым, проходящим через k точек в табличке A × B вычесть (k - 2)(k - 1) из ответа. Это делается перебором вектора прямой со взаимно простыми координатами и нетрудной арифметикой.

    UPD: =( что-то моё такое решение упало, видимо, где-то баг.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Разве (a,b)? Там же инверсия, вроде как (a/sqrt(a*a+b*b),b/sqrt(a*a+b*b)).

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Не-а, проверь сам. Здесь же (a, b) это один из линейных коэффициентов и свободный, поэтому правила чуть-чуть другие. Легко понять, что это значит в терминах линейной зависимости уравнений, задающих прямые.

        и (a, b), (c, d) и (e, f) — коллинеарны.

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Да, согласен, фигню сказал. Коэффициенты уравнения ни одно и то же что ближайшая к началу координат точка...

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Решение за четвёртую степень должно быть очевидно: для каждой прямой прошлись по остальным, посчитали x-координату точки пересечения, сложили в вектор, посчитали количество различных k, прибавили к ответу k+1.

    Теперь оптимизируем. Можно не складывать в вектор, а посчитать НОД числителя и знаменателя x-координаты и добавить к ответу 1 плюс количество других прямых таких, что этот НОД равен единице (это можно делать из-за структуры множества прямых).

    Теперь смотрим внимательно на получившийся цикл и видим предподсчёт. Сначала вида "для a количество меньших b и взаимно простых". Потом сумму этой штуки для всех 1 ≤ a ≤ A1. Получился квадрат.

»
11 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Шестьдесят второй. Неудача.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    Ровно шестьдесятый. Удача :)

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ну у тебя ещё есть -й шанс на рандомную футболочку =)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Надо их было раздавать с весами — чем больше счет, тем больше шансов)

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      ребят а если на арене вылезло такое сообщение

      "The preliminary list of members who won t-shirts in this match is available at ссылка. Congratulations"

      это значит что я получил футболку или всем такое приходило?

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +33 Проголосовать: не нравится

      Сегодня хотя бы ещё за участие, а завтра есть шанс на футболку за открыть арену и пойти спать/по делам/за пивом/...

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Would you say how did you get these informations , because i couldn't find anything about there are two problems.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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!

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

странное решение, на мой взгляд, давать футболку рандомным людям. казалось бы логичным дать просто топу, а так получил футболку рандомно, какой-то соревновательный момент пропадает. тот кто 61, например, и не получил футболку, а тот кто 100500 хоп — и ни за что на тебе футболку от ТС. понимаю, что это just fun, но все же.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    просто так наверное привлекается как можно больше народу, что бы у всех участником была хоть какая то интрига:)

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      да, наверное, но кажется, это единичное привлечение, т.е. в следующий раунд будет столько же человек участвовать, как и в предыдущий

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +52 Проголосовать: не нравится

    Ирония в том, что 61 получил футболку по списку random selection.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What's the idea of 500 (Div. 1, SRM 600) ?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are the problems gonna be as difficult as div1 hard or not ?

»
11 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Я так и не понял, действует еще правило "10 футболок для случайных болельщиков (людей, кто был залогинен в арену больше 3 часов из 4-ех, но не открывал задачи"

»
11 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Походу если не мог принять участие в контесте, правильная тактика была зарегаться на матч, прийти на чалы, почалить всех рандомными тестами и c большой вероятностью получить майку. 50 очков уже 40-е место.

  • »
    »
    11 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    Я так и планировал! К сожалению, дабл-клик по решению почему-то не работал. Оказывается, надо было перезайти в комнату, чтобы он заработал. Topcoder fix it please! Ну а к тому времени, как я догадался перезайти, решение уже взломали.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

      Правда, Alex_2oo8 заметил, что в случае tie'в, майки не дадут всем, а будут давать рандомно. То есть на данный момент, шансы получить майку с 50 очками: 4/34.

      Вот 2 чала уже дают майку, но для этого надо было иметь хотя бы 2 сабмита в комнате, что было далеко не у всех. :D

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        Сейчас эти шансы повысились до 23/39.

        Upd. Появились результаты (см. ссылку ниже). Я немного пролетел.

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

кто знает где посмотреть кого наградили футболками ТС 600.5?

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится