We use two pointers to solve this problem.

Set $$$l=1$$$ and $$$r=n$$$ initially.

• If $$$a_l=a_r$$$, l++,r--;
• If $$$a_l<a_r$$$,split $$$a_r$$$ into $$$a_r-a_l$$$ and $$$a_l$$$, r--;
• If $$$a_l>a_r$$$,split $$$a_l$$$ into $$$a_r$$$ and $$$a_l-a_r$$$, l++;

When $$$l \geq r$$$,the process ends.

Good problem! :
Average problem :
Bad problem... :

Let $$$M$$$ be the initial mass of the bus with all passengers: $$$M = w + \sum_{i = 1}^{n}{m_i}$$$. Let $$$F$$$ be the total force of the pushers, initially, $$$F=0$$$.

Imagine getting out the $$$i$$$-th passenger out of the bus, then $$$M$$$ is decreased by $$$m_i$$$, while $$$F$$$ is increased by $$$f_i$$$. Hence, $$$M - F$$$ is decreased by $$$m_i + f_i$$$. Clearly, we want to make $$$F \ge M$$$, i.e. $$$M - F \le 0$$$.

Therefore, that lead us to the greedy approach: let us sort passengers by $$$m_i + f_i$$$ in descending order and start getting the passengers out of the bus, one by one, according to their order, until the bus is able to be moved, i.e. $$$F \ge M$$$.

Good problem! :
Average problem :
Bad problem... :

$$$Hint 1$$$ : What's the minimum frequency of the most frequent character of a decimal string?

$$$Hint 2$$$ : What's the minimum size of $$$LCS$$$ between two strings of length $$$K$$$ required to make a string of size $$$19k/10$$$?

We can observe one thing that as there are only $$$\tt{10}$$$ possible different characters in a string of length $$$K$$$ then it's obvious that the frequency of the most frequent character in it is $$$\ge K/10$$$ , let's assume that character is $$$\tt{0}$$$ in the first string that we observe.All we need to solve this problem is finding a $$$LCS$$$ of size atleast $$$K/10$$$ between two strings.So we already have a string where there are $$$K/10$$$ $$$\tt{0}$$$s.Now let's observe any other $$$9$$$ strings where the most frequent characters suppose are : $$$1$$$ $$$2$$$ $$$\dots$$$ $$$9$$$ . Notice that we are assuming that there are no same characters among the first $$$10$$$ observed strings' most frequent characters co-incidentally. If there are duplicates we already have our answer. Assuming there are no duplicates in the first $$$\tt{10}$$$ observed strings, it is guaranteed the most frequent character appearing in the $$$11th$$$ string must have appeared before as there are $$$\tt{10}$$$ possible characters only.Then we have our answer , we will construct our answer by merging two strings with same most frequent character.It's basically the $$$pigeonhole$$$ principle like if we have $$$\tt{10}$$$ types of chocolates in $$$\tt{11}$$$ boxes , there has to be duplicates.So we prove that $$$11$$$ strings are enough to generate an answer , so we always have an answer as we have $$$20$$$ decimal strings

