| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3756 |
| 2 | tourist | 3723 |
| 3 | orzdevinwang | 3696 |
| 4 | Kevin114514 | 3647 |
| 5 | Radewoosh | 3631 |
| 6 | ecnerwala | 3596 |
| 7 | Benq | 3527 |
| 8 | maroonrk | 3518 |
| 9 | ksun48 | 3484 |
| 10 | Nachia | 3463 |
| # | User | Contrib. |
|---|---|---|
| 1 | errorgorn | 169 |
| 2 | Qingyu | 165 |
| 3 | Dominater069 | 159 |
| 4 | cry | 157 |
| 4 | Um_nik | 157 |
| 6 | adamant | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | djm03178 | 148 |
| 9 | soullless | 146 |
| 10 | chromate00 | 144 |
Thank you for participating! I hope you enjoyed the problems.
Idea:Galina_Basalova
#include<bits/stdc++.h>using namespace std; int main(){ int t; cin >> t; while (t--) { int n; cin >> n; cout << n * 2 << "\n"; } return 0;}2086B - Large Array and Segments
Idea:FelixArg
#include<bits/stdc++.h>using namespace std;#define int long longvoid solve(){ int n, k, x; cin >> n >> k >> x; vector<int> a(n); for (int i = 0; i < n; i++){ cin >> a[i]; } if (accumulate(a.begin(), a.end(), 0ll) * k < x){ cout << 0 << '\n'; return; } int l = 1, r = n * k; while(l <= r){ int m = l + (r - l) / 2; int cnt_a = (n * k - m + 1) / n; int suff = (n * k - m + 1) % n; int sum = cnt_a * accumulate(a.begin(), a.end(), 0ll); for (int i = n - suff; i < n; i++){ sum += a[i]; } if (sum < x){ r = m - 1; } else{ l = m + 1; } } cout << r << '\n';} signed main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--){ solve();}}2086C - Disappearing Permutation
Idea:FelixArg
#include<bits/stdc++.h>using namespace std;#define int long longvoid solve(){ int n; cin >> n; vector<int> p(n); for (int i = 0; i < n; i++){ cin >> p[i]; p[i]--; } set<int> X; for (int i = 0; i < n; i++){ int d; cin >> d; d--; while(!X.contains(d)){ X.insert(d); d = p[d]; } cout << X.size() << ' '; } cout << endl;} signed main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--){ solve();}}Idea:FelixArg
#include<bits/stdc++.h>using namespace std;#define int long long const int MOD = 998'244'353; int bpow(int x, int p){int res = 1;while(p){if (p % 2){res = (res * x) % MOD;}p >>= 1;x = (x * x) % MOD;}return res;} int fact(int x){int res = 1;for (int i = 1; i <= x; i++){res = (res * i) % MOD;}return res;} void solve(){vector<int> c(26);for (int i = 0; i < 26; i++){cin >> c[i];} int s = accumulate(c.begin(), c.end(), 0ll);vector<int> dp(s + 1);dp[0] = 1; for (int i = 0; i < 26; i++){if (c[i] == 0){continue;}for (int j = s; j >= 0; j--){if (j + c[i] <= s){dp[j + c[i]] = (dp[j + c[i]] + dp[j]) % MOD;}}} int ans = dp[s / 2] * fact(s / 2) % MOD * fact((s + 1) / 2) % MOD;for (int i = 0; i < 26; i++){ans = (ans * bpow(fact(c[i]), MOD - 2)) % MOD;} cout << ans << '\n';} signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while(t--){ solve(); }}Idea:FelixArg
#include<bits/stdc++.h>using namespace std; long long dp[40][120][2][2]; void count(vector<int>& num){int m = num.size();memset(dp, 0, sizeof(dp)); dp[0][0][1][0] = 1;for (int i = 0; i < m; i++){for (int j = 0; j < 3 * m + 2; j++){for (int k = 0; k < 4; k++){if (j + k >= 3 * m + 2){break;}if (num[i] == k){dp[i + 1][j + k][1][0] += dp[i][j][1][0];dp[i + 1][j + k][0][0] += dp[i][j][0][0];if (k == 0){dp[i + 1][j + k][1][1] += dp[i][j][1][1];dp[i + 1][j + k][0][1] += dp[i][j][0][1];}}else if (num[i] > k){dp[i + 1][j + k][0][0] += dp[i][j][0][0];dp[i + 1][j + k][0][0] += dp[i][j][1][0];if (k == 0){dp[i + 1][j + k][0][1] += dp[i][j][0][1];dp[i + 1][j + k][0][1] += dp[i][j][1][1];}}else{dp[i + 1][j + k][0][0] += dp[i][j][0][0];if (k == 0){dp[i + 1][j + k][0][1] += dp[i][j][0][1];}}}if (j + 4 < 3 * m + 2){if (num[i] == 4){dp[i + 1][j + 4][1][1] += dp[i][j][1][0];dp[i + 1][j + 4][0][1] += dp[i][j][0][0];}else{dp[i + 1][j + 4][0][1] += dp[i][j][0][0];}}}}} void solve(){long long l, r, k;cin >> l >> r >> k;l--;if (k >= 90){cout << 0 << '\n';return;} vector<long long> zeb;long long cur = 0;for (int i = 0; i < 60; i += 2){cur ^= (1ll << i);zeb.emplace_back(cur);}int m = zeb.size(); vector<int> num_l;for (int i = m - 1; i >= 0; i--){int cnt = 0;while(l >= zeb[i]){cnt++;l -= zeb[i];}num_l.emplace_back(cnt);} vector<int> num_r;for (int i = m - 1; i >= 0; i--){int cnt = 0;while(r >= zeb[i]){cnt++;r -= zeb[i];}num_r.emplace_back(cnt);} count(num_r);long long ans = dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];count(num_l);ans -= dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1];cout << ans << '\n';} signed main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--){ solve();}}#include <bits/stdc++.h>using namespace std; vector<long long> z; void precalc(){ z = {1ll}; while(z.back() < 1e18) z.push_back(4 * z.back() + 1);} map<pair<long long, long long>, long long> dp; long long get(long long r, long long x){ if(dp.count(make_pair(r, x))) return dp[make_pair(r, x)]; long long& d = dp[make_pair(r, x)]; if(x > 4 * z.size()) return d = 0; if(x < 0) return d = 0; if(r == 0) return d = 0; if(r == 1) { if(x == 0) return d = 1; return d = 0; } auto it = lower_bound(z.begin(), z.end(), r); --it; long long y = *it; return d = get(y, x) + get(r - y, x - 1);} int main() { precalc(); int t; cin >> t; for(int i = 0; i < t; i++) { long long l, r, x; cin >> l >> r >> x; cout << get(r + 1, x) - get(l, x) << endl; }}Idea:Valentin_E
#include<bits/stdc++.h>using namespace std;#define int long long bool is_palindrom(const string& s){ int n = s.size(); for (int i = 0; i < n / 2; i++){ if (s[i] != s[n - i - 1]){ return false; } } return true;} bool check_pattern(const string& s){ int n = s.size(); char a = 'a', b = 'b'; int cnt_a = 0, cnt_b = 0; for (int i = 0; i < n; i++){ if (s[i] == a){ cnt_a++; } else{ cnt_b++; } } if (cnt_a % 2 == 1){ swap(cnt_a, cnt_b); swap(a, b); } if (s[n / 2] != b){ return false; } if (!is_palindrom(s)){ return false; } cnt_b--; cnt_a /= 2; cnt_b /= 2; if (cnt_a > cnt_b){ swap(cnt_a, cnt_b); swap(a, b); } if (s[0] == a){ cnt_a--; } else{ cnt_b--; } for (int i = 1; i < n / 2; i++){ if (s[i] == s[i - 1]){ if (cnt_a == 0){ return true; } return false; } if (s[i] == a){ cnt_a--; } else{ cnt_b--; } } return true;} pair<int, int> find_valid_move_odd(string s){ int n = s.size(); for (int i = 0; i < n; i++){ for (int j = i; j < n; j++){ swap(s[i], s[j]); if (check_pattern(s)){ return {i, j}; } swap(s[i], s[j]); } } return {-1, -1};} pair<int, int> find_valid_move_even(string s){ int n = s.size(); for (int i = n - 1; i >= 0; i--){ for (int j = 0; j <= i; j++){ if (s[i] == s[j] && i != j){ continue; } if (i == j && i != n - 1){ continue; } swap(s[i], s[j]); int cnt = 0; s += 'a'; for (int k = n; k >= 0; k--){ for (int l = 0; l <= k; l++){ if (s[k] == s[l] && k != l){ continue; } if (k == l && k != n){ continue; } swap(s[k], s[l]); if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){ cnt++; swap(s[k], s[l]); break; } swap(s[k], s[l]); } if (cnt == 1){ break; } } s.pop_back(); if (cnt == 1){ s += 'b'; for (int k = n; k >= 0; k--){ for (int l = 0; l <= k; l++){ if (s[k] == s[l] && k != l){ continue; } if (k == l && k != n){ continue; } swap(s[k], s[l]); if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){ return {i, j}; } swap(s[k], s[l]); } } s.pop_back(); } swap(s[i], s[j]); } } return {-1, -1};} void solve(){ string t = ""; while(1){ char ch; cin >> ch; if (ch == '0'){ break; } t += ch; if (t.size() % 2 == 1){ auto [l, r] = find_valid_move_odd(t); swap(t[l], t[r]); cout << l + 1 << ' ' << r + 1 << endl; } else{ auto [l, r] = find_valid_move_even(t); swap(t[l], t[r]); cout << l + 1 << ' ' << r + 1 << endl; } }} signed main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();}#include <bits/stdc++.h>using namespace std;#define forn(i, n) for(int i = 0; i < int(n); i++) const int N = 100; bool dp[N][N];pair<int, int> nxt[N][N][2];bitset<N> cur;bitset<N> form[N][N]; int main(){forn(i, N) forn(j, N) dp[i][j] = (i + j) % 2;for (int len = 1; len < N; len += 2){forn(x, len + 1){int y = len - x;int nx = x, ny = y;int i = 0;while (nx > 1 || ny > 1){if (nx > 1){nx -= 2;++i;}if (ny > 1){form[x][y][i] = form[x][y][len - i - 1] = 1;ny -= 2;++i;}}if (ny > 0){form[x][y][i] = 1;}}}for (int len = N - 3; len >= 1; len -= 2){forn(x, len + 1){int y = len - x;cur = form[x][y];forn(c, 2){cur[len] = c;bool found = false;forn(l, len + 1){forn(r, l + 1){if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();bool ok = true;forn(d, 2){cur[len + 1] = d;int nx = x + (c == 0) + (d == 0);int ny = y + (c == 1) + (d == 1);if ((cur ^ form[nx][ny]).count() > 2){ok = false;break;}}if (ok){found = true;nxt[x][y][c] = {l, r};}if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();if (found) break;}if (found) break;}if (!found){dp[x][y] = false;break;}}}}string s;cur.reset();for (int i = 0;; ++i){cin >> s;if (s == "0") break;int c = s[0] - 'a';int py = cur.count(), px = i - py;cur[i] = c;int nx = px + (c == 0), ny = py + (c == 1);int l = -1, r = -1;if (i % 2 == 1){auto res = nxt[px][py][c];if (res.first != res.second){l = res.first;r = res.second;}}else{assert(dp[nx][ny]);bitset<N> dif = cur ^ form[nx][ny];assert(dif.count() <= 2);if (dif.count() == 2){l = dif._Find_first();r = dif._Find_next(l);}}if (l == -1){cout << 0 << " " << 0 << endl;}else{cout << l + 1 << " " << r + 1 << endl;if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip();}}}
» |
» |
» | My approach for D was unoptimized DP which got MLE. Hope this round is educational for me in this regard. |
» | Before the round, I asked chatGPT to rate the difficulty of the problems, and this is what came out:
What do you think? |
- »»
- »»
- »»
» | can someone explain the combinatorics part of D in an easier way? |
- »»
Let us see another problem How many ways to arrange the word "mississippi"? Now, you have $$$11!$$$ possible permutations. However, there are repeated characters in "miiiisssspp" ,for example, if all similar letters are swapped there is no change. So, you need to put into consideration the frequence of every letter so you need to divide by $$$4!$$$ twice and $$$2!$$$.
Similarly, in our problem after the dp now you can split the string into two parts even and odd since they are independent and the number of ways is as discussed above.
- »»
Basically , there are dp[odd] ways of constructing the string.
Now if all elements were unique in this construction the number of formations would be dp[odd]! , similarly we can calculate for even as well.
Now we know that all elements are not unique as there are repeated elements as well so we use the formula (n!/k!) which gives us the number of unique formations that are possible.(here k means the number of elements which are repeated) This will result in (odd!*even!)/(freq of each element)!
- »»»»
This is similar to counting the number of distinct permutations of a multiset with $$$n$$$ elements, where:
$$$n_1$$$ elements are of type $$$1$$$, $$$n_2$$$ elements are of type $$$2$$$, $$$\dots$$$, $$$n_k$$$ elements are of type $$$k$$$, and $$$n_1 + n_2 + \cdots + n_k = n$$$.
We choose positions step by step: First, $$$ \binom{n}{n_1} = \frac{n!}{n_1!(n - n_1)!} $$$, then $$$ \binom{n - n_1}{n_2} = \frac{(n - n_1)!}{n_2!(n - n_1 - n_2)!} $$$, and so on.
Multiplying all: $$$ \binom{n}{n_1} \binom{n - n_1}{n_2} \cdots = \frac{n!}{n_1!(n - n_1)!} \cdot \frac{(n - n_1)!}{n_2!(n - n_1 - n_2)!} \cdots $$$
All intermediate factorials cancel out, and we get: $$$ \boxed{\frac{n!}{n_1! n_2! \cdots n_k!}} $$$
» | O(n) solution for B |
- »»»»
My O(N) solution for B:
#include <bits/stdc++.h>#define ll long long int#define For(i, N) for(i = 0; i < N; i++)#define FOR(i, K, N) for(i = K; i <= N; ++i)#define v vector#define vl vector<ll>#define vp vector<pair<ll, ll>>using namespace std;void solve() { ll N, K, X; cin >> N >> K >> X; ll i; vl A(N); For(i, N) { cin >> A[i]; } vl suff(N); ll sum = 0; for(i = N-1; i >= 0; i--) { sum += A[i]; suff[i] = sum; } ll ans = 0; For(i, N) { ll num = max(X - suff[i], (ll)0); num = num/sum + (num%sum != 0 ? 1 : 0); ans += max(K-num, (ll)0); } cout << ans << '\n';}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll T = 1; cin >> T; while(T--) { solve(); } return 0;}- »»»»»»
Me too seeing the tutorial saying O(n + log(k)) or O(n + k) got surprised as my solution too was O(n) ~~~~~ // this is code void solve() { int n, k, x; cin >> n >> k >> x; vector v = readVector(n); int s = sum(v); if(x > s * k) { cout << "0\n"; return; } int ans = n * (k — (x / s)), t = x % s; for(int i = n — 1; i >= 0; i--) { if(t < v[i]) { break; } ans--; t -= v[i]; } cout << (t == 0 ? ans + 1 : ans) << endl; } ~~~~~
» |
» | FelixArg you got any idea which problems gpt o3 mini high solves before proposing the contest , also which problems are they |
- »»
Yeap, I checked which problems can be solved by o3-mini-high, it turned out that all but F :(
I think it's because in almost all problem statements were highly formalized, and the problems themselves are more educational than in regular div2.
Now GPT is very good at solving problems, and authors have to either mess up statements or put up with it.
I believe that contests are created to enjoy solving problems without help, not to chase high rankings by all available methods, including unfair use of GPT.
» | Can someone explain why the following approach does not work for E: Zebra numbers are numbers of the form 111...111 in base 4. This is equivalent to $$$\frac{4^p - 1}{3}$$$ for some $$$p > 0$$$. This implies that for a number $$$x$$$ to have a zebra value of $$$k$$$, it is necessary and sufficient that sum of the digits in the base 4 representation of $$$3x + k$$$ must be equal to $$$k$$$. We can set $$$L = 3l + k$$$ and $$$R = 3 r + k$$$. We define our dp to find all numbers less than a number $$$X$$$ which have a zebra value of $$$k$$$ as follows: With Note that in the implementation, we must be sure that the final digit is zero, as we cannot have $p = 0$ since $$$\frac{4^p - 1}{3}$$$ would be equal to $$$0$$$. Subtracting the dp value for $$$X = L - 1$$$ from $$$X = R$$$ should give the correct result, but it does not. Can anyone point out the flaw in my reasoning? |
- »»»»
I had the same approach and the flaw here is that you can take each zebra upto 4 times. Eg answer for (4^m-1)/3-1 is 4. So base 4 doesn't quite work. I don't have a fix for this yet.
» |
» | Note: D can be solve with meet in the middle, which, while slower for this problem, passes no matter what the constraint on the sum of the number of characters is. |
- »»
Isnt the meet in the middle solution
n*26 choose 13 +
n* 26 choose 12 +
n* 26 choose 11 etc which tles?
- »»»»»»
Meet in the middle is 2^(n/2), where n is the number of elements (and a log factor if you are lazy though there are many ways to avoid it here tbh, not that it's needed), per test case. So the complexity is O(2^(n/2)t) which is about 2^13*10^4 in the worst case, which is pretty comfortably passing there. Link:https://codeforces.com/contest/2086/submission/313808229.
» |
» | In problem D we should divide not by the product of the elements of vector c, but by the product of the factorials of the elements of this vector. (In tutorial part. Code solution is ok) Just add factorials to formulas |
» |
» | I solved D — Even String problem using a different approach. The key observation is that every character in the string must be placed either in even or odd indices. This allows us to reduce the problem to a standard "pick-or-leave" DP problem. Let $$$dp[i][j]$$$ represent the number of ways to arrange the last $$$i$$$ characters such that there are $$$j$$$ remaining even indices. Since each character must be placed entirely in either even or odd positions, we don't need to track the number of remaining odd indices in the state—it's implicitly determined. So, let $$$k$$$ be the number of remaining odd indices. The transition becomes: $$$dp[i][j] = dp[i + 1][j - c[i]] * C(j, c[i]) + dp[i + 1][j] * C(k, c[i])$$$, where $$$c[i]$$$ is the count of character $$$i$$$ and $$$C(a, b)$$$ denotes "$$$a$$$ choose $$$b$$$". The idea is simple: if we decide to place character $$$i$$$ in the even indices, we have $$$C(j, c[i])$$$ ways to do it using $$$j$$$ available even positions; similarly, if we place it in the odd indices, we have $$$C(k, c[i])$$$ ways using $$$k$$$ odd positions. We multiply these counts with the respective DP values to accumulate the number of valid configurations. |
» |
» | Speedforces handled A, B, C — D tried, but got speedforced too! |
» | Alternate solution for D: Let $$$dp(i, j, k)$$$ be the number of strings you can make from the first $$$i$$$ letters if there are $$$j$$$ even positions and $$$k$$$ odd positions. Then: We can optimize this by realizing that $j+k = c[1] + c[2] + ... + c[i]$. So we can drop the $$$k$$$. Code:313882724 |
» |
» |
» | There's an easier way to solve problem B. Just use a suffix and see how many "full arrays" you need infront of that suffix so that the sum is larger than or equal to X. Code:https://codeforces.com/contest/2086/submission/314026288 |
» |
» | My O(n) solution for B: the total sum of array B is sum*k so to check how many A arrays we can remove from B, so that the sum is still greater than x would be, (k*sum — i*sum) >=x, i being the number of arrays we can remove, so (k-i)*sum >= x, if we rearrange this we get i <= k — ceil(x/sum), so i is at max k — ceil(x/sum). So number of positions is n*i, and then we have a leftover sum = k*sum — i*sum, we run a loop from the start of the array and we check if leftoversum>=x, we do ++output, then we do leftoversum -= A[idx] submission :https://codeforces.com/contest/2086/submission/314027065 |
» |
» | Can we solve C using graphs? If YES, then how? Can someone share sol? |
- »»
- »»
Yes. I solved C with dsu. I think dsu is also a kind of graph.code
» | In Problem D, why is ans*bpow(fact(c[I]), MOD — 2) the same as dividing by a factorial? |
- »»
In modular arithmetic with a prime modulus p, we cannot perform division directly. So, instead of doing a divided by b modulo p, we transform it into a multiplied by the modular inverse of b modulo p. To calculate this modular inverse, we use Fermat’s Little Theorem, which says that if p is prime, then b^(p — 1) is congruent to 1 modulo p. This implies that b^(p — 2) is congruent to the inverse of b modulo p. So, to divide by a number under modulo p, we multiply by its modular inverse, which is b^(p — 2) mod p. That’s why in the expression ans * bpow(fact(c[i]), MOD — 2), we are not actually dividing by fact(c[i]), but instead multiplying by its modular inverse — effectively achieving the same result as division under modulo MOD. You can search over youtube if you are unable to understand this or you can read other blogs over cf also .
» | I want to explain the brute force for F. In the tutorial of F,it said "however, deriving them manually is quite complicated, as there are many situations." But I consider this problem as a perfect chance to practice case work: Do the first three letters by case work. First, whether $$$s_1$$$ is 'a' or 'b' doesn't matter. We can just record the longest 'ababab' prefix and the value of $$$s_{mid}$$$ ,and do case work. Do two letters $$$x,y$$$ once.
In the $$$p=1$$$,we don't care $$$p=mid-1$$$. As in the code,there is $$$2\times 2 \times 2+2\times 2\times 2\times 2\times 2=40$$$ cases,handle them one by one and get c++ code in 15kb. I highly recommend you to readcode, and I'm glad you to find my mistakes. |
» | Cannot understand why If the greedy algorithm works for all numbers less than y , then in the decomposition of the number y , there must be at least one number zi−1 . |
- »»
Suppose the greedy algorithm works for all numbers less than $$$y$$$, but not for $$$y$$$. Then, the partition of $$$y$$$ should start with some number $$$z_j$$$ such that $$$j < i$$$. If $$$j = i-1$$$, case closed.
Otherwise, the partition of $$$y$$$ consists of the number $$$z_j$$$ and the partition of $$$(y - z_j)$$$ such that $$$z_j \le z_{i-2}$$$. Since $$$y \ge z_i$$$, it means that $$$y - z_j \ge z_{i-1}$$$. So, the greedy partition of $$$(y-z_j)$$$, which is optimal by our assumption, starts with either $$$z_i$$$ (then $$$y$$$ can also be greedily partitioned) or $$$z_{i-1}$$$ (then $$$z_{i-1}$$$ is included in the optimal partition of $$$y$$$).
↓
| Name |
|---|