Hope you liked the problems! Tutorials for E1 and E2 will be added later (though there are hints).
How many operations are needed to make ai≤ai+1 if initially, ai>ai+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 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]) continue;
if (j + 1 >= n) {
c_used = k + 1;
break;
}
c_used += min_needed[j] - a[j];
min_needed[j + 1] = max(min_needed[j + 1], 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 - PermuTree (easy version)
Fix the value of \operatorname{lca}(u, v).
You can solve the problem independently for each value of \operatorname{lca}(u, v).
Do dp.
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 dp 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 - PermuTree (hard version)
Hi
#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;
}