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

Автор chrome, история, 9 лет назад, По-русски

Всем привет!

В данный момент идет SNSS R1, и будет идти до 10 августа.

Как и всегда, предлагаю обсудить задачи после контеста)

Всем удачи!

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

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

Разрешён ли prewritten код?

В правилах не нашёл ничего по этому поводу.

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

Посылки вслепую протестируются после раунда? Раньше вроде сразу показывали вердикты.

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

    Так можно же в дорешивание послать, и узнать, что проходит, а что нет.

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится -27 Проголосовать: не нравится

Жюри не отвечает на клары уже несколько часов, что делать?

UPD. Уже ответили.

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

Как решать C?

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

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

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

В D какой-то перебор?

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

    в Д. в искомой подматрице 1 клетка одного цвета, 2 клетки другого, К клеток еще какого-то. поэтому мы знаем площать подматрицы — к * (к + 1) / 2. поэтому перебираем левый верхний угол, перебираем длину, если площадь делится на длину то получили высоту. проверяем подматрицу на хорошесть частичными суммами.

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

    Так как нам известно количество клеток в основном элементе (k * (k+1) / 2), то мы сможем легко найти все возможные размеры сторон основного элемента (их будет не много). Теперь для каждой клетки переберем все возможные длины сторон и попытаемся построить основной элемент с одной из вершин в перебираемой клетке. Для того, чтобы быстро посчитать количество букв в основном элементе и количество каждой буквы можно воспользоваться динамикой dp[26][251][251], где dp[i][j][k] — количество букв i в прямоугольнике начинающемся в (0,0) с длиной сторон (j,k). Можно воспользоваться битовой маской для нахождения возможных количеств букв и сравнивать с таргетом. Общая сложность O(N * M * 26).

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

Как решать E?

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

    Надо динамикой из A обработать ребра с d > 0 и дейкстрой из B ребра с d = 0

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

      Можно идти с одной и той же стороны, не различая рёбра: пустить Дейкстру k раз для каждого возможного остатка бензина, то есть почти то же самое, что Дейкстру один раз на большом графе. Суммарно в графе 200·2000 вершин и 200·10 000 рёбер. Если сделать не одну очередь с приоритетами на все вершины, а 200 очередей с 2000 вершинами каждая, сдаётся с почти двухкратным запасом (на D 1.65 секунды из 3).

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

      На самом деле можно просто запустить дейкстру на графе, в котором есть вершина для каждого города и для каждого значения остатка топлива.

      Код

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

        В коде не дейкстра. И даже не SPFA: не проверяется, что вершина уже в очереди. По-моему, лучше так не писать, особенно, если сдавать в слепую.

        Такое же решение с обычной дейкстрой с set работает за 0.595с без риска свалиться на анти-SPFA тесте.

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

          Да. Всё именно так. Никак не отучусь, потому что в 90% случаев заходит.

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

      Можно просто дейкстрой. Состояние — вершина+сколько бензина.

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

Прошу прощения, если пишу не туда, но решил не создавать новую тему.

У меня одного произошла такая штука? Написал пару дней назад 2 раунд, а теперь меня нет в таблице и по всем задачам написано "нет посылок", хотя написано, что "Ваше участие в соревновании завершено"

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

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

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

Как решать B?

Мое решение понятно ловит TL

  #define FOR(i, a, b) for (int _n(b), i(a); i < _n; i++)
  #define rep(i, n) FOR(i, 0, n)

  typedef long long ll;

  ll dp[2][255][255];

  int N, K;
  cin >> N >> K;
  ++N;
  --K;

  FOR(i, 1, N) dp[0][i][i] = 1;
  rep(i, K) {
    int cur = i & 1;
    int nxt = cur ^ 1;
    rep(x, N) rep(y, N) dp[nxt][x][y] = 0;
    FOR(n, 1, N) FOR(t, 1, N) {
      for (int m = n; m + t < N; ++m) {
        dp[nxt][m][m + t] += dp[cur][n][t];
      }
    }
  }

  ll ans = 0;
  FOR(i, 1, N) ans += dp[K & 1][i][N - 1];
  cout << ans << endl;

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

Про второй раунд.

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

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

Читайте условия внимательнее, господа.