first.

Time to go back to pupil again XD

Man really that B was much more difficult than C Like literally I took 1hr to think about B but only 5mins to get the idea of C and solve it

I think you should do this next time: swap(B,C);

It would be fun

For C problem I used dequeue to solve it! Any better way?

Pupil I am here

I couldn't figure out how to implement B

nice contest it's very beautiful problems i am happy in here

First time I have solved 3 problems in a div2!

I really enjoyed B. Very fun question, brought me so much joy

For D simple hint Only consecutive value pairs (i, i+1) can violate the constraint. Store positions of each value, then for each pair, check if value i appears before i+1. When found, greedily remove the rightmost occurrence of i+1 to maintain maximum flexibility. This greedy approach works in O(n) time

Can you add spoilers for each problem

Well, that's one fast editorial, thanks for the effort!

Boring B but happy to be able to solve it

for D there is a very simple greedy solution 346684700. consider the graph where numbers are connected if they form a violating pair. we need to delete a minimum vertex cover in this graph. as the graph is bipartite, the minimum vertex cover size is equal to the maximum matching size by König's theorem. after that, it is pretty easy to see that maximum matching in this graph can be found greedily. consider the smallest value $$$x$$$ in the array. if there are multiple, consider the rightmost one. say, it's position is $$$i$$$. this vertex is only connected to vertices with value $$$x+1$$$ that have indices $$$j \gt i$$$. it is now easy to see that if we consider the maximum matching, we can adjust it slightly to ensure that $$$i$$$ is connected to the maximum $$$j$$$ with value $$$x+1$$$. therefore, we just repeat this greedy procedure of taking the right-most value $$$i$$$ and matching it to the rightmost value $$$i+1$$$ if possible.

for B, how is the answer YES for this ?

