G is pretty amazing and educational.

where can i find problems similar to D which don't scream DP but are/

Missing editorial for F btw

I was looking forward to editorial of F,please post it.

Fast Editorial! Nice!

D is a beautiful problem, but can we do better than $$$O(N^4)$$$. Overall B > C. I think E is solvable by SegBeats thought its overkill and I am getting TLE. Binary search with Segtree also Works

F is made easier by the fact that the greedy is correct (since $$$x$$$ and $$$x + 1$$$ can't both be trapped at the same time, it is optimal to advance whenever possible).

However, we can solve a more general version of the problem where there is no greedy, for example when instead of losing if $$$x$$$ mod $$$a_t = b_t$$$ at time $$$t$$$, we lose if $$$x$$$ mod $$$a_t \in B_t$$$ with $$$B_t$$$ a subset of $$$[0, 1, ..., a_t - 1]$$$.

For $$$m \lt = LCM$$$, we can simply run a classic $$$dp[LCM][n]$$$ to find the minimum distance from $$$(0, 0)$$$ to any state. For bigger $$$m$$$ however, we need to go through the torus multiple times (since the dp is cyclic in both variables, the graph looks like a torus).

For that, we can run the dp once to find the min distance from $$$(0, 0)$$$ to $$$(LCM, t)$$$ for each $$$t$$$, then run the dp again this time starting from $$$(0, 1)$$$, $$$(0, 2)$$$, and so on, until we have all minimum distances between $$$(0, i)$$$ and $$$(LCM, j)$$$ for $$$0 \leqslant i, j, \lt n$$$.

Once we have this $$$n * n$$$ matrix, it allows us to connect the start of the torus to its end, and all we need to do is to exponentiate it to the power $$$m / LCM$$$, and run the dp one final time to go through the last $$$m$$$ mod $$$LCM$$$ steps.

Time complexity : $$$O(n^2LCM + n^3log(m))$$$

Can anyone explain why order doesn't matter in problem B?

D can be brute forced for n<80 in python (probably much higher in C++).

If you have answer for all k for a given n, you can find a valid answer for all k which have a valid solution for n+1 by just brute forcing n+1 at every possible position in answer for every k for n then compute the k for that permutation. Given how low the constraints are this will work just fine.

def calc_inversions(arr):
    ans = 0
    curr = 1
    for i in range(1, len(arr)):
        if arr[i] < arr[i-1]:
            ans += curr * (curr - 1) // 2
            curr = 1
        else:
            curr += 1
    ans += curr * (curr - 1) // 2
    ans = len(arr) * (len(arr) - 1) // 2 - ans
    return ans

n = 79

ans = [[None for _ in range(i*(i-1)//2 + 1)] for i in range(n+1)]

ans[2][0] = [1,2]
ans[2][1] = [2,1]

for n in range(3, n+1):
    for j in range((n-1)*(n-2)//2 + 1):
        curr = ans[n-1][j]
        if curr == None:
            continue
        for i in range(n+1):
            new = curr[:i] + [n] + curr[i:]
            k = calc_inversions(new)
            if ans[n][k] == None:
                ans[n][k] = new


for _ in range(int(input())):
    n, k = map(int, input().split())
    x = ans[n][k]
    if x == None:
        print(0)
    else:
        print(*x)

I don't understand D T_T. How do people come up with this shi

stupid 4 pointer idea for B 342285913

Why is $$$n + m - \min(x, y)$$$ the number of operations for problem G?

Isn't it best to select the smallest one if there are $$$x$$$ rows and $$$y$$$ cols with color 1? The number of operations required, in my opinion, is $$$n + m - x - y + \min(x, y) = n + m - \max(x, y)$$$.

Can please anyone explain why this one passes the sample case but fails on test 2, is it my approach is wrong or I missed the edge cases? for C:

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define endl '\n'

void fastio() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int32_t main() {
    fastio();

    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        string s;
        cin>>s;
        int ta=0,tb=0;

        for(int i=0;i<n;i++){
            if(s[i]=='a')ta++;

            else tb++;
        }

if(ta>tb){

    
priority_queue<int> pq;
stack<int> st;

for(int i=0;i<n;i++){

if(s[i]=='a' && i!=(n-1)){
st.push(i);
}

else{
    pq.push(st.size());
    if(!st.empty()){
    st.pop();
    }
}
}

if(pq.top()<abs(ta-tb)){
    cout<<"-1"<<endl;
}

else{
    cout<<abs(ta-tb)<<endl;
}

}


if(ta<tb){

priority_queue<int> pq;
stack<int> st;

for(int i=0;i<n;i++){

if(s[i]=='b' &&  i!=(n-1)){
st.push(i);
}

else{
    pq.push(st.size());
    if(!st.empty()){
    st.pop();
    }
}
}

if(pq.top()<abs(ta-tb)){
    cout<<"-1"<<endl;
}

else{
    cout<<abs(ta-tb)<<endl;
}

}

if(ta==tb){
    cout<<"0"<<endl;
}
    }

    return 0;
}

I think problem B can be solved by Brute-Force and Deque data structure. Because the bottom card removal operation can cost O(n)(remove arr[0] in array ) and repeating it many times like that can make the complexity O(n^2) and it will be TLE. We can solve this problem by Deque which makes the bottom card removal only have complexity O(n) and helps the complexity of the code from O(n^2) to O(n)

This is just a suggestion on the solution of problem B improved from Brute-Force, please do not downvote me

There should be modification in solution of D!

We have to fill up dp & p earlier not in the loop as it will give TLE. I tried solution of editorial its giving TLE. But, if you calculate it earlier then it will work.

"There are other ways to solve this problem, for example, with functional graph cycle detection or fast matrix exponentiation, but in my opinion, this approach is the easiest to implement."

What would the functional graph cycle detection solution be like?

I had similar key idea for D, but with little bit different implementation. Our final permutation (if it exists) consists of several sorted segments with various length. Each of them contribute final answer by minus n*(n-1)/2, so we need to find segments whose sum equal to n*(n-1)/2 — k. Thus we can use knapsack dp to brute force all possible length and find their numbers and length. It will look like dp[i][1][2][3]...[30] right from 1 to n, i represent sum and left 30 numbers are counters of segments with length of its corresponding index. The transition is simple, just like in an ordinary knapsack, taking value from dp[i-op] and changing all its numbers with adding +1 to chosen length. Oh and dp itself is the sum of the length of the taken. So in the last step we just check whether dp[n*(n-1)/2 — k][0] is less or equal than n, and building permutation just like in editorial. Link Here is submission for more details.

It is sad that there is no interactive problem in this contest :(

Could someone clarify what the editorial author meant when they said "Iterate over K — the length of the next sorted block"?

Can someone please tell what was wrong with my solution in "problem C" as I use d the same concept , stored all the consecutive a's and b's in map and as we know we can only remove once hence I found the difference between their counts and tried to find if it is present in the map.

#include<bits/stdc++.h>
using namespace std;
 
 
int solve()
{
    int ans = 0;
 
    int n;
    cin>>n;
    string s;
    cin>>s;
 
 
    //Use the concept of prefix sum here
    //  use map to store them 
    unordered_map<int,int> mpp_a;
    unordered_map<int,int> mpp_b;
int c_a = 0;//total count of a
int c_b = 0; //total count of b
if(s[0]=='b')   c_b++;
else   c_a++;
int count  = 1;

    for(int i=1;i<n;i++)
    {
    if(s[i-1]==s[i])
    {
        if(s[i]=='b')
        {
            c_b++;
count++;
        }
        else{
            c_a++;
            count++;
        }
    }
    else{
        if(s[i]=='b')
        {
            c_b++;
mpp_a.insert({count,-1});
count=0;

        }
        else{
            c_a++;
mpp_b.insert({count,-1});   //Here we find the consecutive sequence ends and hence  I append it to map
count=0;
        }
    }
    }
 
    //Precomputing done
if(c_a>c_b)
{
    int diff = c_a &mdash; c_b;
if(mpp_a.find(diff)!=mpp_a.end())
{
   return diff;
}
else{
    return -1;
}
}
else{
int diff = c_b &mdash; c_a;
if(mpp_b.find(diff)!=mpp_b.end())
{
   return diff;
}
else{
    return -1;
}
}
 
return -1;
}
 
 
int main()
{
int t;
cin>>t;
 
while(t--)
{
cout<<solve()<<"\n";
}
 
    return 0;
}

Just realize, the DP in G is just ordered $$$k-1$$$ partitions of a set with $$$ n-x+m-y $$$ elements.

set partitions could be calculated recursive in $$$O(n^2)$$$: $$$ part(n, k) = part(n-1, k-1)+k*part(n-1, k) $$$

Very educational~

Can someone guide me on how to approach generation based problems? For example, Question D in this contest, where you are asked to generate an array that satisfies certain conditions. How should I approach these types of problems? If it’s too much to explain in a comment, a link to a post or tutorial would be appreciated.

Why greedy doesn't work on D?

Hello, I received a message that my submission (342267062) coincides with submission 342268142 from another account. Both accounts (Mim5270 and akthermim) actually belong to me. I understand now that having multiple accounts and submitting the same solution was a mistake — I did not intend to break any rules or gain an unfair advantage. I sincerely apologize for the violation and assure you it won’t happen again. Please consider this my explanation. I will only use one account from now on. Thank you for your understanding.

My 342314871 for D without any DP (there is dp in my code but its just (i * (i — 1)) / 2)

I'm using brute force and check all possible set of length's for increasing subsegments.

Here is a soltion to solve problem 2145D - Inversion Value of a Permutation without using DP.

First,transform the problem meaning in the same way as the solution. We need to select some items which has $$$i$$$ value and $$$i+1 \choose 2$$$ weight and make the sum of value equal n and the sum of weight equal k.

Second,to do this,we have noticed the partition of $$$30$$$ is less than $$$6000$$$! So we can just use the brute force to solve this problem.

342894423

Can someone tell me what is wrong with this code 349836610 for problem D

i got WA on this testcase:

1 5 10

but when i ran it has the right output

2145C is a very good ques , it seems like easy on first go. but it quite different to think on first hand while u are writing code their are two -1 testcases wont work , it took around 2 hours for the whole code but took 5-6 hours of effort to deal with that -1 testcase :(. but it was worth the time

In F,the "at the end of moves",is it mean "at the end of turns"?

Nice and elegant solution for D. But I'm lacking intuition why is it possible to construct any number using sum of $$$\frac{i_1*(i_1-1)}{2}+\frac{i_2*(i_2-1)}{2}+...$$$ and if it's not possible, then why are we certain that it's not possible to construct the answer in other way than in the editorial?

B is dog shit