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

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

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 $$$ \lt =$$$ to our current intelligence values and because all the checks with value $$$ \lt $$$ $$$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$$$.

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

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

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

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?

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

Another approach for Problem D: https://codeforces.me/contest/2025/submission/294067890

Hints:

--> when we hit a 0, we either increase strength or intelligence
        both strength and intelligence can be solved independenty and similarly
--> let say if we can pass a strength check of value sC then we can pass all strength check of values <=sC
--> let say current strength is sC, and we increase it by 1, sC = sC +1
--> then all the strength checks witth value sC +1 can be passed on the right.
     */

有人帮我c题吗？第10个答案错误

I made an other solve of E, based on basic dp, that counts amount of CBS with len i and balance j https://codeforces.me/contest/2025/submission/371918386