[# . #]

[# . #]

[# . #]

tourist always come back

there is basically no editorial for the first three problems. this is a big issue in general on codeforces. ease problems seem obvious to the contest authors, and it is hard for them to emphasize with lower-rated participants. by saying "it is easy to see" you are robbing the beginner contestants from learing how to prove their solutions. people see this phrase being used all the time and just assume that problemsolving is about guessing the solution rather than proving it. the worst example is problem B. it is not easy to see that these are all possible shapes! it requires a proof. and reading such a proof would be extremely beneficial for some.

tourist on top again.

In Problem B, in my first submission(WA on test case 2 -> 150th input) i checked the conditions for the first black cell in column major order, in my second submission(AC) i checked conditions for every cell(white or black) and it got accepted. Can someone help me to find which testcase my first submission fails.

Though problem D is tagged with DP, data structures, and binary search, the solution by ksun48 was genius! He solved it using a clever greedy approach https://mirror.codeforces.com/contest/2161/submission/346675405. So simple and impressive!

B is much more harder than C....

For D solution, I think it is worth mentioning that $$$dp[i]$$$ means max we can keep until $$$i$$$ while keeping the element $$$b[i]$$$ itself.

thanks for superfast editorial but still struggling to understand DP for D !!! :(

In C, it would’ve been funnier if array a weren’t bounded by X. The solution is simply to take modulo X and do the same thing.

I don't think this was an intended solution, but I think it's a good one nonetheless, and it passed in 200ms(Maybe faster, but I use extra stuff).

https://mirror.codeforces.com/contest/2161/submission/346714483

For problem $$$D$$$, Claim : For each value $$$x$$$, in the optimal solution we only remove a prefix and a suffix from $$$pos[x]$$$ (where $$$pos[x]$$$ stores all indices having value $$$x$$$.)

Proof : Removing an element $$$x$$$ from the array is equivalent to deleting its index from $$$pos[x]$$$. Consider the smallest value $$$x$$$ in the array. Suppose it appears $$$k$$$ times and we remove $$$r$$$ of them in the optima solution. Note that we shall remove smallest positions ,if we remove any non-prefix elements, a smaller index of $$$x$$$ may occur before some occurrence of $$$x + 1$$$ , hence greedily we shall remove only the prefix of them i.e. smallest $$$r$$$ positions from $$$pox[x]$$$.

Now for $$$x + 1$$$, to keep all remaining $$$x$$$ after it, we must remove some largest positions (suffix) from $$$pos[x + 1]$$$. From here all the violations between $$$x$$$ and $$$x + 1$$$ are taken care of. Now we need to take care from $$$x + 1$$$ to remaining , and again by similar reasoning as earlier we would remove a prefix of $$$pos[x + 1]$$$ and continue in the same manner. Thus, each $$$pos[x]$$$ loses elements only from its prefix and suffix.

one of the toughest contest for me till now...

https://mirror.codeforces.com/contest/2161/submission/346696450 why is this submission wrong for B? Can someone please point out the flaw in this.

Please someone check my code of problem B . it gives wrong answer in test 3 . But I can.t find my wrong and is it logical or any syntaxial wrong ? ~~~~~

include <bits/stdc++.h>

using namespace std;

define ll long long

define endl "\n"

define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);

define pb push_back

using vl=vector;

define vvl vector

define asort(v) sort(v.begin(),v.end())

define dsort(v) sort(v.rbegin(),v.rend())

define pll pair<ll,ll>

define vpl vector

define rev(v) reverse (v.begin(),v.end());

define upb(vec, val) ((upper_bound((vec).begin(), (vec).end(), (val))) — (vec).begin())

define lwb(vec, val) ((lower_bound((vec).begin(), (vec).end(), (val))) — (vec).begin())

define sl set

define spl set

define in insert

define c1 __builtin_popcountll

vpl dir={{1,0},{0,1},{-1,0},{0,-1}};

ll n;

void dfs(vector&g,vvl &vis,ll i,ll j){

vis[i][j]=1;

for(ll k=0;k<4;k++){
    ll x=i+dir[k].first, y=j+dir[k].second;

    if(x>=0 && x<n && y>=0 && y<n && !vis[x][y] && g[x][y]=='#'){
        dfs(g,vis,x,y);
    }
}

}

ll check(vector&g,vector<vector>&tmp , ll n){ for(ll i=0;i<n;i++){ for(ll j=0;j<n;j++){ if(g[i][j]=='#' && tmp[i][j]=='.') return 0; } }

return 1;

}

int main() { fast_io;

ll t;
cin>>t;
while(t--){

   cin>>n;

   vector<string>g(n);

   for(auto &d:g) cin>>d;

   ll f=1;

   for(ll i=0;i<n && f ;i++){

    ll cnt=0;

    for(ll j=0;j<n && f ;j++){

        if(g[i][j]=='.'){

            if(cnt>=3){
                f=0;
                break;
            }

            cnt=0;
        }

        else cnt++;
    }

    if(cnt>=3){
        f=0;
        break;
    }
   }


   for(ll i=0;i<n && f ;i++){
      ll cnt=0;
    for(ll j=0;j<n && f ;j++){
        if(g[j][i]=='.'){
            if(cnt>=3){
                f=0;
                break;
            }

            cnt=0;
        }

        else cnt++;
    }
    if(cnt>=3){
        f=0;
        break;
    }
   }

   if(!f){
    cout<<"NO"<<endl;
    continue;
   }


   ll com=0;
   vector<vl>vis(n,vl(n,0));

   for(ll i=0;i<n;i++){
    for(ll j=0;j<n;j++){
        if(g[i][j]=='#' && !vis[i][j]){
            com++;
            dfs(g,vis,i,j);
        }
    }
   }

   if(com<2){
    cout<<"YES"<<endl;
    continue;
   }

   ll ans=0;

   vector<vector<char>>tmp(n,vector<char>(n,'.'));

   for(ll i=0;i<n;i++){
        tmp[i][i]='#';
        if(i+1<n)tmp[i][i+1]='#';
   }

   if(check(g,tmp,n))ans=1;

   for(auto &d:tmp)rev(d);
   if(check(g,tmp,n))ans=1;

   rev(tmp);
   if(check(g,tmp,n))ans=1;


   for(auto &d:tmp)rev(d);
   if(check(g,tmp,n))ans=1;



   if(ans) cout<<"YES"<<endl;
   else cout<<"NO"<<endl;


}
return 0;

}

~~~~~

Please, someone check my code of problem B . it gives wrong answer in test 3 . But I can.t find my wrong and is it logical or any syntaxial wrong ?

https://mirror.codeforces.com/contest/2161/submission/346779118

i thought that B can be solve with dfs :(

For problem D, there is another solution using dp. dp[i][j] is showing answer for values 1, .. i in array and if the first time when we not delete i is i's jth position. We can keep it when there are no i — 1 behind it. So for every a[i] we will keep first a[i] — 1 after it. And if the first a[i] — 1 is j or bigger than j we can use a[i]. This es my implementation 346766931

For problem C:

The best possible answer that we can achieve is obtaining bonus points for purchasing $$$\lfloor\frac{\sum a_i}{X}\rfloor$$$ of the most expensive items. And this number of bonus points always can be reached.

This is wrong, consider $$$a = [4, 1],\ X=2$$$. I guess this mistake could've been caught if the solution description was more formal itself (as mentioned above by peltorator). Would be great if someone can fix it.

how much time it gonna take to reach up to that thinking level ;)

Endagorion For problem $$$E$$$, the period length is supposed to be $$$K-1$$$. It is mentioned as $$$K$$$ in the editorial. Subsequently, the conditions should be changed to $$$s_j = s_{j-k+1}$$$ for all $$$j \gt l + k - 1$$$.

I think Problem B was much harder than regular problem B's

Struggling to see where the inspiration for D's solution might come from. Perhaps I haven't solved enough hard DP problems to build the intuition yet?

Can you please explain problem D solution. Tried to understand others solution as well, unable to understand the logic of dp.

In E, there is this line "s[j]=s[j-k] for all j>l+k". However, I believe it should be s[j]=s[j-k+1] for all j>=l+k, because this ensures that d[j+1,j+k-1]=0 for all j>=l so the substring [j,j+k-1] is always good. I am not sure if my belief is wrong.

Does anyone know what testcase 76 in 'test2' is? I'm failing only because of that specific testcase. for the question B

For problem F,after reading I feel a little awkward Is the editorial discussing all about the weighted tree version,which is strictly harder than the unweighted tree version?