Finally

Hii everyone can anyone help me D problem?

https://codeforces.me/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

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

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

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

.

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

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:

import sys

# defined functions for fast input
input = sys.stdin.readline
readListInts = lambda type_="int", sep=" ": list(
    map(eval(type_), input().strip().split(sep))
)

# defined functions for fast output
output = lambda x: sys.stdout.write(str(x) + "\n")
outputString = lambda x: sys.stdout.write(x + "\n")

def main():
    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
        output(n + m - max(lcp, 1) + 1)

if __name__ == "__main__":
    main()

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:

 s = input().strip()
 t = input().strip()

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

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

_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!

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$$$.

285923775 can someone explain why its giving TLE at test case 24 , in the contest the code was accepted but then it showed TLE, Thanks in advance

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

.

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:

from collections import deque
from sys import stdin
input = lambda: stdin.readline().rstrip()

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    hs = {}
    for i in a:
        if hs.get(str(i)) is None:
            hs[str(i)] = 0
        hs[str(i)] += 1
    mapLi = []
    mx = 0
    for i in hs:
        mx = max(mx, hs[i])
        mapLi.append([i, hs[i]])
    mapLi.sort(key=lambda i: (int(i[0]), -i[1]))
    ans = 0
    queue = deque([])
    cnt = 0
    for i, v in mapLi:
        ans = max(ans, cnt)
        while queue and len(queue) >= k:
            cnt -= queue.popleft()[1]
        ans = max(ans, cnt)
        while queue and abs(int(queue[-1][0]) - int(i)) > 1:
            cnt -= queue.pop()[1]
        ans = max(ans, cnt)
        queue.append((i, v))
        cnt += v
        ans = max(ans, cnt)
    ans = max(ans, cnt)
    return ans

for _ in range(int(input())):
    print(solve())

The second one:

from collections import deque
from sys import stdin
input = lambda: stdin.readline().rstrip()

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    hs = {}
    for i in a:
        if hs.get(i) is None:
            hs[i] = 0
        hs[i] += 1
    mapLi = []
    mx = 0
    for i in hs:
        mx = max(mx, hs[i])
        mapLi.append([i, hs[i]])
    mapLi.sort(key=lambda i: (int(i[0]), -i[1]))
    ans = 0
    queue = deque([])
    cnt = 0
    for i, v in mapLi:
        ans = max(ans, cnt)
        while queue and len(queue) >= k:
            cnt -= queue.popleft()[1]
        ans = max(ans, cnt)
        while queue and abs(int(queue[-1][0]) - int(i)) > 1:
            cnt -= queue.pop()[1]
        ans = max(ans, cnt)
        queue.append((i, v))
        cnt += v
        ans = max(ans, cnt)
    ans = max(ans, cnt)
    return ans

for _ in range(int(input())):
    print(solve())

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.me/contest/2025/submission/286123006 link2:https://codeforces.me/contest/2025/submission/286122969

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

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".

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. After some derivation from the editorial, we translate the question into the following form:

The cards of suit 1 need to form a bracket sequence with $$$x$$$ more open brackets, and each of the remaining suits need to form a bracket sequence with $$$a_i$$$ more close brackets, and need to guarantee $$$\sum a=x$$$.

You can see how to calculate the number of schemes in which cards of a suit have x more brackets in BLOG from darthrevenge. So we can write the generating function for a particular color:

So the anwser is

The only problem is to calculate

That's a typical problem. There's two algorithm: the first is just use NTT while fast power in $O(n\log^2 n)$ and the second is use the derivation like $$$f^{m}(x)=e^{m\ln f(x)}$$$ in $$$O(n\log n)$$$. You need to calculate $$$\frac{f^m(x)}{f_0}$$$ instead of $$$f^m(x)$$$ when $$$f_0\ne 1$$$ because of $$$\ln$$$.

Submission

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

Can someone explain the formal mathematical steps for B? It's easy enough to see the breakdown into an "unweighted pascal's triangle" but can someone show formally the step from ∑i=0j(ji)⋅C[n−i][k−j] TO ∑i=0k(ki)⋅C[n−i][0] just so my mind can rest

"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

Unable to parse markup [type=CF_MATHJAX]

In order to get the value of a check, the following conditions must be met:

Unable to parse markup [type=CF_MATHJAX]

Unable to parse markup [type=CF_MATHJAX]

...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.me/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$$$

Thank you for the contest.

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

Can anyone suggest DP optimisation problems similar to D?

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 :

