Hope you liked the problems!
How many operations are needed to make $$$a_i \le a_{i + 1}$$$ if initially, $$$a_i > a_{i + 1}$$$?
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
for (int i = 0; i < n - 1; i++) {
if (a[i] > a[i + 1]) {
ans = max(ans, a[i]);
}
}
cout << ans << nl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
}
Consider the case $$$n = 1$$$ separately.
Count the number of elements equal to $$$1$$$.
Find the sum of the array.
When there are a lot of elements equal to $$$1$$$ and the sum is not very big, the answer is no.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
ll sum_a = 0, cnt_1 = 0;
for (int x: a) {
sum_a += x;
if (x == 1) cnt_1++;
}
if (sum_a >= cnt_1 + n && n > 1) {
cout << "YES" << nl;
} else {
cout << "NO" << nl;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
}
Binary search on the answer.
Check if it is possible to have $$$\max(a_1,\ldots, a_n) \ge x$$$ for some $$$x$$$.
Fix some possible index that will be the position of the maximum in the final array.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
void solve() {
ll n, k;
cin >> n >> k;
vector<ll> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
ll lb = 0, ub = *max_element(all(a)) + k, ans = 0;
while (lb <= ub) {
ll tm = (lb + ub) / 2;
bool good = false;
for (int i = 0; i < n; i++) {
vector<ll> min_needed(n);
min_needed[i] = tm;
ll c_used = 0;
for (int j = i; j < n; j++) {
if (min_needed[j] <= a[j]) break;
if (j + 1 >= n) {
c_used = k + 1;
break;
}
c_used += min_needed[j] - a[j];
min_needed[j + 1] = max(0LL, min_needed[j] - 1);
}
if (c_used <= k) good = true;
}
if (good) {
ans = tm;
lb = tm + 1;
} else {
ub = tm - 1;
}
}
cout << ans << nl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) solve();
}
What can you say about index $$$j$$$ if the number of inversion in $$$[p_i, p_{i + 1}, \ldots, p_{j - 1}]$$$ is the same as in $$$[p_i, p_{i + 1}, \ldots, p_j]$$$?
Define a function to calculate $$$f(l, r)=$$$ the position of the maximum in $$$[p_l, p_{l + 1}, \ldots, p_{r}]$$$.
Divide and conquer.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
int query(int l, int r) {
if (l == r) return 0;
cout << "? " << l << ' ' << r << endl;
int res;
cin >> res;
return res;
}
// Finds max on p[l; r]
int solve(int l, int r) {
if (l == r) return l;
int m = (l + r) / 2;
int a = solve(l, m);
int b = solve(m + 1, r);
int r1, r2;
r1 = query(a, b - 1);
r2 = query(a, b);
if (r1 == r2) {
return b;
} else {
return a;
}
}
void solve() {
int n;
cin >> n;
int ans = solve(1, n);
cout << "! " << ans << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
}
1856E1 - ПерестановДерево (простая версия)
Fix the value of $$$\operatorname{lca}(u, v)$$$.
You can solve the problem independently for each value of $$$\operatorname{lca}(u, v)$$$.
Do dynamic programming.
For each subtree of $$$\operatorname{lca}(u, v)$$$, we only care about how many vertices are $$$>$$$ or $$$<$$$ less than $$$a_{\operatorname{lca}(u, v)}$$$.
This dynamic programming solution can actually be made to work in $$$\mathcal{O}(n^2)$$$.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 1000000;
vector<int> g[maxn];
int s[maxn];
ll ans = 0;
void dfs(int v, int p = -1) {
vector<ll> a;
s[v] = 1;
for (int u: g[v]) {
if (u == p) continue;
dfs(u, v);
s[v] += s[u];
a.push_back(s[u]);
}
vector<ll> dp(s[v]);
ll cs = 0;
for (int x: a) {
for (ll i = cs + x; i >= 0; i--) {
for (ll pr = min(cs, i); pr >= max(0LL, i - x); pr--) {
ll j = i - pr;
dp[i] = max(dp[i], dp[pr] + j * (cs - pr) + pr * (x - j));
}
}
cs += x;
}
ans += *max_element(all(dp));
dp.clear();
a.clear();
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
g[x - 1].push_back(i);
}
dfs(0);
cout << ans << nl;
}
1856E2 - ПерестановДерево (сложная версия)
Read hints for the easy version.
For each $$$\operatorname{lca}(u, v)$$$, we actually need to do subset sum on the subtree sizes.
If there is a very subtree that is bigger than the sum of the sizes of the other subtrees, you don't have to do subset sum.
Optimize subset sum to $$$\mathcal{O}(s \sqrt s)$$$, where s is the sum of the sizes of the subtrees for some fixed $$$\operatorname{lca}(u, v)$$$.
Use bitset to optimize subset sum even more.
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())
const char nl = '\n';
typedef long long ll;
typedef long double ld;
using namespace std;
const int maxn = 1000000;
vector<int> g[maxn];
int s[maxn];
ll ans = 0;
vector<ll> b;
ll closest;
template <int len = 1>
void subset_sum(int n) {
if (n >= len) {
subset_sum<std::min(len*2, maxn)>(n);
return;
}
bitset<len> dp;
dp[0] = 1;
for (ll x: b) {
dp = dp | (dp << x);
}
ll cv = n;
closest = 0;
for (int i = 0; i <= n; i++) {
if (dp[i] && abs(i - (n - i)) < cv) {
closest = i;
cv = abs(i - (n - i));
}
}
}
ll solve(vector<ll> &a) {
if (a.empty()) return 0;
sort(allr(a));
ll cs = 0;
for (ll x: a) cs += x;
if (a[0] * 2 >= cs) {
return a[0];
}
int n = gsize(a);
a.push_back(0);
b.clear();
int pi = 0;
for (int i = 1; i <= n; i++) {
if (a[i] != a[i - 1]) {
ll cnt = i - pi;
ll x = a[i - 1];
ll j = 1;
while (j < cnt) {
b.push_back(x * j);
cnt -= j;
j *= 2;
}
b.push_back(x * cnt);
pi = i;
}
}
subset_sum(cs);
return closest;
}
void dfs(int v, int p = -1) {
vector<ll> a;
s[v] = 1;
for (int u: g[v]) {
if (u == p) continue;
dfs(u, v);
s[v] += s[u];
a.push_back(s[u]);
}
ll x = solve(a);
ans += x * (s[v] - 1 - x);
a.clear();
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int x;
cin >> x;
g[x - 1].push_back(i);
}
dfs(0);
cout << ans << nl;
}
UPD: Tutorial for E1 has been added.
UPD2: Tutorial for E2 has been added.
