Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
for _ in range(int(input())):
s = input()
t = input()
lcp = 0
n = len(s)
m = len(t)
for i in range(1, min(n, m) + 1):
if s[:i] == t[:i]:
lcp = i
print(n + m - max(lcp, 1) + 1)
```

2025B - Binomial Coefficients, Kind Of

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
const int MOD = int(1e9) + 7;
int main() {
int t; cin >> t;
vector<int> ks(t);
for (int _ = 0; _ < 2; _++)
for (int i = 0; i < t; i++)
cin >> ks[i];
vector<int> ans(1 + *max_element(ks.begin(), ks.end()), 1);
for (int i = 1; i < (int)ans.size(); i++)
ans[i] = (2LL * ans[i - 1]) % MOD;
for (int k : ks)
cout << ans[k] << '\n';
return 0;
}
```

Idea: fcspartakm

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
j = 0
for i in range(n):
j = max(i, j)
while j + 1 < n and a[j + 1] - a[j] <= 1 and a[j + 1] - a[i] < k:
j += 1
ans = max(ans, j - i + 1)
print(ans)
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution 1 (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
typedef long long li;
const int INF = int(1e9);
const li INF64 = li(1e18);
int n, m;
vector<int> rs;
bool read() {
if(!(cin >> n >> m))
return false;
rs.resize(n);
fore (i, 0, n)
cin >> rs[i];
return true;
}
struct LazySum {
vector<int> ps;
LazySum(int n) : ps(n, 0) {}
//[l, r]
void add(int l, int r, int val) {
if (l > r) return;
ps[l] += val;
ps[r + 1] -= val;
}
void pushToAndClear(vector<int> &d) {
int sum = 0;
fore (i, 0, sz(ps)) {
sum += ps[i];
ps[i] = 0;
if (i < sz(d))
d[i] += sum;
}
}
};
void solve() {
LazySum ls(m + 2);
vector<int> d(m + 1, -INF);
d[0] = 0;
int cntP = 0;
for (int r : rs) {
if (r == 0) {
ls.pushToAndClear(d);
for (int i = m; i > 0; i--)
d[i] = max(d[i], d[i - 1]);
cntP++;
continue;
}
if (r > 0)
ls.add(r, m, 1);
else
ls.add(0, cntP + r, 1);
}
ls.pushToAndClear(d);
cout << *max_element(d.begin(), d.end()) << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

**Solution 2 (adedalic)**

```
n, m = map(int, input().split())
rs = map(int, input().split())
d = [-int(1e9)] * (m + 1)
d[0] = 0
add = [0] * (m + 2)
def addSegment(l, r):
if l <= r:
add[l] += 1
add[r + 1] -= 1
def pushAll():
sum = 0
for i in range(m + 1):
sum += add[i]
d[i] += sum
for i in range(m + 2):
add[i] = 0
cntPoints = 0
for r in rs:
if r == 0:
pushAll()
for i in range(m, 0, -1):
d[i] = max(d[i], d[i - 1])
cntPoints += 1
else:
lf, rg = 0, 0
if (r > 0):
lf = min(r, m + 1)
rg = m
else:
lf = 0
rg = max(-1, cntPoints + r)
addSegment(lf, rg)
pushAll()
print(max(d))
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y) {
x += y;
if (x >= MOD) x -= MOD;
return x;
}
int mul(int x, int y) {
return x * 1LL * y % MOD;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> ways(m + 1, vector<int>(m + 1));
ways[0][0] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j <= i; ++j) {
ways[i + 1][j + 1] = add(ways[i + 1][j + 1], ways[i][j]);
if (j) ways[i + 1][j - 1] = add(ways[i + 1][j - 1], ways[i][j]);
}
}
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
dp[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= m; ++j) {
for (int k = 0; k <= m; ++k) {
int nj = i ? j - k : j + k;
if (0 <= nj && nj <= m) {
dp[i + 1][nj] = add(dp[i + 1][nj], mul(dp[i][j], ways[m][k]));
}
}
}
}
cout << dp[n][0] << '\n';
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int N = 300043;
string choice = "xy";
string sign = "+-";
int qs[N][2];
string ans[N];
int n, q;
vector<int> g[N];
int color[N];
void pair_queries(int q1, int q2)
{
if(q1 > q2) swap(q1, q2);
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++)
if(qs[q1][i] == qs[q2][j])
{
ans[q1] = { choice[i], sign[0] };
ans[q2] = { choice[j], sign[1] };
return;
}
}
bool dfs(int v, int pe = -1)
{
// return true if parent edge still exists
color[v] = 1;
vector<int> edge_nums;
for(auto e : g[v])
{
int u = v ^ qs[e][0] ^ qs[e][1];
if(color[u] == 1) continue;
if(color[u] == 0)
{
if(dfs(u, e))
edge_nums.push_back(e);
}
else
edge_nums.push_back(e);
}
bool res = true;
if(edge_nums.size() % 2 != 0)
{
if(pe != -1) edge_nums.push_back(pe);
else edge_nums.pop_back();
res = false;
}
for(int i = 0; i < edge_nums.size(); i += 2)
pair_queries(edge_nums[i], edge_nums[i + 1]);
color[v] = 2;
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 0; i < q; i++)
{
cin >> qs[i][0] >> qs[i][1];
--qs[i][0];
--qs[i][1];
g[qs[i][0]].push_back(i);
g[qs[i][1]].push_back(i);
ans[i] = "x+";
}
for(int i = 0; i < n; i++)
if(color[i] == 0)
dfs(i);
for(int i = 0; i < q; i++) cout << ans[i] << endl;
}
```

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;
struct query{
int t, v;
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int m;
cin >> m;
vector<query> q(m);
forn(i, m) cin >> q[i].t >> q[i].v;
vector<pair<int, int>> xs;
forn(i, m) xs.push_back({q[i].v, i});
sort(xs.rbegin(), xs.rend());
forn(i, m) q[i].v = xs.rend() - lower_bound(xs.rbegin(), xs.rend(), make_pair(q[i].v, i)) - 1;
const int p = sqrt(m + 10);
const int siz = (m + p - 1) / p;
vector<int> tp(m);
vector<int> val(m);
vector<vector<long long>> dp(p, vector<long long>(2 * siz + 1));
vector<int> blbal(p);
auto upd = [&](const query &q){
tp[q.v] = q.t;
val[q.v] = xs[q.v].first;
blbal[q.v / siz] += q.t == 1 ? 1 : -1;
};
auto recalc = [&](int b){
dp[b].assign(2 * siz + 1, 0);
int bal = 0;
for (int i = b * siz; i < m && i < (b + 1) * siz; ++i){
if (tp[i] == 1){
dp[b][0] += val[i];
dp[b][0] += val[i];
dp[b][-bal + siz] -= val[i];
++bal;
}
else if (tp[i] == 2){
dp[b][-bal + 1 + siz] += val[i];
--bal;
}
}
forn(i, 2 * siz){
dp[b][i + 1] += dp[b][i];
}
};
auto get = [&](int b, int bal){
bal += siz;
if (bal < 0) return dp[b][0];
if (bal >= 2 * siz + 1) return dp[b].back();
return dp[b][bal];
};
for (auto it : q){
upd(it);
recalc(it.v / siz);
int bal = 0;
long long ans = 0;
for (int i = 0; i * siz < m; ++i){
ans += get(i, bal);
bal += blbal[i];
}
cout << ans << '\n';
}
return 0;
}
```

Finally

Hii everyone can anyone help me D problem?

https://codeforces.net/contest/2025/my

this was my solution

i would keep count of zeros till i

then our s could range from 0 to zeros

so my state is dp[s] which will have max check passed, so my time complexity was 5000*2*10^6

https://codeforces.net/contest/2025/submission/286105592

here i have reduced most of the redudant operations still i get tle

what i am thinking is to have a vector which stores starting and ending point of zeros if more than 1 then i would just increment my of zeros to difference between start and end their by saving some more time am i going in the right direction?

i would be using a unordered map to store my records.

I think you can safely do 1e8 complexity per second in c++ on codeforces; maybe 1e9 with luck (including simple operations, good caching and etc.); almost never > 5e9.

so my time complexity was 5000*2*10^6If the above is correct, it's 1e10 and should TLE.

yes i have optimized it by using binary search and sorting between 2 zeros.

For those, who interested in combinatorial way for problem E, using something similar to Catalan numbers: I wrote a post about it

Awesome.

Does Problem D fall under some Dp pattern saw this pattern of pushAndClear in many submissions it didn't click to me at all.

why is this downvoted?

isn't the code in problem A's solution $$$ O(n^2) $$$ due to string slicing?

It is, and it was kind of explained in the solution. They say it can be done in O(n) but there is no need to optimize it because the constraints are way too low.

.

for Problem c , can anyone tell why this solution is giving wrong answer on test 4 (i used binarysearch to solve this): https://codeforces.net/contest/2025/submission/285946605 thanks in advance !!

By binary research, you can only find the position of the last card which number is less than $$$(x+k-1)$$$, but you are not able to know if there are some numbers missing (between $$$x$$$ and the number of the last card). It’s the reason why you get wrong answer.

BTW, if you choose to check through the whole interval between $$$x$$$ and $$$(x+k-1)$$$ to make sure there are no missing numbers, the time complexity would be something like $$$O(N^2)$$$ in worst case and fails the time limit.

Therefore, I don’t think it’s possible to use binary research to solve this problem.

If you check my binary search function i have added this line :

here in the second part(after &&) i am checking if difference between the number and index is equal for start and end card. for ex:

if we consider from index 1 to 3 : diff is same (4-1 == 6-3) but for index 1 to 4 : (4-1 != 8-4).

by using this i was able to get correct answer with binary search. But on test case 4 it is failing.

The method works only when all numbers are distinct.

However, the problem allows number to be repeated. For example:

For index 1 to 4, diff is same (8-5 == 4-1), but obviously the number 7 is missing.

As you can see, if there are repeated numbers in the interval, the method cannot handle this situation properly.

More precisely, if the amount of repeated numbers is same as the amount of missing numbers (while both amounts are not 0), then the result of your method would be wrong.

The array on which I am running the binary search function only contains unique elements.

I calculated prefix sum for number of times a unique element in present. And stored all unique elements in an array on which i ran bs to find last index. Then i calculated the and from prefix sum based on the index i found from bs. Does this sound correct ?

Note about Problem A ( or any other problem concerning strings ) if you use Python and fast IO like:

`input = sys.stdin.readline`

then make sure to strip the string from whitespace and newlines.this code was tested in Windows fine:

However, the judges are based on POSIX systems and newlines are treated differently between the two systems. So I needed to make this small adjustment:

A small detail that may cost you a submission.

I guess for veteran competitive programmers this is trivial but it cost me some time and a wrong submission on an easy problem.

Problem B Binomial Coefficients Kind of Video Editorial Link: https://youtu.be/y_b2Khyk28w?si=Ku5V5m1jtT8EtA1e

Honestly, instead of doing this video... up solve next time.Or may be just downvote this comment and rant over it.

Not that anyone asked, but felt like sharing constructive feedback.

_i want to know,would anyone please tell me why rating going back;

my solution to D is a little different and it does not require bs or lazysum.

let $$$dp[i]$$$ denotes the $$$max \ score$$$ we can get if we are at index $$$j$$$ and have total $$$i$$$ intelligence points

if $$$A[i] == 0$$$ we will update dp values as follows.

let $$$cnt1[x] \ and \ cnt2[x]$$$ stores no. of checks with values x of intelligence and strength respectively.

if we choose to increase intelligence points then we are sure that we will pass all the intelligence checks having value $$$<=$$$ to our current intelligence values and because all the checks with value $$$<$$$ $$$current intelligence$$$ are already covered we will need to calculate how many values = current intelligence are there on the right on the right of index i and this value is stored in cnt1[current intelligence].

$$$dp[i] \ = \ max(dp[i] \ + \ cnt2[s - i], \ dp[i - 1] \ + \ cnt1[i])$$$

here $$$i$$$ is $$$current_intelligence$$$ and s is $$$current total score = intelligence + strength$$$

here is the 285916766 to explain better (ignore the code above solve function).

feel free to ask me if you have any queries. Thanks!

great solution... thanks for sharing. I think editorial solution for same is unnecessarily made complex (although nice explaination, but conclusion is messy)

E can be solved using DP + OEIS sequence A050155.

Define $$$g(m,k)$$$: Number of ways to choose $$$(m+k)/2$$$ elements for Player 1 out of m cards in a given suit such that Player 1 wins as given in Problem.

Write a brute force for function $$$g$$$ -> generate the sequence and paste on OEIS -> Find the formula $$$g(m,k)$$$ given in OEIS link above -> Precompute it -> Multiply $$$g(m,j-k)$$$ with $$$DP[i-1][k]$$$ and then sum over all values of $$$0\leq k\leq j$$$ to find $$$DP[i][j].$$$ $$$1\leq i\leq n,0\leq j\leq m$$$.

Can someone explain why its showing TLE in this submission in problem C , in the contest it got accepted but later on it came out to be TLE 285923775 in test case 24

bc of this

Spoilerunordered_map

Understood thanks a lot :)

.

E is a typical problem that requires $$$y-x\ge k$$$ on a path from $$$(0,0)$$$ to $$$(m,n)$$$. See here for more details.

In Problem C, I have an issue:

I have two pieces of code. The first one:

The second one:

I submitted the second piece of code to Codeforces Edu Round 170, Problem C, but it resulted in a Time Limit Exceeded (TLE). Then, I submitted the first piece of code, and it passed successfully. Is this an issue with the judging system, or is there a problem with my code? Can someone explain the reason? I would be very grateful!

link1:https://codeforces.net/contest/2025/submission/286123006 link2:https://codeforces.net/contest/2025/submission/286122969

If this problem is solved, you will get one of Python's optimization ticks!!!!!

Avoid using dict or set in an open-hack round as they're to be easily hacked. If you have to, write your own hash function.

By using

`str(i)`

instead of`i`

as the key, you actually define another hash function for $$$i$$$ so you pass the test.In fact, my program passed the hack attack, but I did not pass the final system test, but I think it is the same, thank you very much for your answer to me!

Is it possible for the O(mn) solution for D to be posted? I'm having a hard time understanding what the difference is between "last state" and "last record".

and are we supposed to increment $$$I$$$ counter while iterating through the input array?

I think an expert has the right answer

I read some of the other D solutions here but I cannot understand the intuition behind any of them so I think I'll give up on this question even though it's extremely frustrating.

Problem F is essentially equivalent to 858F - Wizard's Tour after some transformations, but I still believe it is a valuable problem for an Educational Round.

A $$$O(m\log m)$$$ solution for problem E.

From the derivation of the editorial, we can transform the question into the following form:

Cards of suit $$$1$$$ form a parenthesis sequence with $$$x$$$ extra open parentheses, and cards of suit not $$$1$$$ form a parenthesis sequence with $$$a_i$$$ extra close parentheses, $$$\sum a=x$$$.

Through the blog from darthrevenge can easily calculate a color answer. Write a generating function for a color suit:

Then the anwser is

The only problem is to calculate

There's two ways. One is use quick power with NTT in $O(n\log^2 n)$, and the other is use $$$\ln$$$ and $$$\exp$$$ with $$$f^n(x)=e^{n\ln f(x)}$$$ in $$$O(n\log n)$$$. Notice that calculate $$$\frac{f^n(x)}{f_0}$$$ instead of $$$f^n(x)$$$ when $$$f_0\ne 1$$$ because of $$$\ln$$$. submission

After contest i was thinking about solution one step lower than this. i was to create matrix and create solution of

O(m^3log(n)).if you can give any insight about it. i tried but couldn't create base matrix it got little complicated for me."Alternate" solution to D:

We can imagine an $$$m$$$ by $$$m$$$ grid, where $$$a[i][j]$$$ represents the state of having intelligence $$$i$$$ and strength $$$j$$$. By the end, we should reach the $$$i + j = m$$$ diagonal while reaching the maximum amount of checks.

In order to get the value of a check, the following conditions must be met: $$$i \geq r$$$ (or $$$j \ge r$$$) and $$$i + j = k$$$

...where $$$k$$$ is the number of zeroes before the check. In other words, it corresponds to adding $$$1$$$ to a prefix (or a suffix) of that diagonal. This can be done using prefix sums. Code: https://codeforces.net/contest/2025/submission/285891703

It's basically the same as the model solution, just using more memory. But I feel this is more intuitive and satisfactory.

how to solve E recursively ?

Can anyone please help me find out what's wrong with my submission to problem D? 286175219

In my submission: $$$f(l, r, s, i)$$$ = score if I am passing through $$$[l, r)$$$ having $$$strength = s$$$ and $$$intelligence = i$$$, and $$$dp[i][j]$$$ = max. score when I am at $$$i$$$-th zero and having $$$intelligence = j$$$

Actually I like my D approach better — https://codeforces.net/contest/2025/submission/285910844

We have the same approach! https://codeforces.net/contest/2025/submission/285891703

Can anyone suggest DP optimisation problems similar to D?

You are too pro for that!

sto YashBihany orz

I have a slightly different approach for problem F, though I think it actually ends up being the same as the one explained in the editorial.

Just like the editorial, I reduce the problem to making pairs of edges. Now, notice that on tree problem is quite straightforward as you merge all the leaves of the same parent together and then destroy them. If you have some node v, with only one leaf u and parent w, make pair ((u,v), (w,v)). This guarantees optimal answer.

Now, let's say we have some additional edge a-b, that is not in the tree. We can just direct it towards a and that is identical as if we added a leaf to node a. So we will get a new tree that has Q edges and Q+1 nodes, which we can solve using the algorithm previously mentioned.

Basically, the core of the idea is that as we don't care about the nodes and just edges, we can make multiple copies of one node in order to get a tree.

Hey can anyone help me in D, I think my TC is (m^2+n)*log(n), used dp to solve recursively and sorting checks separately between 0s, failed on test case-8 due to TLE, but saw some other solutions of same TC(I think) get all passed. Here is my code :

Are there any Binary Search & (non-DP) solutions to problem D?

I tried implementing a solution where I Binary Searched the number of points I could gain in the Intelligence Attribute. Using this, the number of points in the Strength Attribute could be found. Now by traversing the array 'r' backwards, we could decrease the Strength and Intelligence Attributes & parallelly counting the maximum score.

Coming to the comparison part, I compared the score to the edge cases (i.e Intelligence = m or Strength = m), If the Intelligence edge case gives a higher score, then I would try to increase the mid value in the Binary search, and if its the other way around, I would decrease the mid value in the BS.

I tried a similar approach but got WA. I am not sure why though.

NVM, I realised what i did wrong. Hope ur's is correct

I find problem D solutions(non DP) too

I see some people getting either WA or TLE on TC-8 of problem D, using a $$$O((m^2+n) \cdot \log n)$$$ solution. I also got stuck on this during the contest, but was able to make it work afterwards: 285935817.

The issue was that my DP was storing the maximum checks for each attribute

separetely(as a pair), whereas in the accepted solution I merged them into one value. Although I'm not sure why this works. If anyone has proof of why the first approach fails, I'd be interested to know.facing the same issue with 286249680

how can i correct mine?

appreciated!

Hey mate. I was looking at your code, but can't quite figure out how it works.

One thing that I noticed is that you're using a

`std::map`

, which is cache-unfriendly and may be causing your algorithm to have a high constant factor. Could you try using a`std::vector`

instead? In this problem it's possible because the values in the input sequence are limited by`m`

.Other things you can try: avoid a second pass over the input array; eliminate the first pass over the dp array, by replacing it with a

`std::vector`

with zero-initialized values; use two one-dimensional dp vectors instead of a full matrix.Thank you so much.. I will surely try to implement these changes and update the results. Appreciate it alot!

dpforces

Problem C: New Game Video Editorial Link : https://youtu.be/_0f9L1gBOP0?si=CHCgboEznPLOYpip

GG

Did anyone consider using Euler cycles/paths on problem F?

Is it possible by applying any trick to complete those components where don't exist any Euler cycle?

I just wonder, thanks in advanced.

**For D, An Alternative

tabulation that worked**

Let (

`dp[i][j]`

) denote the maximum checks passed having acquired (`i`

) points and using (`j`

) into intelligence, leaving (`i`

—`j`

) for strength.Now for the dp transition, we simply check if we reached this state by using the ( i )-th acquired point into strength or intelligence and binary searching for the checks passed after this.

This can be done in

by storing the strengths and intelligence tables where the

`i`

-th element stores a vector of sorted attribute checks of the form.My ImplementationIn Problem F solution what is

`int u = v ^ qs[e][0] ^ qs[e][1]`

in DFS? Is this selecting random vertex for some reason?what's wrong with my Solution D. Please someone explain. CODE

Is D's constraints meant to be so that $$$O(m^2)$$$ memory is too much? My DP runs in $$$O(n + m^2)$$$ with $$$O(m^2)$$$ memory but that seems to be too much. I have three $$$m \times m$$$ size arrays, with about $$$m^2$$$ states for the DP and the other two $$$m \times m$$$ frequency arrays store the number of occurences of each type of check between consecutive attribute point increases.

I think it can be reduced easily to $$$O(m)$$$ by storing only two layers and computing the frequencies during the DP but it didn't seem necessary before, I'm not too sure now. (Edit: I did this and it works now.)

For problem c, my approach was to form a sorted array of pair {number, frequency} using unordered_map first. Then use sliding window to keep a track of the maximumcards that i can gather. however it throws TLE on TestCase 9. I am unable to determine why is that so. Help would be appreciated here thanks!

submission link — https://codeforces.net/contest/2025/submission/287020150

try using just map

Hey thanks, I changed unordered_map to map, and got AC. I have noticed in other problems to, where unordered_set/map gives a TLE and set/map gives AC. Is it because worst case time complexity of unordered_set/map is

`O(n)`

and for set/map it is`O(log(n))`

?Always use map and set instead of unordered_map and unordered_set.

Even though unordered_map and unordered_set might work during initial tests, they can fail later if someone adds a large test case that triggers their worst-case performance, which is O(n). This can cause your solution to be too slow and get a "Time Limit Exceeded" error.

map and set are more reliable because they guarantee O(log(n)) performance.

Spoiler