Codeforces Round #572 (Div. 1) C. Array Beauty
https://codeforces.com/contest/1188/problem/C
Suppose that the array is already sorted. Let f(x) be the number of subarrays such that any difference between adjacent elements is greater than or equal to x. We then have the answer as f(1)+f(2)+f(3)+....
Since it takes O(NK) to calculate f(x), we may think the total complexity become O(NK max A). However, actually, we only have to calculate upto f(N/K), so the true time complexity is O(NK max A / K), that is O(N max A). It is fast enough.
Educational Codeforces Round 67 F. Expected Square Beauty
https://codeforces.com/contest/1187/problem/F
\documentclass[margin=2mm]{standalone} \usepackage{amsmath,amssymb,bussproofs} \begin{document} %\begin{prooftree} \AxiomC{\(N^2\)} \UnaryInfC{\(E[N^2]\)} \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}]\)} \UnaryInfC{\(\displaystyle \sum_{i}E[X_i]\)} \RightLabel{Linearity of Expecation} \UnaryInfC{\(\displaystyle E\left[\sum_{i}X_i\right]\)} \RightLabel{\(({}* -2N)\) Introduction} \UnaryInfC{\(\displaystyle -2NE\left[\sum_{i}X_i\right]\)} \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}]\)} \UnaryInfC{\(\displaystyle E\left[\sum_{i}X_i^2\right] \)} \AxiomC{\(\displaystyle \sum_{i} \Pr[x_i=x_{i+1}=x_{i+2}] \)} \UnaryInfC{\(\displaystyle E\left[\sum_{i} X_i X_{i+1} \right]\)} \AxiomC{\([i+2 \le j]^{(1)}\)} \AxiomC{\(\displaystyle \Pr[x_i=x_{i+1}] \Pr[x_j=x_{j+1}] \)} \BinaryInfC{\(\displaystyle \Pr[x_i=x_{i+1} \land x_j=x_{j+1}] \)} \UnaryInfC{\(\displaystyle E[X_iX_j]\)} \RightLabel{\(\Sigma\) Introduction (1)} \UnaryInfC{\(\displaystyle \sum_{i+2 \le j} E[X_i X_j] \)} \RightLabel{Linearity of Expection} \UnaryInfC{\(\displaystyle E\left[\sum_{i+2 \le j} X_i X_j\right]\)} \BinaryInfC{\(\displaystyle E\left[\sum_{i<j}X_i X_j\right]\)} \RightLabel{\(({}*2)\) Introduction } \UnaryInfC{\(\displaystyle 2E\left[\sum_{i<j} X_i X_j\right] \)} \BinaryInfC{\(\displaystyle E\left[\sum_{i}X_i^2 + 2 p\sum_{i<j} X_i X_j\right] \)} \UnaryInfC{\(\displaystyle E\left[\left(\sum_{i}X_i\right)^2\right]\)} \RightLabel{Linearity of Expectation} \TrinaryInfC{\(\displaystyle E\left[\left(N-\sum_{i}X_i\right)^2\right] \)} \RightLabel{Let \(X_i\) be the indicator variable of \(x_i=x_{i+1}\). } \UnaryInfC{\(\displaystyle E[(N-X)^2] \)} \RightLabel{Let \(X\) be the number of \(i\) such that \(x_i=x_{i+1}\).} \UnaryInfC{answer} \DisplayProof %\end{prooftree} \end{document}
AtCoder Beginner Contest F. Small Products
https://atcoder.jp/contests/abc132/tasks/abc132_f
We have
\[ k \le \left\lfloor \frac{N}{i} \right\rfloor \iff i * k \le N \iff i \le \left\lfloor \frac{N}{k} \right\rfloor. \]
\[ \underbrace{\left\lfloor \frac{N}{1} \right\rfloor, \left\lfloor \frac{N}{2} \right\rfloor , \ldots , \left\lfloor \frac{N}{\left\lfloor \frac{N}{K} \right\rfloor - 1} \right\rfloor, \left\lfloor \frac{N}{\left\lfloor \frac{N}{K} \right\rfloor}\right\rfloor}_{{}\ge K} , \underbrace{\left\lfloor \frac{N}{\left\lfloor \frac{N}{K} \right\rfloor + 1} \right\rfloor, \left\lfloor \frac{N}{\left\lfloor \frac{N}{K} \right\rfloor + 2}\right\rfloor , \ldots, \left\lfloor \frac{N}{N-1} \right\rfloor, \left\lfloor \frac{N}{N} \right\rfloor}_{{}\lt K} \]
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) 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; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N, K; cin >> N >> K; vector<int> val; for (int i = 1; i * i <= N; i++) { val.push_back(i); if (i != N / i) { val.push_back(N / i); } } sort(val.rbegin(), val.rend()); vector<int> bar; for (int v : val) bar.push_back(N / (v + 1) + 1); bar.push_back(N+1); const int m = bar.size() - 1; vector<mint> dp0(m+1); dp0[0] = 1; rep(i, K) { vector<mint> dp1(m+1); rep(j, m) { dp1[0] += dp0[j]; dp1[m - j] -= dp0[j]; } rep(j, m) { dp1[j+1] += dp1[j]; dp1[j] *= bar[j+1]-bar[j]; } dp0 = dp1; } mint ans = 0; rep(j, m) { ans += dp0[j]; } cout << ans << endl; }
Codeforces Round #567 (Div. 2) E2. A Story of One Country (Hard)
https://codeforces.com/contest/1181/problem/E2T(n) = T(x) + T(n - x) + min(x, n - x) = O(n log n)
The solution is based on the following fact:
Analysis: Looking at one specific element, when the element moves to the smaller group, it takes a time. These events happen log n times. Hence, the time complexity must be O(n log n).
// Time complexity: O(n log^2 n) #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--) using namespace std; using ll = long long; template<class T> using minset = set<T, less<T>>; template<class T> using maxset = set<T, greater<T>>; int X1[100000], Y1[100000], X2[100000], Y2[100000]; struct mao { minset<pair<int, int>> rightward; maxset<pair<int, int>> leftward; minset<pair<int, int>> upward; maxset<pair<int, int>> downward; void insert(int id) { rightward.emplace(X1[id], id); leftward.emplace(X2[id], id); upward.emplace(Y1[id], id); downward.emplace(Y2[id], id); } void erase(int id) { rightward.erase({X1[id], id}); leftward.erase({X2[id], id}); upward.erase({Y1[id], id}); downward.erase({Y2[id], id}); } }; template<class T> vector<int> indices(T it, int k) { vector<int> res; for (int i = 0; i < k; i++) { res.push_back(it->second); it++; } return res; } bool f(mao &m) { const int n = m.rightward.size(); if (n <= 1) return true; auto r = m.rightward.begin(); auto l = m.leftward.begin(); auto u = m.upward.begin(); auto d = m.downward.begin(); vector<int> v; int maxr = -1e9; int minl = 1e9; int maxu = -1e9; int mind = 1e9; for (int i = 0; i + 1 < n; i++, r++, l++, u++, d++) { maxr = max(maxr, X2[r->second]); minl = min(minl, X1[l->second]); maxu = max(maxu, Y2[u->second]); mind = min(mind, Y1[d->second]); auto rr = next(r); auto ll = next(l); auto uu = next(u); auto dd = next(d); if (maxr <= X1[rr->second]) { v = indices(m.rightward.begin(), i + 1); break; } if (minl >= X2[ll->second]) { v = indices(m.leftward.begin(), i + 1); break; } if (maxu <= Y1[uu->second]) { v = indices(m.upward.begin(), i + 1); break; } if (mind >= Y2[dd->second]) { v = indices(m.downward.begin(), i + 1); break; } } if (!v.empty()) { mao mm; for (int i : v) { m.erase(i); mm.insert(i); } return f(m) && f(mm); } return false; } int main() { int n; cin >> n; mao m; rep(i, n) { cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i]; m.insert(i); } cout << (f(m) ? "YES" : "NO") << '\n'; } struct init { init() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } init;
SRM 761 500pts. SortArray
From 0-1 sorting lemma, we have an algorithm.
#include <bits/stdc++.h> using namespace std; struct SortArray { vector<int> verify(int N, vector<int> commands) { for (int i = 0; i < 1 << N; i++) { vector<int> a(N); for (int j = 0; j < N; j++) { a[j] = i >> j & 1; } for (int x : commands) { int c = 0; for (int j = 0; j < N; j++) { if (x >> j & 1) { c += !a[j]; } } for (int j = 0; j < N; j++) { if (x >> j & 1) { if (c > 0) { a[j] = 0; c--; } else { a[j] = 1; } } } } if (!is_sorted(a.begin(), a.end())) { int l = 0; int r = N - 1; vector<int> ans; for (int j = 0; j < N; j++) { if (~i >> j & 1) { ans.push_back(l++); } else { ans.push_back(r--); } } return ans; } } return {}; } };
