We shall explain O(NH) solution by dynamic programming. Suppose that the elements are lined up in ascending order. Consider this operation: choose the leftmost element, and increase it to the old maximum or larger. We repeat this operation until all elements become H.

In the following figure, we chose A and inserted A between I and J. As depicted in this figure, between G and H, between H and I, and after J are also possible. Generally, If there are j maximum elements, there are j+1 places we can insert into. After inserting A, we next insert B into somewhere, and then C, D, E, F ... are followed.

f:id:pekempey:20190616000855p:plain

f:id:pekempey:20190616001139p:plain

Let dp[i][j] be the number of ways such that the maximum is equal to i and the number of maximum elements is equal to j. Initially,

\[ dp[0][N]=1. \]

As stated above,

\[ \mathrel{\mathbf{if}} j \ne N \mathrel{\mathbf{then}} dp[i][j+1] \mathrel{{+}{=}} dp[i][j]*(j+1). \]

Moreover, we may increase the leftmost element to the strictly larger than i. Thus,

\[ \mathrel{\mathbf{for}} k=1 \mathrel{\mathbf{to}} D \mathrel{\mathbf{do}} dp[i+k][1] \mathrel{{+}{=}} dp[i][j].\]

Finally, the answer is

\[ dp[H][N]. \]

Let us speed up this dp. Carefully viewing the releation, we can notice that

\[ \mathrel{\mathbf{for}} k=1 \mathrel{\mathbf{to}} D \mathrel{\mathbf{do}} dp[i+k][1] \mathrel{{+}{=}} dp[i][1] + dp[i][2] + \cdots + dp[i][N]. \]

Since \( dp[i][j] = j! * dp[i][1] \), we can restate it as follows.

\[ \mathrel{\mathbf{for}} k=1 \mathrel{\mathbf{to}} D \mathrel{\mathbf{do}} dp[i+k][1] \mathrel{{+}{=}} (1! + 2! + \cdots + N!)*dp[i][1]. \]

Thus, we can solve this problem in O(N+H) time.

https://atcoder.jp/contests/diverta2019-2/submissions/5931171

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
using namespace std;
using ll = long long;

const int MOD = 1000000007;

struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};

mint operator-(mint a) {
  return -a.n + MOD * (a.n != 0);
}
mint operator+(mint a, mint b) {
  int x = a.n + b.n;
  return x - (x >= MOD) * MOD;
}
mint operator-(mint a, mint b) {
  int x = a.n - b.n;
  return x + (x < 0) * MOD;
}
mint operator*(mint a, mint b) {
  return (long long)a.n * b.n % MOD;
}
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

void naive() {
  static mint dp[50][50];
  int N, H, D;
  cin >> N >> H >> D;
  dp[0][N] = 1;
  for (int i = 0; i <= H; i++) {
    for (int j = 0; j <= N; j++) {
      for (int k = i + 1; k <= min(H, i + D); k++) {
        dp[k][1] += dp[i][j];
      }
      if (j < N) {
        dp[i][j + 1] += dp[i][j] * (j + 1);
      }
    }
  }
  cout << dp[H][N] << endl;
}

int main() {
  int N, H, D;
  cin >> N >> H >> D;
  mint f = 1;
  mint s = 0;
  for (int i = 1; i <= N; i++) {
    f *= i;
    s += f;
  }
  vector<mint> dp(H + 2); // dp[i][1]
  dp[1] += 1;
  dp[D + 1] -= 1;
  for (int i = 1; i < H; i++) {
    dp[i + 1] += dp[i];
    int l = i + 1;
    int r = min(H + 1, i + D + 1);
    dp[l] += dp[i] * s;
    dp[r] -= dp[i] * s;
  }
  mint ans = dp[H] * f;
  cout << ans << '\n';
}

2019-06-10

Google Code Jam 2019 Round 3: Datacenter Duplex

Code Jam - Google’s Coding Competitions

