Random guy : **complains about previous contest in comments**

Community: So,you have chosen death?!

Random Guy: *complains about previous contest in comments*

CF-Community: So,you have chosen death?!

not gonna lie, this comment section is already sh*t.

If govt. was the CF community and the people who posted a comment were protesters.

What if someone says that this round is harder than the previous one? Would everyone quit giving it? That depends on us the participants how the round is. And this website is a source of giving us the idea in which topic you lag behind. So lets find and give every round a full shot as if its only created for you. Lets enjoy the process!

Всем удачи на этом соревновании

People in comment section are hiding own weakness by giving other blame.

mynameJEFF

Is m2.codeforces.com not working?

Summary of this blog comment section: The comment is hidden because of too negative feedback, click here to view it.

Downvote is coming :)

My stupid WA on C took expert from me :'(

I don't know why I get demotivated. Please help me with B and C after the contest

Tbh, E was easier than B

The order of problem B and C should be exchanged.

In problem E, Basically we have to found the number of pairs such that

(x + d * y) % w == (y + d * x) % w

How will we reduce this expression?

How to solve F?

How to solve D? Isn't the greedy approach enough?

How to solve D?

How to solve D ?

Can someone please tell me why this solution is wrong for C :

void solve(){
    string s;
    cin>>s;
    int n=sz(s);
    int ans=2e5;
    for(char a='0';a<='9';a++)
        for(char b='0';b<='9';b++){
                int turn=0,cnt=0;
            for(auto x:s){
                if(x==a && turn==0){
                    turn=(turn+1)%2;
                    cnt++;
                }
                else if(x==b && turn==1){
                    turn=(turn+1)%2;
                    cnt++;
                }
            }
            if(cnt%2==1)
                cnt--;
            ans=min(ans,n-cnt);
        }
        cout<<ans;
}

UPD :

if(cnt%2==1 && a!=b) 
   cnt--;

I see many people solved $$$C$$$ without $$$DP$$$, how to do it without $$$DP$$$ ?

B was very uninteresting!! Rest problems were nice.

In B, i cried

Nice Contest.Thanks, CodeForces, for the contest...

Keep these good initiatives coming...

Whoever came up with input format for problem G, please don't do that again.

Spent all my time on B, and literally solved C one minute after the contest ended. I tried to solve C first, but my mind was so stuck on B , couldn't solve C unless I solved B. Took 1 hour to solve B. Gonna lose rating but enjoyed the contest.

ll rec(ll idx, ll moves, ll lmoves, vector<ll>& arr, vector<ll>& psum, vector< vector< vector<ll> > >& dp){
    if(moves == 0){
        return 0;
    }
    if(lmoves == 0){
        return psum[min(idx + moves,(ll)arr.size()-1)] - psum[idx];
    }
    if(dp[idx][moves][lmoves] != -1){
        return dp[idx][moves][lmoves];
    }
    ll ans = 0;
    if(idx + 1 < arr.size()){
        ll v1 = arr[idx+1] + rec(idx + 1,moves-1,lmoves,arr,psum,dp);
        ans = v1;
    }
    if(idx - 1 >= 0){
        ll v2 = arr[idx-1] + rec(idx - 1,moves-1,lmoves-1,arr,psum,dp);
        ans = max(ans,v2);
    }
    dp[idx][moves][lmoves] = ans;
    return ans;
}

How do I reduce space complexity of this DP solution for B ?

what's wrong with a solution for B that does the following:

take all M elements first and then for each i in m, remove the last element and add arr[i-1] then remove the new last element and add arr[i] and then arr[i-1] again and so on until we can't do any extra moves for K, and take the maximium answer.

Problemset was better than previous contest. I enjoyed it :) . Today, B no. was interesting at first look. But most of us missed counter cases in first trial. C no. was easier than B.

Problemset was better than previous contest. I enjoyed it :) . Today, B no. was interesting at first look. But most of us missed counter cases in first trial. C no. was easier than B.

I read the code of A. Why if( L * 2 <= R)? Why not use the LCM function? What is the key point of this problem?

Can anyone tell where I am wrong in C? I checked for max possible alternate (121212 type) and also for element with max frequency(eg 56555)

        string x;
    cin >> x;
            ll n=x.size();
    map<char, ll>m;
    map<ll, ll>odd;
    map<ll, ll>even;
    int flag = 1;
    for (int i = 0; i < x.size(); i++)
    {
       if (i % 2 == 0)
       {
         odd[x[i]]++;
       }
       else
       {
         even[x[i]]++;
       }
       m[x[i]]++;
       if (m[x[i]] == n)
       {
         cout << "0" << endl;
         flag = 0;
       }
    }
    ll maxele = 0;
    for (auto it = m.begin(); it != m.end(); it++)
    {
       maxele = max(it->second, maxele);
    }
    if (flag) {
       ll maxodd = 0, maxeven = 0;
       for (auto it = odd.begin(); it != odd.end(); it++)
       {
         maxodd = max(it->second, maxodd);
       }
       for (auto it = even.begin(); it != even.end(); it++)
       {
         maxeven = max(it->second, maxeven);
       }
       if (maxeven == n || maxodd == n)
       {
         cout << "0" << endl;
       }
       else
       {
         ll maxi = min(maxodd, maxeven) * 2;
         cout << min(x.size() - maxele, x.size() - maxi) << endl;
       }
    }

Problem B:

