Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
n = int(input())
s = input()
if '2025' in s and not '2026' in s:
print(1)
else:
print(0)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
a, b = map(int, input().split())
if a < b:
a, b = b, a
x, y = 0, 0
ans = 0
cur = 1
while True:
x, y = y + cur, x
if x <= a and y <= b:
ans += 1
cur *= 2
else:
break
print(ans)
Idea: Roms
Tutorial
Tutorial is loading...
Solution (BledDest)
def good(x, y, n, k):
ans = True
for i in range(n):
if x[i] <= y[(i + k) % n]:
ans = False
return ans
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
k1, k2 = 0, 0
for i in range(n):
if good(b, a, n, i):
k1 += 1
if good(c, b, n, i):
k2 += 1
print(k1 * k2 * n)
2182D - Christmas Tree Decoration
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
const int MOD = 998244353;
int mul(int x, int y) {
return x * 1LL * y % MOD;
}
int binpow(int x, int y) {
int z = 1;
while (y > 0) {
if (y & 1) z = mul(z, x);
x = mul(x, x);
y >>= 1;
}
return z;
}
int main() {
vector<int> f(N, 1);
for (int i = 1; i < N; ++i)
f[i] = (f[i - 1] * 1LL * i) % MOD;
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n + 1);
for (int &x : a) cin >> x;
int k = accumulate(a.begin(), a.end(), 0) / n;
int z = 0, bad = 0;
for (int i = 1; i <= n; ++i) {
int x = min(a[i], k);
a[i] -= x;
a[0] -= k - x;
z += a[i] == 0;
bad |= a[i] > 1 || a[0] < 0;
}
bad |= a[0] > z;
int ans = bad ? 0 : f[z];
if (!bad) {
ans = mul(ans, f[n - z + a[0]]);
ans = mul(ans, binpow(f[a[0]], MOD - 2));
}
cout << ans << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m;
long long k;
cin >> n >> m >> k;
vector<vector<int>> ev(m);
for (int i = 0; i < m; ++i) {
int x; cin >> x;
ev[x - 1].push_back(-1);
}
for (int i = 0; i < n; ++i) {
int x, y, z;
cin >> x >> y >> z;
ev[x - 1].push_back(z - y);
k -= y;
}
int ans = 0;
multiset<int> s;
for (int i = 0; i < m; ++i) {
reverse(ev[i].begin(), ev[i].end());
for (int x : ev[i]) {
if (x == -1) {
if (!s.empty()) {
s.erase(--s.end());
++ans;
}
} else {
s.insert(x);
}
}
}
while (!s.empty() && *s.begin() <= k) {
k -= *s.begin();
s.erase(s.begin());
++ans;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
2182F1 - Christmas Reindeer (easy version)
2182F2 - Christmas Reindeer (hard version)
Idea: Roms
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
const int LOGN = 61;
int add(int x, int y)
{
x += y;
if(x >= MOD) x -= MOD;
if(x < 0) x += MOD;
return x;
}
int sub(int x, int y)
{
return add(x, -y);
}
int mul(int x, int y)
{
return (x * 1ll * y) % MOD;
}
int binpow(int x, int y)
{
int z = 1;
while(y > 0)
{
if(y % 2 == 1) z = mul(z, x);
x = mul(x, x);
y /= 2;
}
return z;
}
vector<int> get_required(long long x)
{
vector<int> ans(LOGN);
int cnt = 0;
for(int i = LOGN - 1; i >= 0; i--)
{
if((x >> i) & 1)
{
ans[i + cnt]++;
cnt++;
}
}
return ans;
}
void solve()
{
int n, m;
cin >> n >> m;
vector<int> freq(LOGN);
for(int i = 0; i < n; i++)
{
int x;
cin >> x;
freq[x]++;
}
int max_n = n + m + 111;
vector<int> fact(max_n, 1);
for(int i = 1; i < max_n; i++)
fact[i] = mul(fact[i - 1], i);
vector<int> inv_fact(max_n);
for(int i = 0; i < max_n; i++)
inv_fact[i] = binpow(fact[i], MOD - 2);
vector<int> pow2(max_n, 1);
for(int i = 1; i < max_n; i++)
pow2[i] = mul(pow2[i - 1], 2);
auto choose = [&](int x, int y)
{
if(x < y || x < 0 || y < 0) return 0;
return mul(fact[x], mul(inv_fact[y], inv_fact[x - y]));
};
auto sum_greater = [&](int x, int y)
{
if(y >= x) return 0;
int ans = pow2[x];
for(int i = 0; i <= y; i++)
ans = sub(ans, choose(x, i));
return ans;
};
for(int i = 0; i < m; i++)
{
int t;
long long x;
cin >> t >> x;
if(t == 1)
freq[x]++;
else if(t == 2)
freq[x]--;
else
{
auto req = get_required(x);
int ans = 0;
int cur = 1;
int cnt_less = 0;
for(int i = 0; i < LOGN; i++) cnt_less += freq[i];
for(int i = LOGN - 1; i >= 0; i--)
{
cnt_less -= freq[i];
ans = add(ans, mul(cur, mul(sum_greater(freq[i], req[i]), pow2[cnt_less])));
cur = mul(cur, choose(freq[i], req[i]));
}
ans = add(ans, cur);
cout << ans << "\n";
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
for(int i = 0; i < t; i++) solve();
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
const int MOD = 998244353;
int add(int a, int b){
a += b;
if (a >= MOD) a -= MOD;
if (a < 0) a += MOD;
return a;
}
int mul(int a, int b){
return a * 1ll * b % MOD;
}
int binpow(int a, int b){
int res = 1;
while (b){
if (b & 1)
res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int n, k;
vector<vector<int>> g;
struct dpar{
vector<int> dp;
int ml, ad;
dpar(){
ml = 1, ad = 0;
dp.clear();
}
int& operator [](int k){
return dp[max(0, int(dp.size()) - k - 1)];
}
int get(int k){
int x = dp[max(0, int(dp.size()) - k - 1)];
return add(mul(x, ml), ad);
}
};
vector<dpar> dp;
vector<int> fact;
void dfs(int v){
int bst = -1;
vector<int> val;
for (int u : g[v]){
dfs(u);
dp[u].dp.push_back(add(0, mul(binpow(dp[u].ml, MOD - 2), -dp[u].ad)));
if (bst == -1 || dp[u].dp.size() > dp[bst].dp.size())
bst = u;
val.push_back(dp[u].get(k - 1));
}
if (val.empty()){
dp[v].dp.push_back(1);
return;
}
vector<int> pr(val.size() + 1, 1), su(val.size() + 1, 1);
forn(i, val.size()){
pr[i + 1] = mul(pr[i], val[i]);
su[val.size() - i - 1] = mul(su[val.size() - i], val[val.size() - i - 1]);
}
swap(dp[v], dp[bst]);
{
int i = find(g[v].begin(), g[v].end(), bst) - g[v].begin();
int cur = mul(fact[g[v].size() - 1], mul(pr[i], su[i + 1]));
if (cur == 0){
int mx = 1;
for (int u : g[v]) mx = max(mx, int(dp[u].dp.size()));
dp[v].dp.assign(mx, 0);
dp[v].ml = 1, dp[v].ad = 0;
}
else{
dp[v].ml = mul(dp[v].ml, cur);
dp[v].ad = mul(dp[v].ad, cur);
}
}
int rev = binpow(dp[v].ml, MOD - 2);
forn(i, g[v].size()){
int u = g[v][i];
if (u == bst) continue;
int cur = mul(fact[g[v].size() - 1], mul(pr[i], su[i + 1]));
int tot = mul(cur, dp[u].get(n));
dp[v].ad = add(dp[v].ad, tot);
forn(j, dp[u].dp.size()){
dp[v][j] = add(dp[v][j], -mul(rev, tot));
dp[v][j] = add(dp[v][j], mul(mul(cur, dp[u].get(j)), rev));
}
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--){
cin >> n >> k;
g.assign(n, {});
for (int i = 1; i < n; ++i){
int p;
cin >> p;
--p;
g[p].push_back(i);
}
dp.assign(n, {});
fact.resize(n + 1, 1);
for (int i = 1; i <= n; ++i)
fact[i] = mul(fact[i - 1], i);
dfs(0);
cout << dp[0].get(n) << '\n';
}
return 0;
}
good contest
D > E?
Yes, At first when you look at them. E looks more easier. As basic sorting then selecting. But in D you have to apply PnC.
Does PnC mean combinatorial mathematics? :)
I'm pretty sure it means Permutations and Combinations, since P and C are the shorthand for those two respectively (i.e. nPk/nPr and nCk/nCr).
PnC is known as combinatorial mathematics outside india. :)
this section of questions feel particularly harder
Wait outside or inside India? I am from the US and nobody calls it that :skull
Yess !
this test case in Problem E : 2 7 15, 5 6 7 3 5 6 6, 5 8 10, 5 6 8 , ,i didnt get it why the output should be 2 not 0
Bro both get the box with >= xi beauty. So it is sufficient condition to make them happy.
i thought boxes has prices xi , didnt read the part that boxes i earn which means they are free xD
Real GOOD BYE!
x=z−b0 be the number of people who will not hang decorations during this round. If x<0, there are too many decorations in the 0-th box, and z people cannot hang them all. In this case, there are no fair permutations either.
i don't see this condition ever occur BledDest
i even submitted editorial sol'n without that condition and worked well
yeah,i also think the same cz we can always pick the decorations in the zeroth box (untill we are finished ofc).
not only it does never occur but i think it is also logically wrong because if you have more a[0] than "needed" then you can just keep picking decorations from a[0], until you finish all of them. I wonder if it is possible to hack that solution given "bad |= a[0] > z;".
Yeah, looks like this condition is redundant in this implementation of the solution. I think it remained from the previous implementation, where some other check was missing and this condition was needed in its place.
SanathK, your argument is correct. In fact, it's kinda too good case where we've support (
a[0]) more than required (for smallera[i]s). And as mentioned by few users as well, once alla[i]s have been exhausted, we can keep exhaustinga[0]until done. I needed to reiterate back my solution once I read the editorial, then realized that it's logically correct to have this situation.do editorials for educational round usually come out this late only?
Yes they usually are late
How did 9k people even solve C ? Am i missing something ? what the hell bro. Skipped my Dinner for this contest.
same i got 2 tle.
i think you are missing that you use java (runs slow), i recommend using c++
If you had written a brute force solution and checked the array like all i possible for a given j then you would have found that it is same for all j and similarly for k and from there you could have gotten that idea that you only need to calculate it once. Sometimes writing brute helps :)
Its crazy that the first 5 questions did not anything require anything like graphs or proper DP and could be solved with usual solving techniques. W contest but still htf are their so many solves on C and D mannn!!!!
Is it possible to do C in less than O(n^2)?
you can speed it up with bitset
Fenwick Tree,may be.
Before, you could become a pupil by solving A and B, but now there are too many cheaters. Now you need to solve A, B, and C , I don’t support cheaters , I hope in 2026 cheaters will be less than 2025 , welcome 2026
The problem C was overall good problem but I don't understand why the test cases were so strict for it. I had a different approach which was based on hashing but it was too slow because the constraints were strict. I had to use policy based hash tables which I wasn't aware of to get AC. You can find my submission here 355786375
i think you just had to use a custom hash. unordered map will almost always get targeted in test cases
iiit banglore damnnn u must have crazy rank in jee..
Nice contest. D was tough but i managed to get it :D
i don't know why D $$$n \le 50$$$
because t <= 5000 so it will take about 5 * 1e5
that's mean n2 is not good I guess
Am I like the only person who could solve D but not C?
same, i upsolved D without looking at solution but cant understand C even after looking solution of it
I solved C but D cooked me
na i see it, i solved D before C
Very hard contest for me :(
im still perplexed on the thing that in the D you had to take inverse modulus in order to get the correct answer . I calculated NcR correctly , but since i didnt take inverse modulus(i divided by searching a multiple of each denominator in the numerator) i got wa on 3rd test. BledDest please look into the test cases . you can see my submission too .
the accepted one -> 355954390
the wa on third test case one -> 355950951
I don't have an answer to your question unfortunately, but I was wondering if you could help me understand the solution implementation.
The solution gets the final answer by computing
f[z]*f[n-z+x]*inv(f[x])where f[n] is n!
but the combinatorics states that the answer is:
f[z] * inv(f[x]) * inv(f[z-x]) * f[x] * f[n-x]But I don't see how these two are equal.
in the code, a[0] is not x, z — a[0] is actual x described in editorial.
Thank you!!
Your strategy of computing binomial coefficients is incorrect.
Suppose we're trying to compute $$${{15}\choose{9}}$$$, which is $$$\dfrac{10 \cdot 11 \cdot 12 \cdot 13 \cdot 14 \cdot 15}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6}$$$. In your implementation, you will first pick a number from the numerator which is divisible by $$$6$$$, and divide it by $$$6$$$. You will get $$$\dfrac{10 \cdot 11 \cdot 2 \cdot 13 \cdot 14 \cdot 15}{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5}$$$, and you can't get rid of $$$4$$$ in the denominator since no multiple in the numerator is divisible by $$$4$$$.
Option 1: Pascal's triangle.
Option 2: factorials and inverse factorials.
Option 3: factorize all multiples in the denominator, so instead of working with $$$1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6$$$, you work with $$$1 \cdot 2 \cdot 3 \cdot 2 \cdot 2 \cdot 5 \cdot 2 \cdot 3$$$, and the issue does not arise.
thanks a lot sir
My approach to problem D:
You can reduce the problem to creating a matching between $$$Q = [q, q, \ldots, q, q+1, q+1, \ldots, q+1]$$$ and $$$A = [a_1, a_2, \ldots a_n]$$$ (WLOG assume $$$a$$$ is sorted), such that every element $$$Q$$$ maps to an element that is $$$\leq$$$ it in $$$A$$$. Iterate from right to left in $$$a$$$. For $$$a_i$$$, pick an element from the suffix of $$$Q$$$, among the elements that are $$$\geq a_i$$$ -- the answer will end up being a product of $$$n$$$ numbers.
Maybe this approach is overkill, but it was short to code (and intuitive for me personally when I tried the problem). It can be generalized to a setting where you want to count matchings between $$$Q$$$ and $$$A$$$ where $$$Q$$$ could have more than two distinct elements https://mirror.codeforces.com/contest/2182/submission/356026194
awoo I think there is a typo in editorial of Problem F1/F2,
the contribution of the next one will be at most $$$\frac{2^{i-1}}{2^{k-1}}$$$, the contribution of the next one will be at most $$$\frac{2^{i-1}}{2^{k-2}}$$$,
the contribution of the next one will be at most $$$\frac{2^{i-1}}{2^{k+1}}$$$, the contribution of the next one will be at most $$$\frac{2^{i-1}}{2^{k+2}}$$$,
Yes, this is a typo. Thank you for noticing! Will be fixed in a couple of minutes.
Hello
(Someone else has pointed out and I didn't notice, but I don't know how to delete my comment)
For problem D I didn't understand why the editorial code made the check b0 > z, to see if there are more gifts on box 0, compared to the people who dont have any left decorations on the last round.
Suppose we are on the last round and b0 > z. If the gifts on box 0 are more, then by playing two more round we can finish the decorations and the permutation is fair, a contradiction since we conjectured we are on the last round. So, in the last round, b0 <= z by default.
I commented out this check, and the code passes all the test cases. Am I missing something?
Really loved question D
Hello, Does someone have a hint or some code on how to solve D by DP? I find the combinatorial solution pretty inuitive but I guess less generalizable than a DP approach can be. Thank you
Can someone tell me what's wrong with my solution i can't tell at all ):
356437655
never mind i figured it out:
356438348
problem G
the last visited vertex in the subtree must be at a distance of no more than k−1 from v Let dp[v][k] store the number of ways to traverse the subtree of vertex v such that the last visited vertex is at a distance exactly k ** from v**
Doesn't it is typo?
I did't catch. If we have the distance less than k-1 by the condition 1 how it could be k?
:thinkng
Why we need to multiply by the factorial of the number of remaining children to fix their order to the last child?
Dear Codeforces Team / awoo,
I am writing to appeal the plagiarism flag on my submission [355739601] for Problem 2182E.
My solution was flagged as coinciding with other participants. I firmly assert that I wrote this code independently. The similarity arises because the problem relies on a standard and widely known technique: Greedy with Regret (using a Min-Priority Queue).
This approach is the standard solution for this class of problems, most notably seen in Problem 1526C (Potions). The logic dictates a specific implementation structure:
Sort the available resources (in this case, boxes and friends).
Iterate through the requirements.
Use a Priority Queue to track "costs" taken so far.
If a constraint is hit, swap the current element with the minimum element in the PQ if it improves the result (the "Regret" step).
Because this is a standard template for this specific type of greedy problem, the structure of the if/else block and the Priority Queue operations will inevitably look identical across many correct submissions. There are very few distinct ways to implement this exact logic efficiently.
Furthermore, there are distinct implementation details in my code that prove independent authorship:
My code uses a custom struct Friend to manage the data, whereas the conflicting codes (e.g., Yugam2508) utilize vector<pair<int,int>>.
My variable naming and I/O handling are distinct.
The coincidence is strictly algorithmic due to the standard nature of the "Greedy with Regret" pattern, not due to sharing code or using a common unauthorized source during the round.
I kindly request that you review these structural differences and the standard nature of the algorithm used.
Thank you for your time and fairness.
In D, It is not possible for the condition $$$z \lt b_0$$$ to hold. Because, then it can go for one more round i.e $$$k$$$ will increase by 1.
Submission removing that condition from the editorial code — 357421945.
Exactly. I had been thinking for 1 hour here thinking how can $$$z$$$ be $$$ \gt b_0$$$ after decrementing $$$b_i$$$ by $$$k$$$. Your submission that was accepted likely means that the editorial writer overlooked that detail.
Could somebody explain to me why in problem D, $$$b_0 \lt 0$$$ would mean that no permutation is fair? Couldn't it be swapped out for a bigger number and thus allow enough decoration for other boxes that couldn't quite make it upto $$$k$$$? Also, I don't think $$$b_0$$$ would ever be greater than $$$z$$$. Could somebody help me out see $$$b_0$$$ being $$$ \gt z$$$ in some cases? I have been thinking for 1 hour so far, but couldn't come up with answers.
I just bashed the sub-problem in G by maintaining the dp arrays of all the vertices in disjoint lazy segment trees that I lazily expanded, only to realize while in the middle of my implementation that the lazy updates that necessitated their use took the form of "multiply every element with some value", which can be handled in a far simpler manner without segtrees like in the editorial lol.
Surprisingly, my "naive" solution runs in just 515 ms.