Thanks for participation!
Idea: zltzlt
Hint 1
By observing the example, we can see that there is no solution when $$$n$$$ is even.
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
int main() {
int T, n;
cin >> T;
while (T--) {
cin >> n;
if (n & 1) {
cout << n << ' ';
for (int i = 1; i < n; ++i) {
cout << i << " \n"[i == n - 1];
}
} else {
cout << "-1\n";
}
}
return 0;
}
Idea: zltzlt
Hint 1
Consider the position of the minimum value after rearranging the sequence.
Hint 2
What kind of numbers should be placed on the $$$\min$$$ side, and what kind should be placed on the $$$\gcd$$$ side?
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T, n;
cin >> T;
while (T--) {
cin >> n;
vector<ll> a(n);
for (ll &x : a) {
cin >> x;
}
int p = min_element(a.begin(), a.end()) - a.begin();
ll g = 0;
for (int i = 0; i < n; ++i) {
if (i != p && a[i] % a[p] == 0) {
g = __gcd(g, a[i]);
}
}
cout << (g == a[p] ? "Yes\n" : "No\n");
}
return 0;
}
2084C - You Soared Afar With Grace
Idea: CharlieV
Hint 1
Will the $$$b_i$$$ corresponding to a given $$$a_i$$$ change?
Hint 2
Individually place each pair corresponding to $$$(a_i, b_i)$$$ (i.e., $$$(b_i, a_i)$$$) at position $$$n - i + 1$$$.
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200100;
int n, a[maxn], b[maxn], m, p[maxn], ans[maxn][2];
inline void work(int x, int y) {
if (x == y) {
return;
}
ans[++m][0] = x;
ans[m][1] = y;
swap(a[x], a[y]);
swap(p[a[x]], p[a[y]]);
swap(b[x], b[y]);
}
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
p[a[i]] = i;
}
for (int i = 1; i <= n; ++i) {
cin >> b[i];
}
m = 0;
int x = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] == b[i]) {
if (n % 2 == 0 || x) {
cout << "-1\n";
return;
}
x = i;
} else if (b[p[b[i]]] != a[i]) {
cout << "-1\n";
return;
}
}
if (n & 1) {
work(x, (n + 1) / 2);
}
for (int i = 1; i <= n / 2; ++i) {
work(p[b[i]], n - i + 1);
}
cout << m << '\n';
for (int i = 1; i <= m; ++i) {
cout << ans[i][0] << ' ' << ans[i][1] << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
2084D - Arcology On Permafrost
Idea: zltzlt
Hint 1
Treat "at most $$$m$$$ operations" as "exactly $$$m$$$ operations".
Hint 2
What is the maximum value of $$$f(a)$$$?
Hint 3
Ensure that the distance between each pair of identical numbers is at least $$$k$$$.
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n, m, k;
cin >> n >> m >> k;
for (int i = 0; i < n; ++i) {
cout << i % (n < (m + 1) * k ? k : n / (m + 1)) << " \n"[i == n - 1];
}
}
return 0;
}
Idea: zltzlt
Hint 1
Transform the calculation method of $$$\operatorname{mex}$$$.
Hint 2
Try to come up with an $$$O(n^3)$$$ approach and then optimize it to $$$O(n^2)$$$.
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5050;
const int mod = 1000000007;
int n, a[maxn], fac[maxn], C[maxn][maxn], b[maxn], d[maxn][maxn];
bool vis[maxn];
void solve() {
cin >> n;
for (int i = 0; i <= n; ++i) {
vis[i] = 0;
for (int j = 0; j <= n; ++j) {
d[i][j] = 0;
}
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
fac[i] = 1LL * fac[i - 1] * i % mod;
b[i] = b[i - 1] + (a[i] == -1);
if (a[i] != -1) {
vis[a[i]] = 1;
}
}
for (int i = 0; i <= n; ++i) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
}
int mn1 = n;
for (int i = 1; i <= n; ++i) {
int mn2 = n;
for (int j = n; j >= i; --j) {
int x = b[j] - b[i - 1], y = min(mn1, mn2);
++d[x][0];
--d[x][y];
if (a[j] != -1) {
mn2 = min(mn2, a[j]);
}
}
if (a[i] != -1) {
mn1 = min(mn1, a[i]);
}
}
for (int i = 0; i <= b[n]; ++i) {
for (int j = 1; j <= n; ++j) {
d[i][j] += d[i][j - 1];
}
}
int ans = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
cnt += (!vis[i]);
for (int j = cnt; j <= b[n]; ++j) {
ans = (ans + 1LL * C[j][cnt] * fac[cnt] % mod * fac[b[n] - cnt] % mod * d[j][i]) % mod;
}
}
cout << ans << '\n';
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Idea: zltzlt
Developer: 244mhq
Hint 1
What kind of permutation $$$b$$$ is good?
Hint 2
Consider transforming this problem into a classic greedy algorithm problem.
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500100;
int n, a[maxn], b[maxn], c[maxn], p[maxn], q[maxn];
struct node {
int r, x;
node(int a = 0, int b = 0) : r(a), x(b) {}
};
inline bool operator < (const node &a, const node &b) {
return a.r > b.r || (a.r == b.r && a.x > b.x);
}
vector<node> vc[maxn];
struct DS1 {
int c[maxn];
inline void init() {
for (int i = 0; i <= n; ++i) {
c[i] = 0;
}
}
inline void update(int x, int d) {
for (int i = x; i <= n; i += (i & (-i))) {
c[i] = max(c[i], d);
}
}
inline int query(int x) {
int res = 0;
for (int i = x; i; i -= (i & (-i))) {
res = max(res, c[i]);
}
return res;
}
} T1;
struct DS2 {
int c[maxn];
inline void init() {
for (int i = 0; i <= n; ++i) {
c[i] = n + 1;
}
}
inline void update(int x, int d) {
for (int i = x; i; i -= (i & (-i))) {
c[i] = min(c[i], d);
}
}
inline int query(int x) {
int res = n + 1;
for (int i = x; i <= n; i += (i & (-i))) {
res = min(res, c[i]);
}
return res;
}
} T2;
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
p[a[i]] = i;
q[i] = 0;
vector<node>().swap(vc[i]);
}
for (int i = 1; i <= n; ++i) {
cin >> b[i];
if (b[i]) {
q[b[i]] = i;
}
}
T1.init();
for (int i = 1; i <= n; ++i) {
if (q[i]) {
if (T1.query(p[i]) > q[i]) {
cout << "-1\n";
return;
}
T1.update(p[i], q[i]);
}
}
T1.init();
T2.init();
for (int i = 1; i <= n; ++i) {
if (q[a[i]]) {
T1.update(a[i], q[a[i]]);
} else {
c[i] = T1.query(a[i]) + 1;
}
}
for (int i = n; i; --i) {
if (q[a[i]]) {
T2.update(a[i], q[a[i]]);
} else {
int r = T2.query(a[i]) - 1;
if (c[i] > r) {
cout << "-1\n";
return;
}
vc[c[i]].emplace_back(r, a[i]);
}
}
priority_queue<node> pq;
for (int i = 1; i <= n; ++i) {
for (node u : vc[i]) {
pq.push(u);
}
if (!b[i]) {
if (pq.empty() || pq.top().r < i) {
cout << "-1\n";
return;
}
b[i] = pq.top().x;
pq.pop();
}
}
for (int i = 1; i <= n; ++i) {
cout << b[i] << " \n"[i == n];
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
2084G1 - Wish Upon a Satellite (Easy Version)
Idea: zltzlt
Hint 1
What is the value of $$$f(c)$$$?
Hint 2
Try DP.
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1, -1);
vector< vector<ll> > f(n + 1, vector<ll>(n + 1, 1e18));
for (int i = 1, x; i <= n; ++i) {
cin >> x;
if (x) {
a[x] = i & 1;
}
}
if (a[1] != 1) {
f[1][0] = 0;
}
if (a[1] != 0) {
f[1][1] = 0;
}
for (int i = 1; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
f[i][j] += j * (n / 2 - (i - j)) + (i - j) * ((n + 1) / 2 - j);
if (a[i + 1] != 1) {
f[i + 1][j] = min(f[i + 1][j], f[i][j]);
}
if (a[i + 1] != 0) {
f[i + 1][j + 1] = min(f[i + 1][j + 1], f[i][j]);
}
}
}
ll ans = -f[n][(n + 1) / 2];
for (int i = 1; i <= n; ++i) {
ans += i * i;
}
cout << ans << '\n';
}
int main() {
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
2084G2 - Wish Upon a Satellite (Hard Version)
Idea: zltzlt
Hint 1
Optimize the DP in G1.
Solution
Tutorial is loading...
Implementation
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 500100;
int n, a[maxn];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int p[maxn], nt, ls[maxn], rs[maxn], sz[maxn];
bool vis[maxn];
struct vec {
ll a0, a1, a2;
vec(ll a = 0, ll b = 0, ll c = 0) : a0(a), a1(b), a2(c) {}
} val[maxn];
struct mat {
ll a00, a01, a02, a10, a11, a12, a20, a21, a22;
mat(ll a = 0, ll b = 0, ll c = 0, ll d = 0, ll e = 0, ll f = 0, ll g = 0, ll h = 0, ll i = 0) : a00(a), a01(b), a02(c), a10(d), a11(e), a12(f), a20(g), a21(h), a22(i) {}
} I, tag[maxn];
inline vec operator * (const vec &a, const mat &b) {
vec res;
res.a0 = a.a0 * b.a00 + a.a1 * b.a10 + a.a2 * b.a20;
res.a1 = a.a0 * b.a01 + a.a1 * b.a11 + a.a2 * b.a21;
res.a2 = a.a0 * b.a02 + a.a1 * b.a12 + a.a2 * b.a22;
return res;
}
inline mat operator * (const mat &a, const mat &b) {
mat res;
res.a00 = a.a00 * b.a00 + a.a01 * b.a10 + a.a02 * b.a20;
res.a01 = a.a00 * b.a01 + a.a01 * b.a11 + a.a02 * b.a21;
res.a02 = a.a00 * b.a02 + a.a01 * b.a12 + a.a02 * b.a22;
res.a10 = a.a10 * b.a00 + a.a11 * b.a10 + a.a12 * b.a20;
res.a11 = a.a10 * b.a01 + a.a11 * b.a11 + a.a12 * b.a21;
res.a12 = a.a10 * b.a02 + a.a11 * b.a12 + a.a12 * b.a22;
res.a20 = a.a20 * b.a00 + a.a21 * b.a10 + a.a22 * b.a20;
res.a21 = a.a20 * b.a01 + a.a21 * b.a11 + a.a22 * b.a21;
res.a22 = a.a20 * b.a02 + a.a21 * b.a12 + a.a22 * b.a22;
return res;
}
inline void init() {
for (int i = 0; i <= nt; ++i) {
p[i] = ls[i] = rs[i] = sz[i] = 0;
val[i] = vec();
tag[i] = I;
vis[i] = 0;
}
nt = 0;
}
inline int newnode(ll x, ll y) {
int u = ++nt;
p[u] = rnd();
ls[u] = rs[u] = 0;
sz[u] = 1;
val[u] = vec(x, y, 1);
tag[u] = I;
vis[u] = 0;
return u;
}
inline void pushup(int x) {
sz[x] = sz[ls[x]] + sz[rs[x]] + 1;
}
inline void pushtag(int x, const mat &y) {
if (!x) {
return;
}
val[x] = val[x] * y;
tag[x] = tag[x] * y;
vis[x] = 1;
}
inline void pushdown(int x) {
if (!vis[x]) {
return;
}
pushtag(ls[x], tag[x]);
pushtag(rs[x], tag[x]);
vis[x] = 0;
tag[x] = I;
}
void split(int u, int &x, int &y) {
if (!u) {
x = y = 0;
return;
}
pushdown(u);
if (val[u].a0 < 0) {
x = u;
split(rs[u], rs[u], y);
} else {
y = u;
split(ls[u], x, ls[u]);
}
pushup(u);
}
int merge(int x, int y) {
if (!x || !y) {
return x | y;
}
pushdown(x);
pushdown(y);
if (p[x] < p[y]) {
rs[x] = merge(rs[x], y);
pushup(x);
return x;
} else {
ls[y] = merge(x, ls[y]);
pushup(y);
return y;
}
}
ll f[maxn], tot;
void dfs(int u) {
if (!u) {
return;
}
pushdown(u);
dfs(ls[u]);
f[++tot] = val[u].a0;
dfs(rs[u]);
}
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i) {
a[i] = -1;
}
for (int i = 1, x; i <= n; ++i) {
cin >> x;
if (x) {
a[x] = (i & 1);
}
}
init();
int rt = 0;
ll l = 0, r = 0, x = 0;
if (a[1] == 1) {
l = r = 1;
} else if (a[1] == -1) {
rt = newnode(0, 1);
r = 1;
}
for (ll i = 1; i < n; ++i) {
x += l * l * 2 + (-i - i - (n & 1)) * l + i * ((n + 1) / 2);
pushtag(rt, mat(1, 0, 0, 4, 1, 0, -i - i - (n & 1) - 2, 0, 1));
if (a[i + 1] == 1) {
pushtag(rt, mat(1, 0, 0, 0, 1, 0, 0, 1, 1));
++l;
++r;
} else if (a[i + 1] == -1) {
int u, v;
split(rt, u, v);
pushtag(v, mat(1, 0, 0, 0, 1, 0, 0, 1, 1));
rt = merge(merge(u, newnode(0, l + 1 + sz[u])), v);
++r;
}
}
tot = 0;
dfs(rt);
ll ans = -x;
for (int i = 1; i <= (n + 1) / 2 - l; ++i) {
ans -= f[i];
}
for (ll i = 1; i <= n; ++i) {
ans += i * i;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
I.a00 = I.a11 = I.a22 = 1;
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Idea: zltzlt
Developer: StarSilk
Hint 1
Extract the longest contiguous segments in $$$s$$$ where the values remain the same.
Hint 2
According to greedy matching, an $$$O(n^2)$$$ DP can be obtained.
Hint 3
Optimize the DP from $$$O(n^2)$$$ to $$$O(n)$$$.
Solution
Tutorial is loading...
Implementation 1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2000100;
const ll mod = 1000000007;
int n, a[maxn], m, nxt[maxn], stk[maxn], top;
ll f[maxn], d[maxn];
char s[maxn];
inline ll calc() {
top = 0;
for (int i = m; i >= 1; i -= 2) {
while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
--top;
}
nxt[i] = stk[top];
stk[++top] = i;
}
top = 0;
for (int i = m - 1; i >= 1; i -= 2) {
while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
--top;
}
nxt[i] = stk[top];
stk[++top] = i;
}
for (int i = 1; i < m; ++i) {
f[i] = d[i] = 0;
}
f[1] = a[1];
for (int i = 3; i < m; i += 2) {
f[i] = 1;
}
ll ans = 0;
for (int i = 1; i < m; ++i) {
if (i >= 3) {
d[i] = (d[i] + d[i - 2]) % mod;
}
f[i] = (f[i] + d[i]) % mod;
int j = i + 1, x = 0;
while (j < m) {
int k = (nxt[j] ? nxt[j] : m);
f[j] = (f[j] + f[i] * (a[j] - x)) % mod;
x = a[j] + (k - j) / 2 - 1;
d[j + 2] = (d[j + 2] + f[i]) % mod;
d[k] = (d[k] - f[i] + mod) % mod;
j = k;
}
if ((m - i) & 1) {
ans = (ans + f[i]) % mod;
}
}
return ans * a[m] % mod;
}
void solve() {
cin >> n >> s;
m = 0;
for (int i = 0, j = 0; i < n; i = (++j)) {
while (j + 1 < n && s[j + 1] == s[i]) {
++j;
}
a[++m] = j - i + 1;
}
if (m == 1) {
cout << n - 1 << '\n';
return;
}
if (m == 2) {
cout << 1LL * a[1] * a[2] % mod << '\n';
return;
}
ll ans = calc();
--m;
for (int i = 1; i <= m; ++i) {
a[i] = a[i + 1];
}
a[1] = 1;
ans = (ans + calc()) % mod;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
Implementation 2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2000100;
const ll mod = 1000000007;
int n, a[maxn], m, nxt[maxn], stk[maxn], top;
ll f[maxn], g[maxn], d[maxn];
char s[maxn];
inline ll calc() {
top = 0;
for (int i = m; i >= 1; i -= 2) {
while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
--top;
}
nxt[i] = stk[top];
stk[++top] = i;
}
top = 0;
for (int i = m - 1; i >= 1; i -= 2) {
while (top && a[stk[top]] - stk[top] / 2 < a[i] - i / 2) {
--top;
}
nxt[i] = stk[top];
stk[++top] = i;
}
for (int i = 1; i < m; ++i) {
f[i] = g[i] = d[i] = 0;
}
f[1] = a[1];
for (int i = 3; i < m; i += 2) {
f[i] = 1;
}
ll ans = 0;
for (int i = 1; i < m; ++i) {
if (i >= 3) {
d[i] = (d[i] + d[i - 2]) % mod;
}
f[i] = (f[i] + d[i]) % mod;
g[i + 1] = (g[i + 1] + f[i]) % mod;
f[i + 1] = (f[i + 1] + f[i] * a[i + 1]) % mod;
d[i + 2] = (d[i + 2] + g[i]) % mod;
if (nxt[i]) {
g[nxt[i]] = (g[nxt[i]] + g[i]) % mod;
f[nxt[i]] = (f[nxt[i]] + g[i] * (a[nxt[i]] - a[i] - (nxt[i] - i) / 2 + 1)) % mod;
d[nxt[i]] = (d[nxt[i]] - g[i] + mod) % mod;
}
if ((m - i) & 1) {
ans = (ans + f[i]) % mod;
}
}
return ans * a[m] % mod;
}
void solve() {
cin >> n >> s;
m = 0;
for (int i = 0, j = 0; i < n; i = (++j)) {
while (j + 1 < n && s[j + 1] == s[i]) {
++j;
}
a[++m] = j - i + 1;
}
if (m == 1) {
cout << n - 1 << '\n';
return;
}
if (m == 2) {
cout << 1LL * a[1] * a[2] % mod << '\n';
return;
}
ll ans = calc();
--m;
for (int i = 1; i <= m; ++i) {
a[i] = a[i + 1];
}
a[1] = 1;
ans = (ans + calc()) % mod;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--) {
solve();
}
return 0;
}
for C I created a graph for the target positions of each index and then ran a dfs. There will be a cycles and we need size — 1 steps to reach out target and graph building got me a WA :(((
you don't need to put the pairs such that a[i] = i in the end. You just need to ensure in the end that if some pair (a[i], b[i]) exists, that (a[j], b[j]) = (b[i], a[i]) exists for some other j as well. You can place them at ANY symmetric positions about the middle.
for C I swap and pray, after swapping I check one last time if all match -> YES/NO.
And it works like a charm.
So
solution by swapping each? Or did you do additional check first whether it's possible or not?
my sol is at most n//2 operations, overall is O(n).
I marked the number position then swap it... idk how you can do O(n^2)?
a piece of advice: Think more deeply and plan thoroughly before you start writing.
so quick tho
The Penalties got us fr , could've avoided so much of penalty this contest!!
The checker message
Jury has the better answer: jans = 2, pans = 0helped me figure out that I need to find $$$f(a)$$$ to solve D lmaoThe Permutation Contest
Difficulty gap from D to E is ridiculous
As a specialist, all I do after ABCD is stair at the ceiling after done reading the problems.
As a specialist I have never read E in div2 contest within contest
As a specialist, I was not able to do D itself :(
but, you aren't a specialist
As a specialist, i have rarely done D in div2
As an Expert : I saw only $$$250$$$ AC in $$$(Div$$$ $$$1+2)$$$, Took that as a sign from the universe to brew a cup of coffee :D
As a International Grandmaster, I solve ABCD within 30 mins and then stuck in E for almost 2 hours.
As a pupil,I almost died when implementing E before dawn.
C messed up the whole contest, but D was saver
D messed up the whole contest, but E was saver
can you explain your solution for problem E.
Update: Thank You for the well explained solution.
Firstly, you need to do some transformations of the statement.
Define $$$mex(a)$$$ as the number of $$$k$$$'s such that every number in the range $$$[0, k]$$$ is present in $$$a$$$. This number actually equals to $$$mex$$$, because by the definition, all numbers from $$$0$$$ to $$$mex - 1$$$ are present and $$$mex$$$ is not present.
Also, let's count the contribution of each subarray independently. Now, you can sum up the contributions of each $$$k$$$ separately. For this purpose, you can brute force the value of $$$k$$$. It is possible to make all integers from $$$0$$$ to $$$k$$$ appear in the subarray if the subarray contains all the fixed positions where $$$a_i \le k$$$, because if this doesn't satisfy, i.e. there's a value $$$\le k$$$ in the whole array, but not in the subarray, then you should repeat that value $$$2$$$ times to make this value appear in the subarray.
Now, let's keep track of the minimum/maximum position of a fixed element that is $$$\le k$$$, let's denote them as $$$[lx, rx]$$$ correspondingly. Then, for the subarray $$$[l, r]$$$ to have a positive contribution, it should contain the segment $$$[lx, rx]$$$.
To calculate the contribution of segment $$$[l, r]$$$, let's denote $$$cnt$$$ as the number of elements that are $$$-1$$$ in the current segment, and let's denote $$$miss$$$ as the number of elements in the array that are $$$-1$$$, and let's denote $$$x$$$ as the number of elements that are $$$\le k$$$ that aren't present in the array. The contribution becomes $$$P(cnt, x) * (miss - x)!$$$ . This is because you must insert those $$$x$$$ missing elements $$$\le k$$$ in the subarray to make all of them appear, and you can insert them in any order and in any position that is $$$-1$$$ in the subarray, so the number of such arrangements is $$$C(cnt, x) * x!$$$, or $$$P(cnt, x)$$$. And all other $$$miss - x$$$ elements can be inserted arbitarily into $$$-1$$$ positions, so the number of those arrangements is $$$(miss - x)!$$$ . Together, the number of ways equals to $$$P(cnt, x) * (miss - x)!$$$ .
To calculate this value fast, you need to fix the $$$cnt$$$, because $$$miss$$$ and $$$x$$$ are the same for all the subarrays. For each $$$cnt$$$, you should save the number of segments that contain $$$[lx, rx]$$$ and have the number of missing elements equal to $$$cnt$$$. Now you can notice that the number of $$$[lx, rx]$$$s for which the answer should be calculated equal to $$$n$$$, $$$k$$$ can take the maximum value of $$$n - 1$$$, so you can fix $$$cnt$$$ for each of those segments independently.
Let's iterate $$$rx$$$-s in decreasing order and add segments which have $$$r \ge rx$$$ and take a fenwick tree for each $$$cnt$$$. For each of those segments $$$[l, r]$$$, you need to add $$$1$$$ to the $$$l$$$-th position of the $$$cnt$$$'th fenwick tree. Now, the number of segments that contain $$$[lx, rx]$$$ and have the number of missing elements equal to $$$cnt$$$ is given by the $$$sum(1, lx)$$$ in the $$$cnt$$$-th fenwick tree. Basically, among segments with $$$r \ge rx$$$, you calculate the number of those with $$$l \le lx$$$. For more implementation details, you can look at my code.
Problem C is really interesting. Thanks for the round and very fast editorial
A little typo: in problem B, time complexity for finding the gcd of $$$n$$$ numbers is $$$\Theta(n+\log a)$$$ instead of $$$\Theta (n\log a)$$$.
To be fair, the complexity could depend on which gcd implementation you use.
Example: https://codeforces.me/blog/entry/137056
Literally there is no graph , dp , binary search , greedy , etc... in A-D problems.
it is only based on mex and permutation .
like why now a days , the contest are going bad and bad ?
D is greedy and C feels as well , the thing is that on lower level(or my level) questions they have started giving constructive or less — pattern based more to avoid AI based cheating
C is graphs and cycle. Check my submission
Also, I politely disagree with you. This is one of the best rounds recently on codeforces. The problem quality was amazing
can anyone help me with this doubt with problem B..can anyone explain why if i iterate over all the elements in the vector divisible by minimum element given to find a pair if its gcd is equal to minimum element if i find then i just print yes....then it should not give wrong answer in o(n^2) time complexity..it would have given tle ...but it gave wrong answer....if i take gcd of all elements divisible by minimum element it shows accepted how?? i mean let g = gcd(b,c,d....z),where a|b,c,d,...z; so g should be equal to either of (gcd(b,c...z),gcd(c,d....z),gcd(d,e....z),...gcd(y,z)) right?
Let $$$G = \gcd(a_1, a_2, \dots, a_n)$$$.
For any pair $$$(a_i, a_j)$$$, we have: $$$G \mid a_i$$$ $$$\text{and}$$$ $$$G \mid a_j$$$ $$$\Rightarrow G \mid \gcd(a_i, a_j)$$$ $$$\Rightarrow$$$ Thus, $$$\gcd(a_i, a_j) \geq G$$$
Let the array be:
[2, 12, 20, 30]min = 2gcd(12, 20, 30) = 2 = minSo we can split as:
Prefix =
[2], Suffix =[12, 20, 30]→min = gcd = 2→ YESBut pairwise GCDs are:
gcd(12, 20) = 4gcd(12, 30) = 6gcd(20, 30) = 10None equal to
2, hence pairwise checking fails. Must take gcd of all divisible-by-min elements.thank you very much!!got it..
THANKS!
nice C and nice D. but E is too hard for me :)
B's complexity is $$$O(n + \log mn)$$$ I guess, since $$$\gcd$$$ reduces $$$\log$$$ times, or it does not change. After $$$\gcd$$$ becomes $$$mn$$$, $$$\gcd$$$ function is calculated in $$$O(1)$$$.
Kind of a dumb question, but for problems like C, do we always need to assume that we need to output the minimum number of operations needed? I got that problem wrong because of that :( ...
Generally, I maintain a rule of thumb that it's good to highlight keywords such as minimize, maximize, etc. I have had an unpleasant amount of WAs because I'd just skim over those words and forget about them when modeling the solution.
If you highlight those keywords, you can then determine whether or not you should minimize/maximize or whatever it is you have to do.
On a separate note, sometimes it's easier to make a strategy that always minimizes the number of operations and sometimes it is not. If it's easy to make such a strategy (and you can more or less prove that it's always optimal), then you should use it. Otherwise, such as in the case of problem C (I personally just avoided that line of thought as I figured it would waste more time), it's easier to come up with a strategy that just works and doesn't minimize the number of operations + the statement didn't have any of those keywords, because of which we aren't restricted.
yeah what happened was that I didn't consider the case where if n was odd and if the index where the numbers were the same on a and b (ex: n = 5, and a[3] = 4 and b[3] = 4), then I wouldn't need to do a swap to the middle. I just swapped the element that has the same values to the middle always without considering this case, figuring it wasn't important as the solution didn't require you to minimize the swaps.
Can anyone please share their approach for problem E? I didn't quite understand any part from the editorial for E.
Formula Calculation :
Missing = array of all the numbers that do not appear in the original array
For a range [l,r], spotted = number of -1's present in the range
total = number of -1's in the original array
non-spotted = total — spotted = number of -1's present outside the range
idx = index of the maximum number in Missing that can contribute to MEX of the range
Eg. Permutation: [-1, 0, -1, -1, 3, -1]
=> Missing = [1,2,4,5]
In range [1, 4], spotted = 3 and idx = 2
(Note that the maximum MEX for the range is 3, but it is not present in the Missing Array)
Claim: Every element in Missing having index <= idx can be made the MEX of range [l,r]
Proof: Let's say we want Missing[i] $$$(i \lt =idx)$$$ as the MEX of the range,
Choose i-1 positions from the spotted -1's, insert all the elements with index<=i
and 1 position from non-spotted -1's and insert Missing[i].
So we reduce down to calculating the number of ways in which $$$Missing[i]$$$ become MEX for a range.
=> Number of ways = C(spotted, i-1) * (total — spotted) * (i-1)! * (total — i)!
=> Contribution of i = Number of ways * Missing[i].
Now we can simply precompute the Contribution for all possible pairs of (spotted, i) in O(N^2).
An another number which can contribute as a MEX for a range is the MEX we generate by putting all the missing elements ideally.
For eg. Permutation: [-1, 0, -1, 3, -1]
=> Missing = [1,2,4]
In range 1 to 3, if we put 1 at index 1 and 2 at index 3, the MEX of [1,3] is 3.
Let this number be Ideal MEX.
We can compute the contribution due to Ideal MEX for a range by:
=> C(spotted,idx) * idx! * (total-idx)! * Ideal MEX.
For O(N^3), we can iterate over all possible range and calculate the contribution for each i.
This can be optimised to O(N^2)
For a given range, sum of the value of all possible valid permutations(answer) = summation of contribution due to Missing[1] + Missing[2] + .. Missing[idx] which can be precalculated using prefix sum.
Refer to my submission for implementation:
https://codeforces.me/contest/2084/submission/314305426
IDK but D feels like 1300, C was more difficult than D I guess
Can you please write proper editorial for problem E? Especially optimization part
This is my solution:
Firstly, we can calculate the expected MEX values for all ranges independently. Let's assume we are calculating for a specific range $$$[L, R]$$$. Let $$$emp$$$ be the number of $$$-1$$$'s in the range $$$[L, R]$$$, and let $$$all$$$ be the total number of $$$-1$$$'s in the entire array.
Instead of summing the expected MEX values as $$$\sum_{\text{mex}} (\text{how many permutations have MEX equal to } \text{mex}) \times \text{mex}$$$, we will instead sum as $$$\sum_{\text{mex}} (\text{how many permutations have MEX} \geq \text{mex})$$$, without multiplying by the MEX.
Suppose we want to compute the number of permutations where $$$\text{mex} = m$$$. Then, every integer $$$i \lt m$$$ must appear in the range $$$[L, R]$$$. If any such $$$i$$$ does not appear, then there are no valid permutations with MEX $$$\geq m$$$.
Let $$$bon$$$ be the number of integers $$$i \lt m$$$ that do not appear in the range. Then the number of permutations with MEX $$$\geq m$$$ is $$$\frac{emp! \times (all - bon)!}{(emp - bon)!}$$$.
This works because we choose $$$bon$$$ positions among the $$$emp$$$ empty slots to assign the missing values $$$i \lt m$$$, and the remaining $$$emp - bon$$$ slots can be filled with the remaining $$$-1$$$'s, while adjusting for the total permutations using the factorials.
It's clear that this can be computed for all MEX values in $$$O(N^3)$$$ time: 314148419.
We can optimize this using prefix sums: precompute values for all possible $$$emp$$$ and MEX values, and for each query, just check whether all integers $$$i \lt m$$$ are present in the range. My current implementation runs in $$$O(N^2 \log N)$$$, but I believe it can be optimized to $$$O(N^2)$$$: 314152700.
You're right, and removing the log is actually quite simple. You can refer to my implementations during and after the contest: 314135087 and 314183843. The main idea is that the maximum possible MEX will never decrease as R increases, so you can just maintain it with two pointers.
Problem C Never mentioned to output minimum number of operations.
It clearly says, "If it is possible, output any valid sequence of operations. Otherwise, output −1 ".
I could not solve this problem during contest because of this and so many others would have faced the same problem. This needs to be addressed...!!!
Yeah I had the same issue too lol, I assume that they would usually say print the minimum number of operations, right?
You don't need to output the minimum number of operations thou...
You can check my two submissions and that is what got me WA
No your code is wrong check the judge result it says p[1] = q[1], not too many operations used or something
It said the same for me, yet when I changed my code to correct one specific case where if the middle element had the same indices, then I wouldn't need to do a swap (I did a swap which used an extra operation unneccesarily), it was AC.
From the statement:
You can perform the following operation at most $$$n$$$ times: Choose two indices $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq n$$$, $$$i \neq j$$$)...
Note that it says $$$i\neq j$$$. Both yours and MaheshDA's submissions output an operation on
2 2for the test case:which clearly violates this condition.
Oh ok, that makes a lot of sense. Thank you so much.
In E's solution:
There are exactly $$$k$$$ -1s
I believe it's supposed to $$$c_1$$$ not $$$k$$$. zltzlt
Fixed. Thank you.
Anyone ~ why this is giving WA , 314126993 , on PreT 3 ?
should output
YESbecause $$$\gcd{(30, 42, 70)} = 2$$$ but your submission outputsNO.For problem C, does anybody know why the following strategy of doing the swaps fails?
Store the indices of symmetric pairs in a map. Say
a[i] = b[j] = x, andb[i] = a[j] = y, for some1 <= i, j <= n, then we havemp[{min(x, y), max(x, y)}] = {i, j}.Keep a counter (initially 0) and loop through each pair
p:pis the pivot for oddn(i.e.p.first == p.second), ignore it.(p.first, p.second)with the pairs at(counter, n - counter - 1)respectively.Here is the submission: 314141297
Look, it's nice that there's hints in editorials these days, but those hints need to match difficulty of the problem. Take hint 1 of F, for example: it's offering 0 new information, instead it's (rephrasing) just "read and comprehend the problem statement". Here's an example of a much better hint:
The limit on number of operations doesn't matter.
Perhaps extremely basic handholding hints that point people to look for the obvious, to "speak math language" in general, are useful for early problems, but they won't help anyone who can actually solve a harder problem with hints without looking at a solution. That should be the criterion: can we reasonably expect anyone to be good enough to solve a problem just looking at hints up to K, but unable to figure out hint K on his own?
Solution for d:https://youtu.be/Ts0a4loZEP4
I think there might be a minor error in the Problem E solution—shouldn't it be $$$c_1 = i, k = j$$$?
This C makes me very annoyed because it's extremely difficult to debug.
I'd like to know how to write the checker for problem D,does there exist a solution of complexity O(n)?
Can anyone pls tell me why this fail problem C:
code...
Although E is difficult（I think the difficulty is 2400），E is an excellent problem！
Can anyone just explain the approch in layman terms for problem E, Everyone is focusing on the implimentation, but I just want to know how it got there.
Let's say the permutation is filled. How many intervals have MEX > 0? Add that to the answer. How many have MEX > 1? How many have > 2? Etc. At the end, every interval is added to the answer as many times as its MEX.
When the permutation is unfilled, at each of these steps where we're counting MEX > $$$m$$$, the cost of each interval isn't 1 but the number of permutations we can make such that this interval has MEX > $$$m$$$, i.e. it contains everything in $$$[0, m]$$$. That's the formula with factorials.
For a given $$$m$$$, the formula only depends on the number of unfilled positions $$$f$$$ in a given interval; the number of intervals can be large, but $$$f \in [0, N]$$$ so we want to count how many intervals have a given $$$f$$$; answer is (sum of cost * count over $$$f$$$) over $$$m$$$.
Last thing to deal with is that as $$$m$$$ increases, some intervals become impossible — we're only counting those that contain all the values in $$$[0, m]$$$ that are filled at the start, so they're superintervals of $$$I$$$ = [min position, max position of those filled values]. As $$$m$$$ increases, this interval $$$I$$$ increases too, so we can just remove those intervals from the counting above, each will only be removed once.
Ohh, I think I got it, I'll have to give it some time of my own to fully understand. Thanks a lot
The editorial for E says $$$d_{x,0},d_{x,1},\dots,d_{x,y-1}$$$, but shouldn't it be $$$d_{0,x},d_{1,x},\dots,d_{y-1,x}$$$ based off of the definition of $$$d_{i,j}$$$?
I think definition of dp[i][j] should be the number of intervals satisfying these conditions for c1 = i and k = j? Then rest makes sense a little bit.
zltzlt
Sorry. Now it's fixed.
I have a slightly different implementation of H. I think it is a bit simpler: 314754662.
For problem G2, I have a solution whose correctness I don't know how to prove. You can see it here:the link. The intrinsic interpretation is that the positrons and the electrons must be distributed as uniformly as possible, thus we only need to consider the states where the number of positrons and the number of electrons near each other.
My submission for E (Blossom) gets TLE on test-7 despite being O(n^2). Could someone help me figure out the issue?
Submission ID: 323239191
solving D in O(1)
For B, why are we putting all the numbers that are
on the right (GCD) side? For example, the numbers in the array could be p*min(a) and p*q*min(a) — these two are divisible by min(a), but their GCD is p*min(a), not min(a). Why not put p*min(a) in the left (MIN) side instead?