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

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

Is starting right now.

Теги srm, tc, 569
  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

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

Что и как нужно перебирать в 500?

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

Феерический челенж, не могу это не запостить

Код c175353 (он красный) по 250:

int minimumAdditional(vector<string> s) {
    s.clear();
    int n = s.size(), m = s[0].size(), ans = 0;
    REP(i, m) {
        int cnt = 0;
        REP(j, n) if (s[i][j] == '1') ++cnt;
        if (cnt < 2) ans = max (ans, 2-cnt);
        if (cnt == n) ans = max(ans, 1);
    }
    return ans;
}

Читаю, вижу что на одну '1' он ответит 1 вместо 2, челенжу — unsuccessful. И так ещё двое в моей комнате челенжат, видимо по тому же тесту.

Потом замечаю s.clear() и понимаю что эта штука ВСЕГДА отвечает 2 :)

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

Обидно, упали и 250 и 500. Вдвойне обидно что дописал 1000 через 5 минут после конца

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

Решение третьей.

Напомню условие: N!k = N!k - 1 * (N - 1)!k . Единички при N = 0, при k = 0 совпадает с N, из чего вытекает что k = 1 это обычный факториал. Если взять логарифм то формула расчёта будет как у Ckn + k. Посчитать число нулей на конец числа в системе счисления B, по модулю MOD.

Сначала посчитаем ответ для простого B. Всё можно раскрыть в произведением чисел. Понятно, что надо учитывать только вклад чисел делящихся на B. Посчитаем сколько раз число X = Bt * u меньшее N появится в произведении: по формулам нетрудно вывести, что это Ck - 1k - 1 + (n - X). При k = 1 (обычный факториал) каждая пара (t, u) даёт нам по единичке, получаем частный случай: N / B + N / B2 + N / B3 + ....

Будем перебирать t, сумма C-шек с разным u считается возведением матрицы в степень (k маленькое, в векторе храним C^i_k и сумму). Конечно, при этом придётся поизвращаться, формула там что-то типа

ans = mul(pow(mul(pow(A1, B1 - 1), A2), N / B1), pow(A1, K + N % B1))

где A1 матрица для вычисления следующего слоя C-шек, а A2 та же матрица, только с прибавлением k-ой C-шки в ответ, а B1 = Bt.

Начальный вектор — (1, 0, 0, 0...) так как C00 = 1.

Итак, мы посчитали сумму C-шек, что есть количество ноликов в системе по базе B, если B простое. Остальные случаи:

  • B=10 считаем как для B=5
  • B=6 считаем как для B=3
  • B=9 считаем для B=3 по модулю MOD*2, применяем частный случай КТО чтобы поделить на 2 с остатком.
  • B=8 считаем для B=2 по модулю MOD*3, делим на 3
  • B=4 считаем для B=2 по модулю MOD*2

Чтобы понятней было про КТО, вот кусок кода:

if (B == 8) {
    long a = doIt(N, K, 2, MOD);
    long b = doIt(N, K, 2, 3);
    a = (a + MOD - b) % MOD;
        for (int s = 0; s < 3; s++)
            if ((a + s * MOD) % 3 == 0)
		return (int) ((a + s * MOD) / 3);
}
  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Авторское решение такое же, только вместо КТО можно было считать например для B=8 по модулю 3MOD и делить (просто div) в конце на 3.

    "B=10 считаем как для B=2" — видимо как B=5.

    А вообще там ещё один трюк был, который мы не стали использовать: матрица получается такая специфическая, что можно её за квадрат перемножать (соответственно для K по крайней мере вдвое больше спокойно работает).

    Кстати у Макото другое, более интересное, решение.

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

      Трюк? Да, понятно что там A[a][b] только от a-b зависит.

      И понятно что это подсчёт суммы C-шек для разных Bt можно объединить с возведением в степень, код упростится.

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

Может кто-нибудь объяснить решение medium-а одним циклом (за O(n))?