Simply we should select maximum number and we should print:

value (number_of_value / n). If we select all (values) we can reach maximum possibility

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d", &n);
    int arr[n+1];
    for(int i = 1;i <= n;i++)
        scanf("%d", arr + i);
    map<int, int> h;
    int maxim = -1;
    for(int i = 1;i <= n;i++){
        maxim = max(arr[i], maxim);
        h[arr[i]]++;
    }
    printf("%d %.2f", maxim , (double)h[maxim]/n);
}

So, Simply we should assign leaf nodes to 2 and multiply it with other children, do it step by step, because leaf node should be minimum number that greater than 1.

//Bismillahirrahmanirrahim

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define mp make_pair
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000000;
 
int n,m,b[li],a[li],k,flag,t,dp[li];
int cev;
string s;
vector<int> v[li];
 
inline int mul(int x,int y){
	return (x%mod)*(y%mod)%mod;
}
 
inline void dfs(int node,int ata){
	dp[node]=1;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i];
		if(go==ata)continue;
		dfs(go,node);
		dp[node]=mul(dp[node],dp[go]);
	}
	if(dp[node]==1)dp[node]=2;
}
 
main(void){
	scanf("%lld",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%lld %lld",&x,&y);
		v[x].pb(y);
	}
	dfs(1,0);
	FOR printf("%lld ",dp[i]);
	return 0;
}

In this problem you will erase some letters. So when you found a subsequence with lenght k you will erase it.You will do at most (string size) erasing. If you do the erasings in string string.erase is working too slow and you need to do with another way. I did it with set. set.erase is working at log2(n) so mine solution is O(N log(N)). I think that there is a solution which works in O(N)(with stack or another thing) but mine solution is working in O(N logN)

//Bismillahirrahmanirrahim

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;
 
int n,m,k,flag,t,d[li];
int cev;
set<int> st;
string s;
 
int main(void){
	fio();
	cin>>n>>k>>s;
	for(int i=0;i<n;i++)st.insert(i);
	int say=1;
	d[0]=1;
	auto it=st.begin();
	it++;
	for(;it!=st.end();it++){
		int i=*it;
		auto it1=it;
		it1--;
		int i1=*it1;
		if(s[i]==s[i1])say++;
		else say=1;
		if(s[i]==s[i1])d[i]=d[i1]+1;
		else d[i]=1;
		if(d[i]>=k){
			say=k;
			auto it2=it;
			it2++;
			while(say>1){say--;it--;}
			it1=it;
			it=it2;
			it++;
			say=k;
			if(it1!=st.begin())it--;
			st.erase(it1,it2);
			//~ cout<<*it<<endl;
			while(say>0){
				//~ it=st.find()
				//~ cout<<*it<<endl;
				
				d[i-k+1+say-1]=1;
				say--;
			}
			n-=k;
			i-=k;
			
			it--;
			
		}
	}
	int tut=0;
	int at=0;
	for(auto it=st.begin();it!=st.end();it++){
		if(tut>=k)break;
		tut++;
		if(s[*it]==s[*st.begin()])at++;
	}
	if(at==k){
		tut=0;
		for(auto it=st.begin();it!=st.end();it++){
			if(tut>=k)break;
			tut++;
			st.erase(it);
		}
	}
	it=st.begin();
	for(;it!=st.end();it++){
		cout<<s[*it];
	}
	return 0;
}

D) Smart Move This question can solve with dynamic programming. Dp parameters are index of current item, remaining right, number of selected elements odd or even, number of selected elements modulo 3. Last two of them seen unnecessary, however these parameters help much in real solution. Naive Solution(O(N*K*K)) We can find the solution in O(N*K*K). For all k from k to 1 we calculate new dp array in O(N*K). If we use parameters as explain in top for all k we can find in O(N*K). We can solve like knapsack problem. Either we select this element or not. Original Solution(O(N*K*2*3)) As seen in the naive solution we are calculating same case lots of time. For reduce the time complexity firstly we can calculate the case which we have K right. Then we need to find the case which we have K-1 right. How we can pass it? In my solution I start my selected number as 0 and in the function if my selected number is much than k (if my selected number>k) I finish. With a smart move I start my selected number as 1 and I don’t change stopping condition(if my selected number>k) in recursion. For K-2 right, I start my selected number as 2 and it goes like this. So with this smart move we don’t calculate same case and we calculate maximum N*K case since complexity is O(N*K*2*3).

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define inf 1000000000000000000
#define md 1000000007
#define pb push_back
#define li 2005
#define int long long
using namespace std;
int n,A[li],k,dp[li][li][3][2];
int dfs(int node,int hak,int flag1,int flag2){
    int cev=-inf;
    if(hak>k) return -inf;
    if(node==n+1) return 0;
    if(~dp[node][hak][flag1][flag2]) return dp[node][hak][flag1][flag2];
    cev=max(cev,dfs(node+1,hak,flag1,flag2));
    cev=max(cev,dfs(node+1,hak+1,(flag1+1)%3,(flag2+1)%2)+A[node]*((flag1+1)%3)*((flag2+1)%2==1?-1:1));
    return dp[node][hak][flag1][flag2]=cev;
}
void solve(){
    memset(dp,-1,sizeof(dp));
    scanf("%lld %lld",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&A[i]);
    for(int i=k;i>=1;i--){
        int cikar=k-i;
        int ty=dfs(1,cikar,0,0);
        printf("%lld ",ty);
    }
    printf("\n");
}
int32_t main(){
    solve();
    return 0;   
}