Time complexity of optimal implementation of this problem : $$$O(20 * K)$$$ , although there are $$$O(20^2 * K)$$$ solutions which may also pass which takes advantage of the fact that there has to be a pair of strings which have $$$LCS$$$ of length >= $$$K/10$$$

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
#define pb push_back
#define pf push_front
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin>>k;
    vector<string> v;
    string s;
    vector<ll> adj[10];//to store indices of string where a particular character is most frequent
    for(int i=1;i<=20;i++){
        cin>>s;
        v.push_back(s);
    }
    int l=-1;
    int r=-1;
    char aa='Z';
    for(int i=0;i<=19;i++){
        ll m[10]={};//character frequency array
        for(auto u : v[i]){
            int kk=u-'0';
            m[kk]++;
        }
        ll best=0;
        ll yy=-1;
        for(char xx='0';xx<='9';xx++){
            ll xx1=xx-'0';
            if(m[xx1]>best){
                best=m[xx1];
                ll pal=xx-'0';
                yy=pal;
            }
        }
        adj[yy].push_back(i);
        if(adj[yy].size()==2){
            aa='0';
            aa+=yy;
            l=adj[yy][0];
            r=adj[yy][1];
            break;
        }
    }
    deque<ll> v2,v3;//used for storing indices of LCS of two optimal strings
    string ans="";
    //string merging process starts
    ll kk=-1;
    for(auto u : v[l]){
        kk++;
        if(u==aa) v2.pb(kk);
    }
    v2.pf(-1);
    kk=-1;
    for(auto u : v[r]){
        kk++;
        if(u==aa) v3.pb(kk);
        
    }
    v3.pf(-1);
    for(ll aa1=1;aa1<=k/10;aa1++){
        
        for(ll bb=v2[aa1-1]+1;bb<=v2[aa1]-1;bb++){
            ans+=v[l][bb];
            
        }
        for(ll bb=v3[aa1-1]+1;bb<=v3[aa1]-1;bb++){
            ans+=v[r][bb];
            
        }
        ans+=aa;
        
    }
    for(ll aa1=v2[k/10]+1;aa1<=(k)-1;aa1++) ans+=v[l][aa1];
    for(ll aa1=v3[k/10]+1;aa1<=(k)-1;aa1++) ans+=v[r][aa1];
    cout<<ans<<endl;
    
}

Good problem! :
Average problem :
Bad problem... :

First, let's find the minimum number of the stops Rudraksh will make. There are 4 different cases. Let's say the school coordinates are $$$(x, y)$$$.

$$$1)$$$ The manhattan distance of $$$(x,y)$$$ from $$$(0,0)$$$ (means $$$x+y$$$) is itself a prime number. So we can directly jump to the school, making only one-stop.

$$$2)$$$ If the $$$x+y-2$$$ is a prime number so we should first travel distance 2 i.e any of {(1,1),(0,2),(2,0)} as per the school coordinates, and then the next stop will be the school coordinate.

$$$3)$$$ If the $$$x+y$$$ is even, then as per Goldbach Conjecture, it can be written as the sum of two prime numbers. So the stops can be determined based on that prime numbers.

$$$4)$$$ If the $$$x+y$$$ is odd, then we may move to some coordinate whose Manhattan distance is odd and that is prime (for simplicity we can use 3), too. Now this became a similar problem to type $$$3$$$.

For identifying the exact stops, you can iterate over every prime number.

Good problem! :
Average problem :
Bad problem... :

For each index $$$i$$$, $$$a_i$$$ should be the greater than or equal to the $$$k^{th}$$$ maximum element in the subarray. So, to make the subarray longest, $$$a_i$$$ should be as least as possible therefore,it should be $$$x^{th}$$$ maximum $$$(x \leq k)$$$, where $$$x$$$ should be the maximum possible value.

If $$$a_i$$$ is $$$x^{th}$$$ maximum in the subarray $$$a[l...r]$$$, then there are $$$x-1$$$ elements greater than $$$a_i$$$. Suppose there are $$$p$$$ $$$(0 \leq p \leq k-1)$$$ elements from $$$l$$$ to $$$i-1$$$, that are greater than $$$a_i$$$, then there will be $$$(x-1)-p$$$ elements greater than $$$a_i$$$ in $$$i+1$$$ to $$$r$$$ (all elements are distinct) .As $$$k \leq 10$$$, therfore for every index $$$i$$$, we can find the minimum $$$l$$$ and maximum $$$r$$$ for every $$$p$$$, and find the maximum of $$$(r-l+1)$$$, which will be our answer.

For implementing, we can use set or ordered set (policy-based data structure), and can start inserting the index of elements from $$$n$$$ to $$$1$$$, after every insertion, we can iterate $$$k$$$ indices in the set in both directions — previous the current element's index in set and after the current element's index in set.