Adding the edges without making any cycles as many as possible, we finally obtain the answer if the answer exists. We don't have to consider the order of adding edges. It is easy to imagine why this holds by checking some actual cases.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct unionfind {
  vector<int> A;
  int cnt;

  unionfind(int n) : A(n, -1), cnt(n) {}

  int find(int x) {
    if (A[x] < 0) return x;
    return A[x] = find(A[x]);
  }

  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (A[x] > A[y]) swap(x, y);
    A[x] += A[y];
    A[y] = x;
    cnt--;
    return true;
  }

  int size(int x) {
    return -A[find(x)];
  }
};

void solve() {
  int h, w;
  cin >> h >> w;
  vector<string> g(h);
  for (int i = 0; i < h; i++) {
    cin >> g[i];
  }
  auto f = [&](int i, int j) { return i * w + j; };
  unionfind uf(h * w);
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i + 1 < h && g[i][j] == g[i + 1][j]) uf.unite(f(i, j), f(i + 1, j));
      if (j + 1 < w && g[i][j] == g[i][j + 1]) uf.unite(f(i, j), f(i, j + 1));
    }
  }
  vector<string> ans(h - 1, string(w - 1, '.'));
  for (int i = 0; i < h - 1; i++) {
    for (int j = 0; j < w - 1; j++) {
      if (g[i][j] == g[i + 1][j + 1] && uf.unite(f(i, j), f(i + 1, j + 1))) {
        ans[i][j] = '\\';
      } else if (g[i][j + 1] == g[i + 1][j] && uf.unite(f(i, j + 1), f(i + 1, j)))  {
        ans[i][j] = '/';
      }
    }
  }
  if (uf.cnt != 2) {
    cout << "IMPOSSIBLE\n";
    return;
  }
  cout << "POSSIBLE\n";
  for (int i = 0; i < h - 1; i++) {
    cout << ans[i] << '\n';
  }
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int T;
  cin >> T;
  for (int i = 1; i <= T; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
}

2019-06-10

ABC129 E. Sum Equals Xor

https://atcoder.jp/contests/abc129/tasks/abc129_e

I solved it by digit DP with ordering monoid. In this DP, we scan the digits from the lowest to the highest as maintaining (order, carry). Iwarete mireba a+b=(a^b)+2*(a&b) kizuku beki.

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;

struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};

mint operator-(mint a) {
  return -a.n + MOD * (a.n != 0);
}
mint operator+(mint a, mint b) {
  int x = a.n + b.n;
  return x - (x >= MOD) * MOD;
}
mint operator-(mint a, mint b) {
  int x = a.n - b.n;
  return x + (x < 0) * MOD;
}
mint operator*(mint a, mint b) {
  return (long long)a.n * b.n % MOD;
}
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
istream &operator>>(istream &i, mint &a) { return i >> a.n; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

mint dp[100003][3][2]; // EQ, LT, GT

enum { EQ, LT, GT };

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  const int n = s.size();
  dp[n][EQ][0] = 1;
  for (int i = n - 1; i >= 0; i--) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 2; k++) {
        for (int x = 0; x < 2; x++) {
          for (int y = 0; y < 2; y++) {
            int v = x + y + k;
            int u = v % 2;
            if ((x ^ y) != v % 2) continue;
            int nj = j;
            if (s[i] - '0' < u) nj = GT;
            if (s[i] - '0' > u) nj = LT;
            dp[i][nj][v / 2] += dp[i + 1][j][k];
          }
        }
      }
    }
  }
  cout << dp[0][LT][0] + dp[0][EQ][0] << endl;
}

2019-06-08

Codeforces Round #564 (Div. 1) E. Nauuo and ODT

https://codeforces.com/contest/1172/problem/E

HL decomposition.
https://codeforces.com/contest/1172/submission/55290873

2019-06-04

Codeforces Round #230 (Div. 1) D. Three Arrays

https://codeforces.com/contest/392/problem/D

Let \(f_A(k)\) be the minimum i such that \(A_i=k\). If there doesn't exist such a index, we define \(f_A(k) = \infty\). \(f_B(k)\) and \(f_C(k)\) are similarly defined. Then, we want to obtain this.

\begin{align}
\min \left\{ x + y + z \;\middle|\; \bigwedge_{k} x \ge f_A(k) \vee y \ge f_B(k) \vee z \ge f_C(k) \right\}
\end{align}

Fix x, then possible (y,z) are in the following area. This is like stairs.