Sorry for time limit mistakes but if we didn’t change the time limit then question would wasted. Thank you for participating. It can be seen that ans(i+1)>=ans(i) because max and min number in ans(i) also in ans(i+1) and thanks to growth of interval there can be any other min or max value since ans(i+1)>=ans(i). After this observation divide and conquer comes to mind. First send (1,n) interval to the divide and conquer. Then find the mid value of interval with naïve solution. Then divide the interval into two parts. (l,mid-1) and (mid+1,r). Max result of left part is result[mid] and min result of right part is result[mid]. But this is already O(logn*logn- >> divide and conquer part). So we need to find naive solution in O(n). In naive solution I traverse array one by one. Firstly look (1,k) then (2,k+1), (3,k+2)…. (n-k+1,n) But for each step I need to find result in O(1). Find maximum and minimum number in this interval in O(1). This can be done with sparse table. We firstly build sparse table in O(Nlogn) time and then calculate all queries in O(1). Solution has O(N*logN*log(10^9)) complexity. Because in divide and conquer we use 4 parameter(l,r,optl,optr). And interval length of (optl,optr) is 10^9.

#include <bits/stdc++.h>
using namespace std;
#define mid (l+r)/2
#define mid2 (start+end)/2
#define inf 1000000000
#define li 37000
#define mp make_pair
#define fi first
#define se second
#define lo long long
int n,A[li],dp[li],say,vis[li],lookup[li][30],lookup2[li][30];
pair<int,int> tree[li*4];
void buildminSparseTable(int n) 
{ 
    for (int i = 1; i <= n; i++) 
        lookup[i][0] = A[i]; 
    for (int j = 1; (1 << j) <= n; j++) {  
        for (int i = 1; (i + (1 << j) - 1) <= n; i++) 
        {  
            if (lookup[i][j - 1] <  lookup[i + (1 << (j - 1))][j - 1]) 
                lookup[i][j] = lookup[i][j - 1]; 
            else
                lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1]; 
        } 
    } 
}
int querymin(int L, int R) 
{  
    int j = (int)log2(R - L + 1);  
    if (lookup[L][j] <= lookup[R - (1 << j) + 1][j]) 
        return lookup[L][j]; 
  
    else
        return lookup[R - (1 << j) + 1][j]; 
}
void buildmaxSparseTable(int n) 
{ 
    for (int i = 1; i <= n; i++) 
        lookup2[i][0] = A[i]; 
    for (int j = 1; (1 << j) <= n; j++) {  
        for (int i = 1; (i + (1 << j) - 1) <= n; i++) 
        {  
            if (lookup2[i][j - 1] >  lookup2[i + (1 << (j - 1))][j - 1]) 
                lookup2[i][j] = lookup2[i][j - 1]; 
            else
                lookup2[i][j] = lookup2[i + (1 << (j - 1))][j - 1]; 
        } 
    } 
}
int querymax(int L, int R) 
{  
    int j = (int)log2(R - L + 1);  
    if (lookup2[L][j] >= lookup2[R - (1 << j) + 1][j]) 
        return lookup2[L][j]; 
  
    else
        return lookup2[R - (1 << j) + 1][j]; 
}
int naive(int val){
	say++;
	int cev=0;
	for(int i=val;i<=n;i++){
		int basla=i-val+1;
		cev=max(cev,querymax(basla,i)-querymin(basla,i));
	}
	return cev;
}
void solve(int l,int r,int optl,int optr){
	if(l>r) return ;
	if(optl==optr || vis[mid]==1){
		if(vis[mid]==0)
			dp[mid]=optl;
		vis[mid]=1;
	}
	else {dp[mid]=naive(mid);vis[mid]=1;}
	solve(l,mid-1,optl,dp[mid]),solve(mid+1,r,dp[mid],optr);
}
void general(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	buildmaxSparseTable(n);
	buildminSparseTable(n);
	solve(1,n,0,inf);
	for(int i=1;i<=n;i++) printf("%d ",dp[i]);
	printf("\n");
}
int main(){
	general();
	return 0;
}