See code for detailed implementation.

Good problem! :
Average problem :
Bad problem... :

$$$hint 1$$$ : Maximum possible score of a subsequence is $$$n$$$ as in an array of size $$$n$$$ $$$\rm{mex}$$$ can't be greater than $$$n$$$

$$$hint 2$$$ : Calculating number of subsequences where $$$score$$$ is $$$i$$$ for each $$$0 \le i \le n$$$ is enough

First let's calculate for each $$$0 \le i \le n$$$ the number of subsequences where score is $$$i$$$.How to calculate that?Well when is mex of a subsequence a positive integer $$$i$$$?How does the subsequence look like?In that subsequence there can be arbitrary integers greater than $$$i$$$ ,no appearance of $$$i$$$ and every integer from $$$\tt{0}$$$ to $$$i-1$$$ is present in the subsequence each arbitrary number of times.So if $$$f_i$$$ is the value of number of subsequences where $$$mex$$$ is $$$i$$$ , $$$f_i$$$ : $$$ 2^X * (2^{a_0}-1) * (2^{a_1}-1) * (2^{a_2}-1)* \dots * (2^{a_{i-1}}-1)$$$ where $$$X$$$ is count of elements greater than $$$i$$$ and $$$a_j$$$ is count for j in the array.If subsequence count for some $$$i$$$ crosses $$$K$$$ we minimise it to $$$K$$$.In case of $$$0$$$ : $$$f_0$$$ = $$$2^y$$$ where $$$y$$$ is count of elements greater than $$$0$$$. But we subtract $$$\tt{1}$$$ from that count as we are considering $$$non-empty$$$ subsequences only. Now when we pick and arrange $$$K$$$ subsequences it's obvious that we have to pick $$$(k+1)/2$$$ subsequences with $$$minimum$$$ scores and $$$k/2$$$ subsequences with $$$maximum$$$ scores. As the range of possible $$$scores$$$ is very low $$$[0 \dots n]$$$ we just iterate greedily from the beginning of the range to add scores of $$$odd$$$ indices and after that we iterate from the end greedily to subtract the scores of $$$even$$$ indices.

Time complexity of optimal implementation of this solution : $$$O(N)$$$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
   ios::sync_with_stdio(0);
   cin.tie(0);
   cout.tie(0);
   ll t=1;
   cin>>t;
    ll m[100002];//subsequence count array
    ll m2[100002]={};//frequency array
    ll fact[100002];//array for storing values of 2^i
    for(int j=1;j<=t;j++){
        ll n,k;
        cin>>n>>k;
        ll i,x;
        vector<ll> v;
        fact[0]=1;
        m2[0]=0;
        for(i=1;i<=n;i++){
            m2[i]=0;
            fact[i]=fact[i-1];
            fact[i]*=2;
            fact[i]=min(fact[i],k+1);
        }
        ll sum=0;
        for(i=1;i<=n;i++){
            cin>>x;
            if(x<=n) m2[x]++;
        }
        sum=n;
        ll dal=1;
        for(ll i=0;i<=n;i++){
            m[i]=dal;
            sum-=m2[i];
            m[i]*=fact[sum];
            if(i==0) m[i]-=1;
            m[i]=min(m[i],k);
            dal*=(fact[m2[i]]-1);
            dal=min(dal,k+1);
        }
        ll ans=0;
        ll jh=(k+1)/2; // odd
        ll jk=k/2; // even
        for(i=0;i<=n;i++){
            ll kk=min(m[i],jh);
            ans+=(i*kk);
            jh-=kk;
            m[i]-=kk;
        }
        for(i=n;i>=0;i-=1){
            ll kk=min(m[i],jk);
            ans-=(i*kk);
            jk-=kk;
            m[i]-=kk;
        }
        cout<<ans<<endl;
        }
}

Good problem! :
Average problem :
Bad problem... :