#include <bits/stdc++.h>
using namespace std;
int mod = 1e9 + 7;
int main(){
    int n,m;
    cin>>n>>m;
    vector<int> v(n),z;
    int i1 = 0;
    z.push_back(0);
    vector<vector<int>> pos(m+1);
    vector<vector<int>> neg(m+1);
    for(int i = 0; i < n; i ++) {
        cin>>v[i];
        if(v[i] == 0) {z.push_back(i);i1++;}
        else if(v[i] > 0) pos[i1].push_back(v[i]);
        else neg[i1].push_back(abs(v[i]));
    }
    for(int i = 1; i < m+1; i ++) sort(pos[i].begin(),pos[i].end());
    for(int i = 1; i < m+1; i ++) sort(neg[i].begin(),neg[i].end());
    vector<vector<int>> dp(z.size()+1,vector<int>(z.size()+1,INT_MIN));
    function<int(int,int)> solve = [&](int i, int j){
        if(dp[i][j] != INT_MIN) return dp[i][j];
        if(i == z.size()) {
            int tot = (lower_bound(pos[i-1].begin(),pos[i-1].end(),j+1) - pos[i-1].begin()) +  (lower_bound(neg[i-1].begin(),neg[i-1].end(),i-j) - neg[i-1].begin());
            return dp[i][j] = tot;
        }
        int tot = (lower_bound(pos[i-1].begin(),pos[i-1].end(),j+1) - pos[i-1].begin()) +  (lower_bound(neg[i-1].begin(),neg[i-1].end(),i-j) - neg[i-1].begin());
        return dp[i][j] = max(solve(i+1,j),solve(i+1,j+1)) + tot;
    };
    int ans = solve(1,0);
    cout<<ans<<endl;
    return 0;
}

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 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.

for problem D , please can somebody help with my dp solution

286249680

vector z => stores indices of zeros

pmp , nmp are map of long long , vector => storing indices of corresponding numbers

transition:

dp[current index of zero in z vector][positive strength]

dp[m+1][m+1]

//if pos strength is increased a = dp[I+1][pos+1] + fun(pos+1)

if negative strength be increased b = dp[I+1][pos] + fun(I — pos + 1)

here fun(x) calculates count of nos that are equal to x and ahead of index i in input

so finally dp[I][j] = max(a,b)

for me expected TC: O(m^2 * logn) . But why the tle? Also how to correct it if i am on the right track?

dpforces

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

GG

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.

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define all(x) x.begin(),x.end()
#define yes cout<<"YES \n";
#define no cout<<"NO \n";
#define ln "\n"
#define MOD 1000000007
#define fi(ii, n) for(ll ii = 0; ii < n; ii++)
#define fd(ii,n) for(ll ii=n;ii>=0;ii--)
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vector<int>>

using namespace std;

int doshit(int target, vector<int> &vec){
int ans =0;
if(vec.empty()) return ans;

int high = vec.size()-1 , low =0;

while(low<=high){
     int mid = (low+high)/2;
     if(vec[mid]<=target){
        low = mid+1;
        ans = low;
     }
     else high = mid-1;
}
return ans;

}

void solve(){
int n,m;cin>>n>>m;
vi v(n);

fi(i,n) cin>>v[i];

vvi st(m+2),it(m+2);   // st[i] is strengths of people between ith anad i-1th zero encountered
vi tempS,tempI;

int ptr = 1;

fi(i,n){
    if(v[i]==0){
        st[ptr] = tempS;
        it[ptr] = tempI;
        ptr++;
        tempS.clear();
        tempI.clear();
    }
    else if(v[i]>0) tempI.push_back(v[i]);
    else tempS.push_back(abs(v[i]));
}
st[m + 1] = tempS;
it[m + 1] = tempI;

fi(i,m+1){
    sort(all(st[i+1]));
    sort(all(it[i+1]));
}

vvi dp(m + 3, vi(m + 3, 0));
//dp[i][j] - max checks passed with i points acquired and j in intelligence

//base case all strength pts (greedy?)

for(int i=1;i<=m;i++){
    
    int temp = doshit(i,st[i+1]);
    dp[i][0] = dp[i-1][0]+temp;
}

for(int i=1;i<=m;i++){
    for(int j=0;j<=i;j++){
        int strength = i-j;
        int intelligence = j;
        //assume this point was added to strength
        int temp1 = doshit(intelligence,it[i+1]);
        int temp2 = doshit(strength, st[i+1]);
        dp[i][j] = dp[i-1][j] + temp1+temp2;

        if(j>0)//now assume this point was added to intelligence
        dp[i][j] = max(dp[i][j],dp[i-1][j-1]+ temp1+temp2);
    }
}
int ans =0;
fi(i,m+3){
    ans = max(ans,dp[m][i]);
}
cout<<ans;
}

int main(void){

   ios_base::sync_with_stdio(false);
    cin.tie(NULL);

   int t=1;//cin>>t;
   while(t--){
      solve();
   }
   return 0;
}

In 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.)

**Problem D** : Can someone point out the error here 
int dynamic(int ind,vector<int>&v,vector<int>&dp,int sct,int ict)
{
    if(ind>=v.size())return 0;
    if(dp[ind]!=-1)return dp[ind];
    if(v[ind]==0)
    {
        return dp[ind]=max(dynamic(ind+1,v,dp,sct+1,ict),dynamic(ind+1,v,dp,sct,ict+1));
    }
    else if(v[ind]<0)
    {
        int a=0;
        if(abs(v[ind])<=sct)a=1;
        return dp[ind]=a+dynamic(ind+1,v,dp,sct,ict);
    }
    else 
    {
        int a=0;
        if(abs(v[ind])<=ict)a=1;
        return dp[ind]=a+dynamic(ind+1,v,dp,sct,ict);
    }

}
int32_t main() {
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   
        int n,m;
        cin>>n>>m;
        vector<int>v;
        vin(v,n);
        vector<int>dp(n,-1);
        int sct=0,ict=0;
        int ans=dynamic(0,v,dp,sct,ict);
        cout<<ans <<endl;

}

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.me/contest/2025/submission/287020150

why i am not able to come up with the solution of even 2nd and 3rd question contest(div2)??