editorial of Bangladesh 2.0 contest.

solution:

we know that any number A>B if A has more digit than B. If both number has same number of digits then the number which is lexicographically larger is greater among them.

so our first target is to concatenate a subarray of length K+1 to make the longest string. if there are more than one longest string possible take the lexicographically maximal one.

to do so, we can iterate over all K+1 length subarray and find the maximum length possible.

time complexity : \(O(N*(N-k))\)

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

#define fr freopen("input14.txt","r",stdin)
//ofstream file("output14.txt");

void solve()
{
    int n,k; cin>>n>>k;
    ++k;
    vector<string> a(n);
    for(int i=0;i<n;i++) cin>>a[i];

    vector<int> pfs(n);
    pfs[0] = a[0].size();
    for(int i=1;i<n;i++) pfs[i] = pfs[i-1]+a[i].size();

    int longest=pfs[k-1];
    for(int i=k;i<n;i++) longest = max(longest , pfs[i]-pfs[i-k]);  // tbc
    
    vector<char> ans(longest,'0');
    int cnt = 0;
    if(pfs[k-1] == longest)
    {
        int ind = 0;
        for(int i=0; i<k; i++)
        {
            for(auto e:a[i]) 
            {
                ans[ind] = e;
                ++ind;
                //++cnt;
            }
        }
    }
    
    for(int i=k; i<n; i++)
    {
        if(pfs[i]-pfs[i-k] == longest)
        {
            int ind = 0;
            bool run = false, br = false;
            for(int j=i-k+1; j<=i; j++)
            {
                for(auto e:a[j])
                {
                    if(e > ans[ind]) run = true;
                    if(e < ans[ind] && !run) 
                    {
                        br = true;
                        break;
                    }
                    ans[ind] = e;
                    ++ind;
                    //++cnt;
                }
                if(br) break;
            }
        }
    }

    //cout<<ans.size()<<endl;
    for(auto e:ans) cout<<e; cout<<endl;
    //cout<<cnt<<endl;
}

int main()
{
    //fr;
    int t; cin>>t; while(t--) 
    {
        solve();
    }
}