![ ]()

Really, what goes through people's heads when they message others like this during the contest....

Best Educational Round EVER!!

Can anyone tell why this is giving TLE on test case 2 ( Problem B ) ? https://mirror.codeforces.com/contest/1389/submission/88360778 Thanks in advance

Does D have a more elegant solution than lots of nested ifs?

What's wrong with my this solution for problem C ? Please provide any counter case .

I tried to solve problem B with 3d DP but I failed. The three states that I think needed are dp[number of moves done][whether the current element taken in forward move or backward][number of backward moves done] , also I used pair<int,int> dp to store the index where we are now. But still got the wrong answer, can anyone help me how to solve this problem B with DP using the states that I've used? Or if you have any 3d DP solution can you explain?

I am very demotivated... where is button to delete account?****

![ ]()

Could Someone tell my mistake in B? This has happened to a lot of people in B (Test case 2 failed, 19th number differs). That very specific number. Some people figured it out. My submission is: 88310231

Thanks in advance!

B was like a hell... AGC B?

Hints for B, please.

In problem C, I selected "two" most occurring digits present in String, let's call them A and B and their frequencies be F_A and F_B (F_A >= F_B) and I removed the rest of the integers, let's call Sum of these remove integers be X. Now in this New String I counted number of pairs of type AB and BA and at the end final result should be X + min( new_string_length - 2* max(#AB,#BA) , F_B), right ?

But I got the wrong answer on test 2. I am not able to figure out what is wrong in my approach. Please help.

Solution for D:

At first lets calculate how much more we need "intersection_length". Call it need. If (need <= 0) then print(0)

else

Lets for basic pair of segment calculate number of steps required that the segments touch each other.Call it cost.

And for basic pair of segment calculate number of steps required to make the segments are equal.Call it kol.

Then, fo basic segments maximal number of steps, that will gives us +1 to "intersection_length" in one step is kol — cost. Call it add.

Now, lets iterate over i-th pair of segments, while need > 0 At first we need to make this segments contiguous, then add to answer cost. Now, let`s add to answer min(**kol**, need), and substract kol from need.

Also we need consider one case:

When need <= kol, and we already have identical segments, is can be better for us, if do next steps on current pair of segments. I.e if need <= kol, answer += min(need * 2, cost + need)

If need > 0 and we went through all the segments, Then each pair of segment(L, R) equal to L = min(l1, l2), R = max(l2, r2).(l1, l2, r1, r2 from text of D) Each that pair can add "intersection_length" only after two steps. Therefore, we need add to answer 2 * need.

С++ code

Can anyone tell why my soln for B fails???

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;

main(){
    int t;cin>>t;
    while(t--){
        int n,k,z;cin>>n>>k>>z;
        int a[n];
        int maxpos=1;
        cin>>a[0];
        ll score=a[0],maxpair=-1;
        for(int i=1;i<n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=k;i++){
            if((a[i]+a[i-1]) >= maxpair){
                maxpos = i;
                maxpair = (a[i]+a[i-1]);
            }
        }
        for(int i=1;i<=maxpos;i++){
            score+= a[i];
            k--;
            if(k<=0) break;
        }
        int curr = maxpos;
        while(z>0 && k>0){
            if(curr == maxpos){
                curr--;
                score+= a[curr];
                z--;k--;
            }
            else{
                curr++;
                score+= a[curr];
                k--;
            }
        }
        curr++;
        while(k>0 && curr<n){
            score+= a[curr];
            curr++;
            k--;
        }
        cout<<score<<"\n";
    }
}

Can anybody tell where is this approach failing in C question?

Your code here...

from collections import defaultdict as dd
for _ in range(int(input()):
    s=input().strip()
    d=dd(list);d1=dd(int)
    n=len(s)
    for i in range(n):
        d[s[i]]+=[i]
        d1[s[i]]+=1
    ans=max(d1.values())
    if(ans%2==1):ans-=1
    l=list(d.keys())
    for i in l:
        for j in l:
            if(i!=j):
                l1=d[i]+d[j]
                l1.sort()
                curr=i
                te=1
                p=l1.index(d[i][0])
                for k in l1[p+1:]:
                    if(s[k]==curr):continue
                    else:
                        te+=1
                        if(curr==i):curr=j
                        else:curr=i
                if(te%2==1):te-=1
                ans=max(ans,te)
                l1=[]
    print(n-ans)
                    
              

Amazing round. Really enjoyed these problems. Thank you :D

Can someone please help me with B. My approach is --> find the prefix sum and the max adjacent sum till current index and then start from kth element and find the max answer. https://mirror.codeforces.com/contest/1389/submission/88373889

In problem D I thought by mistake that it's all the intersections between all pairs of segments (i.e. n**2 intersections) :<<< (At the end I noticed it and I just now, an hour after the contest was over, submitted the correct answer...). I should read more carefully. meh.

It made it much harder...
I was sure I was on the right path because there were all these nice formulas coming up. For example, if all segments in both sides are now the same (that's the first step) then you start building the intersections one at a time. You first add 1 in one of the segments in a, then add 1 in one of the segments in b, then another one in a... It creates the formula 0+1+1+2+2+3+3+4.... which at an even index 2*i, the sum is i**2, and at odd index 2*i+1, its 2(1+2+...)=i(i+1). So you can get the minimum i between the two options that achieves k.

That was just a taste as there are plenty more cases I had to think of etc...