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

Автор Egor, 12 лет назад, По-английски

Just a kindly reminder that TopCoder SRM #568 will start in about hour and a half

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

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

Егор, спасибо, а то я бы опять пропустил :)

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

Какой клёво сбалансированный контест.
Секунды решают десятки, если не сотни мест. Хорошо, хоть очки зависят от секунд, а не как здесь — от минут
PS Никаких претензий к автору. Он молодец.

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

    А челлендж решает 300+ мест.
    Великолепно, учитывая что их возможность сильно зависит от комнаты.

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

Как делать 500?

У меня были идеи с дфс и кучей муры, но так я это и не дописал.

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

    Ну пока сэмплы проходит такое решение: посмотрим на таблицу, как на двудольный граф, где ребра — клетки, в которых стоит не '-'. Тогда в каждой компоненте связности такого графа можно определить все значения(это как раз какой-то дфс), проверим сразу что все они неотрицательные и найдем в каждой компоненте минимальное, пусть они получились v0, v1, ..., vm - 1. Тогда нам нужно найти количество таких наборов чисел x1, x2, ..., xm - 1, что min(0, x1, x2, ..., xm - 1) + min(v0, v1 - x1, ..., vm - 1 - xm - 1) ≥ 0(вообще говоря сумма слева это и будет минимальное число во всей таблице). Для этого можно например зафиксировать левый минимум и первое из чисел на котором он достигается. Тогда на все остальные иксы будут просто лежать в каких-то отрезках, надо просто перемножить их длины.

    прошло, но на задачу пришлось потратить два срма :o

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

    Что такое куча муры?

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

Что интересно, были 2ые задачи на много легче сегодняшней, но имели стоимость 600.

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

    Сложность относительна внутри одного матча

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

      Есть же универсальное мерило — челлендж. Тогда надо и его стоимость менять.
      Upd. Поясню: если написанное выше верно, то можно было бы сделать стоимости, например, 25000-50000-100000. Но так сделать сложно, ведь они "завязаны" на челленджи, которые бы обесценились.
      Upd2. На самом деле написанное Егором правда, но этого не достаточно чтобы оправдывать стоимости задач, так как есть челленджи.

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

        Челлендж есть, но изменения в стоимостях задач достаточно малые, чтобы нарушить баланс челленджа. Ведь стоимости в 512 СРМе явно ставили не задумываясь о челленджах ;)

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

Why KADR's solution was challenged? It looks right as for me.

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

МГУ Хэт Трик, однако :)

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

I compete on SRM 568 DIV 2 and using dp table 55 * 5 * 55 * 55 * 55 for 500 pt that approximately 45753125 and I got SIGKILL on final test, I wanna ask, what's is memory limit for topcoder ? Thanks