W contest, W editorial!

Is there any way to determine the difficulty rating of recently asked contest problems? Any guidance on this would be greatly appreciated.(Any extension ?)

whats the motivation behind problem-C, i was blank after reading the problem. Any tips for such problem.

I created a blog discussing an alternate $$$O(n \cdot log(n))$$$ solution for D: Invertible Bracket Sequence. If you want to test your understanding of this conept, I also created some practice problems

Loved C

Alternative DP solution to F:

The problem choose the largest connected set of edges that has exactly $$$k$$$ leaves and contains the root can be solved with DP. Let $$$\mathrm{dp}_{i, j}$$$ be the answer for the subtree rooted at $$$i$$$, when taking exactly $$$j$$$ leaves. The transitions are straightforward — same as in knapsack. This gives us a $$$\mathcal{O}(n^2)$$$ solution.

Notice that the sequence $$$(\mathrm{dp}_{i, 0}, \mathrm{dp}_{i, 1}, \dots)$$$ is always concave for a fixed $$$i$$$. This can be easily proven with induction — the sequence in leaves is concave, and the max-plus convolution of two concave sequences is also concave. This gives us a faster solution. Instead of storing the DP directly, store the adjacent differences (they will always be sorted in non-increasing order). Then, we can use small-to-large merging, which gives us $$$\mathcal{O}(n \log^2 n)$$$ complexity.

More about max-plus convolution

Submission

I couldn't figure out how to implement the range condition of balance[i] <= 2 * balance[l — 1] bit, later figured some people used data structures to check if the max of the range is lesser than 2 * balance[l — 1].

But I must say that the simple map implementation is the best I have seen in two days, how did you even come up with that?

Nice contest ! Thanks for this nice editorial

Can someone explain why the time complexity of the solution for problem D is O(nlogn). Like how the while loop is taking logn time only. I can visualize it somehow but I can't prove it.

Can anyone tell me why does my O(n) solution fail for problem C

263511839

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll bucket[200100];
int main()
{
    int z;
    cin >> z;
    while(z--){
		string s;
		cin >> s;
		ll n = s.size(), ans = 0, potential = 0;
		memset(bucket, 0, sizeof(ll) * (n/2 + 5));
		for(ll i=0; i<n; i++) {
			potential += (s[i] == '(' ? 1: -1);
			ans += bucket[potential];
			bucket[potential] ++;
			if(potential & 1ll) bucket[potential/2] = 0;
		}
		cout << ans << '\n';
    }
 	return 0;
}

UPD: I compressed my code further and I'm surprised to find that I now have the shortest correct solution for the problem.

In problem F, how to prove greedy is correct?

Why does this code gives TLE? As far as I know it is clearly O(nlogn).

263649473

For Problem F, instead of the implementation idea mentioned in the editorial, if we simply brute force (i.e. when we take the longest path, simply update the distances of all leaves whose edge numbers decrease), what would be the complexity? I am struggling to find a construction that makes the number of updates worse than O(N^1.5)

In D tutorial can someone explain these lines? I couldnt get it:

"Luckily, it is easy to fix, if the current balance balr and there is balance x in the map such that x<balr−x , we can remove all its occurrences from the map (i. e. remove the key x from the map). This fix works because the current position lies between the left border (which we store in the map) and the potential right border, and the current balance is too high (which violates the first condition)."

Amazing E problem, thank you BledDest !

Just got this e-mail that plague has been detected in my code and I am genuinely so confused. My solution for D problem is only slightly similar to one random guy's solution!? This contest was a huge rating boost for me. Please review this 263359271 This is my submission and the following is the other guy's submission: 263354669 MikeMirzayanov

I think in the editorial of B, in the first point we should increase a[i] to b[n+1] instead of a[n+1] to b[n+1] because a's size is n only.

Can anyone point out my mistake in this solution for C, I am not able to figure out where am i going wrong. I has implement in exactly same way as given in the editorial.

Submission Link: https://mirror.codeforces.com/contest/1976/submission/283706262

can someone tell me why is this wrong?

~~~~~~~~~~

void solve(){

ll n,m;cin>>n>>m;

vll ps(n+m+1);ai(ps,n+m+1);

vll ts(n+m+1);ai(ts,n+m+1);

sll prog,test;

ll ans=0;
vll vecans;

for(int i=1;i<n+m+1;i++){
    if(ps[i]>ts[i]){
        if(prog.size()==n){
            test.insert(i);
            ans+=ts[i];
        }else{
            prog.insert(i);
            ans+=ps[i];
        }
    }else{
        if(test.size()==m){
            prog.insert(i);
            ans+=ps[i];
        }else{
            test.insert(i);
            ans+=ts[i];
        }
    }
}
vecans.pb(ans);
// cout<<ans<<"\n";

for(int i=1;i<n+m+1;i++){
    if(prog.find(i)!=prog.end()){
        ans-=ps[i];
        prog.erase(i);
    }else{
        ans-=ts[i];
        test.erase(i);
    }

    if(ps[i-1]>ts[i-1]){
        prog.insert(i-1);
        ans+=ps[i-1];
    }else{
        test.insert(i-1);
        ans+=ts[i-1];
    }

    if(prog.size()==n){
        vecans.pb(ans);
    }else{
        if(prog.size()>n){
            auto it=*prog.rbegin();
            ans-=ps[it];
            ans+=ts[it];
            prog.erase(it);
            test.insert(it);
        }else {
            auto it=*test.rbegin();
            ans-=ts[it];
            ans+=ps[it];
            test.erase(it);
            prog.insert(it);
        }
        vecans.pb(ans);
    }
}

printvec(vecans);

}

~~~~~~~~~~~~

I felt that the subintervals intuitively pushed for DP and prefixes on D, here's a DP solution to that.