I also dislike it a lot, the solution is very obvious immediately. After reading for 20 seconds, you just have to implement "longest path from each vertex in a tree" which is boring.

It's ok I guess. I don't think the solution is too interesting, but it seems fine for an easy problem and isn't tedious to implement.

I like it quite a bit (other than that it uses floats, and the fact that the output says "output the maximum possible mean" which I think is an accident).

The proof that you can indeed make all the elements exactly equal to the mean of the whole grid, by first flipping all rows, then columns, is nice imo.

Nice problem, although I feel like tests might be weak (?). My program passes pretty comfortably even tho it uses up to like 2*10^7 __gcd calls.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;cin>>n;
    vector<int>a(n),b(n);
    for(auto&x:a)cin>>x;
    for(auto&x:b)cin>>x;
    vector<int>c(2*n);
    for(int i=0;i<n;i++)
    {
        c[2*i]=max(a[i],b[i]);
        c[2*i+1]=min(a[i],b[i]);
    }
    vector<int>dp;
    for(auto&x:c)
    {
        auto it=lower_bound(dp.begin(),dp.end(),x);
        if(it==dp.end())dp.push_back(x);
        else *it=x;
    }
    cout<<dp.size()<<"\n";
}

Consider only the first and last occurrence of each letter.

To make all the letters equal, you will perform fewer than 26 operations. Try iterating through each starting letter.

Greedy doesn't work. Maybe generalize the idea with DP?

For each letter $$$c$$$, let's store its first and last occurrence: $$$l_c, r_c$$$. Now, if we want to perform an operation with letter $$$c$$$, the cost will be $$$r_c - l_c$$$. After this, $$$l_{c+1} = \min(l_{c+1}, l_c)$$$ and $$$r_{c+1} = \max(r_{c+1}, r_c)$$$.

Let $$$\text{meet}(l, r)$$$ be the letter we will encounter if we want to get from letter $$$l$$$ to letter $$$r$$$, and let $$$sz(l, r)$$$ be $$$r_{\text{meet}(l, r)} - l_{\text{meet}(l, r)}$$$ when we have already moved all letters up to $$$meet(l, r)$$$.

Now we can write a range DP.

Let $$$dp(l, r)$$$ be the minimal total cost to get from letter $$$l$$$ to letter $$$r$$$.

The transitions are:

At first, we move all the letters from $$$k+1$$$ to $$$r$$$. Then, we move all the letters from $$$l$$$ to $$$k$$$. Now, we need to get from $$$k$$$ to $$$r$$$. The size of the segment is $$$sz(l,k)$$$, and we will do exactly $$$\text{meet}(k+1, r) - \text{meet}(l, k)$$$ such operations.

The complexity is $$$O(A^4)$$$ where $$$A$$$ is the size of the alphabet. The DP works in $$$O(A^3)$$$ and we process it starting from each character.

The solution was proposed by Yam.

#include<bits/stdc++.h>
using namespace std;
const int A=30;
int dp[A][A],l[A][A],r[A][A],sz[A][A],meet[A][A];
int calc(int l,int r)
{
    if(meet[l][r]==-1)return 0;
    if(dp[l][r]!=1e9)return dp[l][r];
    auto&x=dp[l][r];
    for(int k=l;k<r;k++)
    {
        if(meet[l][k]==-1)x=min(x,calc(k+1,r));
        else if(meet[k+1][r]==-1)x=min(x,calc(l,k));
        else x=min(x,calc(l,k)+calc(k+1,r)+(meet[k+1][r]-meet[l][k])*sz[l][k]);
    }
    return x;
}
int get(vector<array<int,2>>a)
{
    for(int i=0;i<26;i++)
    {
        l[i][i]=a[i][0];
        r[i][i]=a[i][1];
        sz[i][i]=r[i][i]-l[i][i];
        dp[i][i]=0;
        if(a[i][1]==-1)meet[i][i]=-1;
        else meet[i][i]=i;
        for(int j=i+1;j<26;j++)
        {
            dp[i][j]=1e9;
            l[i][j]=min(l[i][j-1],a[j][0]);
            r[i][j]=max(r[i][j-1],a[j][1]);
            sz[i][j]=r[i][j]-l[i][j];
            if(a[j][1]!=-1)meet[i][j]=j;
            else meet[i][j]=meet[i][j-1];
        }
    }
    return calc(0,25);
}
int main()
{
    int n;string s;
    cin>>n>>s;
    vector<array<int,2>>a(26,{n,-1});
    for(int i=0;i<n;i++)
    {
        int c=s[i]-'a';
        a[c][0]=min(a[c][0],i);
        a[c][1]=max(a[c][1],i);
    }
    int mn=1e9;
    for(int k=0;k<26;k++)
    {
        mn=min(mn,get(a));
        a.push_back(a[0]);
        a.erase(a.begin());
    }
    cout<<mn<<"\n";
}

/*
    Author : Vimal Kumar Dubey
    Cf handle : code_vkd_001
    --------------------------------------------------------------------------------------

  When I wrote this, only God and I understood what I was doing
  Now, only God knows

  Roses do not bloom hurriedly; for beauty, like any masterpiece, takes time to blossom */

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

/*-------------------------------------------------------------------------------------------------------------*/
#define loop(k,b,a)                                                for(ll k=b;k<a;k++)
#define vl                                                              vector<ll>
#define print(s)                                                      cout<<s<<endl;
#define beg2end(count)                                        count.begin(),count.end()
using namespace std;
#define ll long long
#define KOPIKO                                                  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define getArr                                                      ll n; cin>>n; vl arr(n); for(auto&i:arr) cin>>i;
void display(vl &arr){for(auto&i:arr) cout<<i<<" "; cout<<endl;}
/*-------------------------------------------------------------------------------------------------------------*/
 template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
 template<typename T> using maxpq = priority_queue<T>;

/*====================================================CODE BEGINS ->!====================================================*/

void __jaiShreeRam() {


    ll n; cin>>n;

    ll xorr = n^1;

    loop(i,1,n+1){
     ll temp = i^(n-i+1);
     if(temp != xorr){
        print("-1")
        return;
    }
}

if(xorr==0){
    print(-1)
    return;
}


print(xorr)


}


int main() {

    KOPIKO

    #ifndef ONLINE_JUDGE
    cerr << "Exectution Time : " << clock() / (double)CLOCKS_PER_SEC << "sec   ";
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif


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

    __jaiShreeRam();
}

 void CPwithVKD() {
 
 
ll n; cin>>n;
 
if(isPowerofTwo(n+2)) print(n+1)
else print(-1)
 
 }

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int c[N],a[N];
int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;cin>>x;
        c[x]++;
    }
    for(int d=1;d<N;d++)
    {
        int k=0;
        for(int x=d;x<N;x+=d)k+=c[x];
        a[k]=d;
    }
    for(int i=n;i>=1;i--)a[i]=max(a[i+1],a[i]);
    for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}