Thanks to everyone who participated in this round! I hope you enjoyed the problems! Apologies for the strict time limit on E; it was very hard to balance allowing slow intended solutions but not fast cheese ones.
2285A - Composite Permutation
What possible values are there for $$$p_1$$$?
How can you extend a valid permutation of length $$$n-1$$$ to length $$$n$$$?
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
if (n < 4) cout << "-1\n";
else {
cout << "4 3 2 1";
for (int i = 5; i <= n; i++) cout << ' ' << i;
cout << '\n';
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
cin >> t;
while (t--) solve();
}
Can you count the number of composite permutations of length $$$n$$$?
2285B - Diverse String
Find a formula for the diversity of a string. It may help to consider which strings are obtainable when $$$x=0$$$ and when $$$x=1$$$ separately.
If the string has $$$z$$$ zeroes and $$$o$$$ ones, then its diversity is $$$(1+2+\dots +z)+(1+2+\dots +o)+1$$$.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
string s;
cin >> n >> k >> s;
int x = 0;
for (char c : s) if (c == '0') x++;
x = min(max(x, n - x) + k, n);
int y = n - x;
long long ans = 1LL * x * (x + 1) / 2 + 1LL * y * (y + 1) / 2 + 1;
cout << ans << '\n';
}
signed main() {
int t = 1;
cin >> t;
while (t--)
solve();
}
2285C - Max Substitution
Sort the array in descending order.
To use the operation on an element, what other elements must you use the operation on first?
In every obtainable array, there exists a prefix where every value in the prefix is modified, and no value outside the prefix is modified.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9+7;
ll mpow(ll a, ll b) {
ll r = 1;
while (b) {
if (b & 1) {
r *= a;
r %= mod;
}
a *= a;
a %= mod;
b /= 2;
}
return r;
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &i: a) cin >> i;
sort(rbegin(a), rend(a));
ll ans = 1;
for (int i = 0; i < n; i++) {
if (i < n - 1 && a[i] == a[i + 1]) break;
ans += mpow(a[i] - 1, i + 1);
ans %= mod;
}
cout << ans << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
cin >> t;
while (t--) solve();
}
2285D - Reverse Partition
To count the number of special partitions of $$$a$$$, let $$$b$$$ denote the reverse of $$$a$$$. How does $$$p$$$ partition $$$a-b$$$?
It partitions it into $$$m$$$ segments which each have sum $$$0$$$.
Consider the prefix sum of $$$a-b$$$. At what positions can this array be cut by $$$p$$$?
It can be cut after a prefix if and only if the prefix has sum $$$0$$$.
How does each query affect the prefix sum of $$$a-b$$$?
Each query corresponds to a range addition on the prefix sum.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
const int mod = 1e9+7;
ll mpow(ll a, ll b) {
ll r = 1;
while (b) {
if (b & 1) {
r *= a;
r %= mod;
}
a *= a;
a %= mod;
b /= 2;
}
return r;
}
vector<ll> fact, ifact;
void precomp_fact(int n) {
fact.resize(n + 1);
ifact.resize(n + 1);
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % mod;
ifact[n] = mpow(fact[n], mod - 2);
for (int i = n; i; i--) ifact[i - 1] = ifact[i] * i % mod;
}
int choose(int n, int r) {
if (r < 0 || r > n) return 0;
return fact[n] * ifact[r] % mod * ifact[n - r] % mod;
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<int> a(n);
for (auto &i : a) cin >> i;
precomp_fact(n);
vector<ll> c(n);
for (int i = 0; i < n; i++) c[i] = a[i] - a[n - 1 - i];
vector<int> zero(n);
map<ll, vector<int>> pos;
for (int i = 0; i < n - 1; i++) {
if (c[i] == 0) zero[i + 1]++;
zero[i + 1] += zero[i];
c[i + 1] += c[i];
pos[c[i]].push_back(i);
}
while (q--) {
int i, v;
cin >> i >> v;
int l = --i;
int r = n - 1 - i;
if (l > r) swap(l, r), v = -v;
int x = zero[n - 1] - zero[r] + zero[l];
auto it = pos.find(-v);
if (it != pos.end()) {
x += lower_bound(all(it->second), r) - lower_bound(all(it->second), l);
}
int ans = choose(x, m - 1);
cout << ans << '\n';
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
cin >> t;
while (t--) solve();
}
Can you solve if the queries are not independent, with the same time complexity?
2285E - Arithmetic Subarray
Fix the leftmost unchanged element $$$a_l$$$ in the subarray.
Extend as far right as possible using a greedy algorithm.
To extend right efficiently, use the fact that $$$k$$$ is smaller than $$$n$$$.
Consider the arithmetic subarrays of the original array.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a) cin >> x;
vector<int> end(n, n - 1);
for (int i = n - 3; i >= 0; --i)
end[i] = a[i + 1] - a[i] == a[i + 2] - a[i + 1] ? end[i + 1] : i + 1;
int ans = min(n, k + 1);
for (int i = 0; i < n; ++i) {
map<int, int> slopes;
int r = i + 1, most = 0;
int d = 0;
if (end[i] - i > k) {
most = end[i] - i; d = a[i + 1] - a[i]; r = end[i];
} else {
for (; r < n; ++r) {
int delta = a[r] - a[i];
if (delta % (r - i) == 0) {
auto it = slopes.try_emplace(delta / (r - i), 0).first;
if (++it->second > most) most = it->second, d = it->first;
}
if (r - i - most > k) break;
if (most > k) break;
}
}
ans = max(ans, min(n, most + 1 + k));
if (r == n || most <= k) continue;
int bad = r - i - most;
++r;
while (r < n) {
if (a[r] != a[i] + 1LL * d * (r - i)) {
if (bad == k) break;
++bad;
++r;
} else {
r = (r + 1 < n && a[r + 1] - a[r] == d ? end[r] : r) + 1;
}
}
ans = max(ans, min(n, r - i - bad + k));
}
cout << ans << '\n';
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
cin >> t;
while (t--) solve();
}
2285F - Mooclear Reactor 3
Think of the atoms as vertices of a graph, where reactive pairs are edges.
What algorithms can we use to check for edges after each merge?
There are two simple ways to check whether an edge exists between $$$U$$$ and $$$V$$$:
Check every pair of atoms in $$$U$$$ and $$$V$$$.
Scan the adjacency lists of $$$U$$$ and check whether any neighbor belongs to $$$V$$$.
What is the worst-case complexity for both algorithms?
Combine both algorithms using square root decomposition.
Carefully analyze the time complexity using amortized analysis.
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m, q;
cin >> n >> m >> q;
vector<vector<int>> r(n);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
--x, --y;
r[x].push_back(y);
r[y].push_back(x);
}
for (auto &i : r) sort(begin(i), end(i));
vector<int> c(n), s(n), d(n);
vector<vector<int>> a(n);
int ans = n;
int threshold = sqrt(m) / 5;
for (int i = 0; i < n; i++) {
c[i] = i;
s[i] = 1;
d[i] = size(r[i]);
a[i] = {i};
}
while (q--) {
int u, v;
cin >> u >> v;
u = c[--u];
v = c[--v];
if (u != v) {
bool e = 0;
if (make_pair(d[u], s[u]) < make_pair(d[v], s[v])) swap(u, v);
if (d[v] == 0) {}
else if (max(s[u], s[v]) > threshold) {
for (int i : a[v]) {
for (int j : r[i]) {
if (c[j] == u) {
e = 1;
}
}
}
} else {
for (int i : a[v]) {
if (r[i].empty()) continue;
for (int j : a[u]) {
if (binary_search(r[i].begin(), r[i].end(), j)) {
e = 1;
break;
}
}
}
}
if (e) {
ans += s[u] + s[v] - 2;
vector<int> b;
for (int i : a[u])
b.push_back(i);
for (int i : a[v])
b.push_back(i);
for (int i : b) {
c[i] = i;
s[i] = 1;
d[i] = size(r[i]);
a[i] = {i};
}
} else {
ans--;
if (s[u] < s[v])
swap(u, v);
for (int i : a[v]) {
a[u].push_back(i);
c[i] = u;
}
a[v].clear();
s[u] += s[v];
d[u] += d[v];
}
}
cout << ans << '\n';
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int t = 1;
cin >> t;
while (t--)
solve();
}








