My Editorial for Google Kick Start 2020 Round D

#	User	Rating
No items

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145

Problem A — Record Breaker

Implementation. Keep a record of the current maximum. Compare the current value to it, and also to the next number.

Time complexity is $$$O(N)$$$.

Code

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve(int case_num) {
    int n;
    read(n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
      read(a[i]);
    int ans = 0, hi = -1;
    for (int i = 0; i < n; ++i) {
      if (a[i] > hi && (i == n - 1 || a[i] > a[i + 1]))
        ans++;
      hi = max(hi, a[i]);
    }
    printf("Case #%d: %d\n", case_num, ans);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

Problem B — Alien Piano

Simple DP. Enumerate all choices of the last step and the current step.

Time complexity is $$$O(P^2K)$$$, where $$$P=4$$$ in this problem.

Code

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve(int case_num) {
    int n;
    read(n);
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
      read(a[i]);
    vector<vector<int>> dp(n, vector<int>(4, n));
    for (int k = 0; k < 4; ++k)
      dp[0][k] = 0;
    for (int i = 1; i < n; ++i) {
      for (int last = 0; last < 4; ++last)
        for (int now = 0; now < 4; ++now) {
          if (now == last) {
            if (a[i] == a[i - 1])
              dp[i][now] = min(dp[i][now], dp[i - 1][last]);
            else
              dp[i][now] = min(dp[i][now], dp[i - 1][last] + 1);
          } else if (now > last) {
            if (a[i] > a[i - 1])
              dp[i][now] = min(dp[i][now], dp[i - 1][last]);
            else
              dp[i][now] = min(dp[i][now], dp[i - 1][last] + 1);
          } else {
            if (a[i] < a[i - 1])
              dp[i][now] = min(dp[i][now], dp[i - 1][last]);
            else
              dp[i][now] = min(dp[i][now], dp[i - 1][last] + 1);
          }
        }
    }
    int ans = n;
    for (int k = 0; k < 4; ++k)
      ans = min(ans, dp[n - 1][k]);
    printf("Case #%d: %d\n", case_num, ans);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

Problem C — Beauty of Tree

Inclusion-exclusion, DFS.

We need to find, for every node, the number of descendants has a distance that can be divided by $$$A$$$, and similar for $$$B$$$. This can be done during DFS if we keep a record of the current path.

After having $$$ca[i]$$$ and $$$cb[i]$$$, we can simply calculate how many times the current node will be counted, via inclusion-exclusion:

$$$t[i]=(ca[i]+cb[i])\cdot N-ca[i]\cdot cb[i]$$$

Then we add up all the results and divide it by $$$N^2$$$.

The total time complexity is $$$O(N)$$$.

Code

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
  int n, a, b;
  vector<vector<int>> adj;
  vector<int> pa, pb, ac, bc;
  void dfs(int u, vector<int> &path) {
    int l = path.size();
    if (l >= a)
      pa[u] = path[l - a];
    if (l >= b)
      pb[u] = path[l - b];
    path.emplace_back(u);
    ac[u] = 1, bc[u] = 1;
    for (int v : adj[u])
      dfs(v, path);
    path.pop_back();
    if (pa[u] > 0)
      ac[pa[u]] += ac[u];
    if (pb[u] > 0)
      bc[pb[u]] += bc[u];
  }

public:
  void solve(int case_num) {
    read(n), read(a), read(b);
    adj = vector<vector<int>>(n + 1);
    for (int i = 2; i <= n; ++i) {
      int v;
      read(v);
      adj[v].emplace_back(i);
    }
    pa = vector<int>(n + 1);
    pb = vector<int>(n + 1);
    ac = vector<int>(n + 1);
    bc = vector<int>(n + 1);
    vector<int> path;
    dfs(1, path);
    double ans = 0;
    for (int i = 1; i <= n; ++i) {
      ans += (double)(ac[i] + bc[i]) * n;
      ans -= (double)ac[i] * bc[i];
    }
    printf("Case #%d: %.12f\n", case_num, ans / n / n);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

Problem D — Locked Doors

I used a rather complicated algorithm leveraging monotonic stack, sparse table and binary search.

For each door, calculate the first door to its left having higher difficulty, and the first door to its right having higher difficulty. For simplicity, a door with infinite difficulty is added at either end. This part is done by monotonic stack in $$$O(N)$$$.

Then construct a sparse table for range maximum query in $$$O(N\log N)$$$.

In each query, on the $$$K_i$$$-th day, there will be $$$K_i-1$$$ opened doors. Some are to the left of the $$$S_i$$$-th room, while some are to the right. If there are $$$l$$$ opened doors to the left on the $$$K_i$$$-th day, there needs to be at least $$$f(l)$$$ opened doors to the right, so that the highest difficulty among the $$$f(l)$$$ doors to the right is higher than the highest difficulty among the $$$l$$$ doors to the left. An observation is that $$$l+f(l)$$$ is monotonic. So the suitable $$$l$$$ can be found via binary search.

The last step is to determine whether we should use the leftmost room or the rightmost room. This can be done by comparing the highest difficulty of the doors to the left and those to the right. If the highest difficulty is to the left, then on the $$$K_i$$$-th day we must be in the leftmost room, otherwise rightmost.

The total time complexity is $$$O((N+Q)\log N)$$$.

Code

#include <cmath>
#include <cstdio>
#include <iostream>
#include <stack>
#include <vector>
#define INF 0x3f3f3f3f;
#define K 18

using namespace std;

template <typename T> void read(T &x) {
  x = 0;
  char c = getchar();
  T sig = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-')
      sig = -1;
  for (; isdigit(c); c = getchar())
    x = (x << 3) + (x << 1) + c - '0';
  x *= sig;
}

class Solution {
public:
  void solve(int case_num) {
    int n, q;
    read(n), read(q);
    vector<int> a(n + 1);
    for (int i = 1; i <= n - 1; ++i)
      read(a[i]);
    a[0] = INF;
    a[n] = INF;
    printf("Case #%d: ", case_num);
    vector<int> lf(n + 1, -1), rf(n + 1, n + 1);
    vector<vector<int>> sparse(n + 1, vector<int>(K));
    for (int i = 0; i <= n; ++i)
      sparse[i][0] = i;
    for (int k = 1; k < K; ++k) {
      for (int i = 0; i <= n; ++i) {
        sparse[i][k] = sparse[i][k - 1];
        int right = i + (1 << (k - 1));
        if (right <= n && a[sparse[right][k - 1]] > a[sparse[i][k]])
          sparse[i][k] = sparse[right][k - 1];
      }
    }
    auto query_sparse = [&](int l, int r) {
      if (l == r)
        return l;
      int len = r - l + 1;
      int half = trunc(log2(len - 1));
      int ans = sparse[l][half];
      if (a[sparse[r - (1 << half) + 1][half]] > a[ans])
        ans = sparse[r - (1 << half) + 1][half];
      return ans;
    };
    stack<int> st;
    for (int i = 0; i <= n; ++i) {
      while (!st.empty() && a[st.top()] < a[i]) {
        rf[st.top()] = i;
        st.pop();
      }
      st.push(i);
    }
    st = stack<int>();
    for (int i = n; i >= 0; --i) {
      while (!st.empty() && a[st.top()] < a[i]) {
        lf[st.top()] = i;
        st.pop();
      }
      st.push(i);
    }
    while (q--) {
      int s, k;
      read(s), read(k);

      auto output = [&](int ans) {
        printf("%d ", ans);
      };

      if (rf[s - 1] - (s - 1) > k - 1) {
        int ans = s + k - 1;
        if (ans > n)
          ans = n - k + 1;
        output(ans);
        continue;
      }
      if (s - lf[s] > k - 1) {
        int ans = s - k + 1;
        if (ans < 1)
          ans = k;
        output(ans);
        continue;
      }
      int l = 1, r = min(k - 2, s);
      while (l <= r) {
        int mid = (l + r) >> 1;
        int ma = query_sparse(s - mid, s - 1);
        int right = rf[ma];
        int tot = right - (s - mid);
        if (tot > k - 1)
          r = mid - 1;
        else
          l = mid + 1;
      }
      int lmost = s - r;
      int rmost = s - r + k - 2;
      int ans;
      if (rmost > n)
        ans = n - k + 1;
      else {
        int hi = query_sparse(lmost, rmost);
        if (hi >= s)
          ans = rmost + 1;
        else
          ans = lmost;
      }
      output(ans);
    }
    printf("\n");
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  read(t);
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}

Heltion's Cartesian tree solution.

Code

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr int maxn = 240000;
int D[maxn], S[maxn], L[maxn], R[maxn], H[maxn];
int RL[maxn], RR[maxn];
int SZ[maxn], F[maxn][20];
void DFS(int u){
    SZ[u] = u & 1;
	if(u & 1) RL[u] = RR[u] = (u + 1) / 2;
    for(int i = 1; i < 20; i += 1) F[u][i] = F[F[u][i - 1]][i - 1];
    if(~L[u]){
        F[L[u]][0] = u;
        DFS(L[u]);
        SZ[u] += SZ[L[u]];
		RL[u] = RL[L[u]];
    }
    if(~R[u]){
        F[R[u]][0] = u;
        DFS(R[u]);
        SZ[u] += SZ[R[u]];
		RR[u] = RR[R[u]];
    }
}
void work(){
    int N, Q;
    cin >> N >> Q;
    for(int i = 1; i < N; i += 1) cin >> D[i];
    for(int i = 1; i < 2 * N; i += 1){
        L[i] = R[i] = -1;
        if(i & 1) H[i] = 0;
        else H[i] = D[i / 2];
    }
    for(int i = 1, top = 0; i < 2 * N; i += 1){
        int k = top;
        while(k and H[S[k]] < H[i]) k -= 1;
        if(k) R[S[k]] = i;
        if(k < top) L[i] = S[k + 1];
        S[k += 1] = i;
        top = k;
    }
    int root = max_element(H + 1, H + 2 * N) - H;
    F[root][0] = 0;
    DFS(root);
    SZ[0] = INT_MAX;
	//for(int i = 1; i < 2 * N; i += 1) cout << i << " " << L[i] << " " << R[i] << "\n";
    for(int i = 0, S, K, X; i < Q; i += 1){
        cin >> S >> K;
        if(K == 1) cout << S << " ";
        else{
            X = S * 2 - 1;
            for(int j = 19; ~j; j -= 1) if(SZ[F[X][j]] < K) X = F[X][j];
			int L = RL[X], R = RR[X];
			//cout << "\nX = " << X << " " << L << " " << R << "\n";
			if(L == 1) cout << K;
			else if(R == N) cout << N - K + 1;
			else if(D[L - 1] > D[R]) cout << L + K - 1;
			else cout << R - K + 1;
			cout << " ";
        }
    }
    cout << "\n";
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    for(int t = 1; t <= T; t += 1){
        cout << "Case #" << t << ": ";
        work();
    }
    return 0;
}

Rev.	By	When	Δ	Comment
en6	lucifer1004	2020-07-15 11:18:36	19
en5	lucifer1004	2020-07-12 18:48:11	2	Tiny change: '<vector>\n\nusing na' -> '<vector>\nusing na'
en4	lucifer1004	2020-07-12 18:27:25	1364
en3	lucifer1004	2020-07-12 17:14:02	5	Tiny change: ' is that $f(l)$ is m' -> ' is that $l+f(l)$ is m'
en2	lucifer1004	2020-07-12 17:11:16	15397	Tiny change: '## Problem' -> '[Problems]()\n\n## Problem' (published)
en1	lucifer1004	2020-07-12 16:57:52	2925	Initial revision (saved to drafts)

Problem A — Record Breaker

Problem B — Alien Piano

Problem C — Beauty of Tree

Problem D — Locked Doors

History