Wow, record editorial release! Thanks for the contest!
peak contest
The 2nd one was too hard for me lol Now it's time to understand how to solve
wow so fast editorial. thanks
I didn't perform well in this round though
I was still able to cheese $$$O(nklog(nk))$$$ on E. Might be hackable.
398698053
I also had O(nklog(nk)), don't think it's hackable (tcs are pretty strong)
Yeah, my bad. I forgot to use long long on problem B, thought my solution was wrong, and ended up submitting 4 times.
Next time I’ll always use
#define int long long:)No contest can be better than goodbye 2026. But, I will accept it being equal.
awesome contest thx.
Hi Administrators,
I am writing this comment on behalf of Chirag352 whose account was disabled during the contest. He started the contest by trying to solve question D but was using wrong value of MOD, so he got 3 wrong submissions, after 1:09 hrs, he started from question A, but while solving C, which also used MOD as 1e9+7, he realized his mistake in D's code and after submitting C, he corrected the value and also submitted D within 1-2 minutes and after this his submissions were skipped and the account was disabled. To justify his accountability, he has solved around 1000 questions on this platform and around 700+ on others and also he is my teammate in icpc this time and we are selected for 2 regionals. Please look on this matter as quickly as possible. Thanks
AksLolCoding MikeMirzayanov
the wrong value of mod can happen to anyone. my biggest blunder was once i kept using wrong problem input to check and keep getting WA. But i didn't submit that. was so upset after that.
MikeMirzayanov
I feel like the amount of math problems in this contest is not normal.
Isn't problem C $$$O(n \log V)$$$?
you are confusing base of the exponentiation with the exponent itself. the exponent can at max be n not v.
Didn't realize updates were independent lol
Oh, i see you in Yotube :)
I have 974 subscribers :) — https://www.youtube.com/@Freddy-a01
s3 для резервирования медиаархивов
Solved D using Mo's Algorithm to sort the range count queries, thankfully the time limit was lenient
I tried to solve problem D using sqrt decomposition to calculate the values of the difference array, but I got TL. In the end, only AI was able to optimize the code.
Yes, me too. I was afraid that it will fail in the main tests but luckily it did not despite I used map which worsens the complexity.
my solution in O(n): https://codeforces.me/contest/2285/submission/398728798
For problem $$$A$$$ we can simply use random shuffle. The only invalid cases are when $$$a_1 = 1$$$, $$$a_1 = 2$$$, or $$$a_i = 1$$$ for some prime index $$$i$$$. Since there are only $$$25$$$ primes up to $$$100$$$, the probability of getting an invalid permutation in one shuffle is at most $$$\frac{27}{100} = 0.27$$$. If we shuffle $$$60$$$ times independently, the probability that all attempts are invalid is at most $$$0.27^{60} \approx 1.4 \times 10^{-34}$$$, which is practically zero.
look at my submission.
Thanks for the interesting solution.
To be more accurate, the only invalid cases are $$$a_1=1$$$, $$$a_1=p$$$ or $$$a_p=1$$$ ($$$p$$$ is prime). So the invalid probability of each random shuffle is $$$\frac{26}{100}+(1-\frac{26}{100})\times\frac{25}{99}\approx 0.45$$$.
Thanks for pointing that out
If there was a testcase with t = 100 and all n = 5, your solution would have failed with high probability. If n = 5, only possible answers are when a1 = 4 and a4 = 1, so 6 correct answers. Overall 120 permutations => probability of failing all would be (114/120)^number of tries. You used 60 in your code => (114/120)^60 ≈ 0.046. Given t = 100, your solution would have failed with high probability.
A good counterexample, but thankfully it didn't happen.
Liked (not loved) C. Max Substitution but I believe B. Diverse String was unnecessarily overcomplicated as a statement; it could have been simpler.
i thought b statement was basically as simple as the problem would allow.
B's statement is really short, no clue what you're talking about
If they just said "the diversity is $$$T(\text{ones}) + T(\text{zeros}) + 1$$$ then the problem would be a slop div2a instead of a good div2b
the wording on 'k' felt ambiguous
yeah but reading the samples made it pretty obvious what was going on.
another solution for problem E. https://codeforces.me/contest/2285/submission/398683302
In this code, we use the structure like LCA with binary-lifting, and the time Complexity is $$$ O(NK\log K) $$$. This is first coded by @sadmecurial, but this user is unfortunately disabled.
Post contest discussion stream with ABCDE here
Editorial?????? Incredibly fast!!!!
Problem E has questionable constraints.
$$$O(nk \log k)$$$ for $$$nk \le 10^7$$$ should not pass.
Mooclear reactor 4 soon...
Quick editorial release, nice! Will try to upsolve D.
Slightly unrelated, but does anyone have any idea when the ratings for problems will be updated? It's been a while... the last time ratings were updated, it had been a while too (and I think they were updated shortly after someone posted a blog about it, although I don't know whether it was just a coincidence)
sometimes they will get updated, you can check clist.by for approximate ratings
I drew 4 pages of trees to up solve problem C after the contest, but after reading the editorial, I realized that I was too focused on the trees and missed the forest. No wonder why some people were able to solve C very quickly. RIP pupil :(, back to grey again...
the statement for b sucked ass.
Good for number theory lovers. Became expert btw...
For E, I upsolved by maintaining linked lists of maximal size over (delta, position) elements, adding $$$(\frac{a_j-a_i}{j-i}, j)$$$ in front of $$$(\frac{a_j-a_i}{j-i}, i)$$$ when $$$i$$$ is at the head. This approach would allow one to do aggregations over all possible subarrays with at least 2 elements unchanged, not just find the maximal size.
literal slopfest
author forgot it is NNN and put a lot of number-theory
In Problem B how can we say that the diversity is independent of on the positions of 0's and 1's in the explanation "_Consider the subsequence of 0s in s. Any operation with x=1 must affect a contiguous segment of these 0s. In fact, we can change any segment of these 0s to 1s by using the operation._ _ There are T(z)=z+(z−1)+⋯+1=z(z+1)/2 segments of 0s_"
here we assume contiguous segment of 0's and 1's and later says only depends on count of 1s and 0s.
Can anyone please explain it.
if we have 0100101 and let's say we want to look for the new distinct arrays that can be formed by the operation of changing a range [l,r] to 0, then choosing a subarray that only has 0's won't create any alternations, so 1 must be included choosing the ranges [2,2] = {1}, [1,2] = {0,1}, [2,3] = {1,0}, [2,4] = {1,0,0} all leads to same new array cause they only cause the 1 on position 2 to change, all other elements are the same so we should choose the ranges that are different based on the 1's they enclose the ranges that we can choose here are: [2,2], [5,5], [7,7] for one 1's [2,5], [5,7] for two 1's [2,7] for three 1's here we can already see the pattern of number of subarrays decreasing by one, everytime number of 1's enclosed in increased by one so its 3,2,1 here
moreover, it's like we can choose any 1 as starting point and any 1 after it or itself as the ending point of the range for three 1's if we choose first 1 as the start then for the end, we have three options: itself, the second one, or the last if we choose 2nd 1 then we have 2 options and for the 3rd one as start we only have 1 option so we get 3+2+1 for three ones so it doesn't matter where the ones are, the number of ranges that can be formed with a given count of 1 is always the same and by ranges we mean those ranges that leads to a distinct new array that no other chosen ranges produce
we can also say say if we have n number of 1's then the number of (start, end) pairs of that can be formed is C(n,2) but it doesn't include the unit length ranges so we got to add n to it C(n,2) + n = n(n-1)/2 + n = n(n+1)/2
For Problem E
Index $$$i$$$ must be paired with a value at least a distance of $$$k+1$$$ from it if it will remain unchanged in any maximal subarray. You can then check each pair $$$j$$$ and hash the pair $$$(\frac{a_i-a_j}{i-j}, a_i-i\frac{a_i-a_j}{i-j})$$$ and maintain the maximum cnt for a window.
Even though the solution is $$$O(nk)$$$ with hashing it's literally impossible to pass. I've tried some small worst case improvements by making the hash table at most size $$$k^2$$$ and upgrading my pair hash but it doesn't seem to work. [submission:https://codeforces.me/contest/2285/submission/398740269]. I know technically this code is nklogk but it seems sorting vectors with unique is faster than using sets and maintaining the values of the hash is faster than calculating on the fly.
Problem A, Bonus: (n-1)! * (n-P) (where P is number of prime indices from 1 to n).
C seems too hard !
Is it just me ?