To solve this problem, use seive to find prime factors and use two pointer to maximize the largest segment.

#include <iostream>
#include <vector>
#include<set>
using namespace std;
#define N 1000000+1
int spf[N];
void sv()
{
	spf[1]=0;
	for(int i=2;i<N;i++)
		spf[i]=i;
	for(int i=4;i<N;i+=2)
	    spf[i]=2;
	for(int i=3;i*i<N;i+=2)
	{
		if(spf[i]==i)
		{
			for(int j=i*i;j<=N;j+=i)
			{
				if(spf[j]==j)
				    spf[j]=i;
			}
		}
	}
}
void solve(int t)
{
	vector<int>dp(N,0);
	int n,k,almost=0,mx_sz=0,l=0;
	cin>>n>>k;
	int a[n],b[n];
	vector<int>v;
	for(int i=0;i<n;i++)
		cin>>a[i];
	for(int r=0;r<n;r++)
	{
		int x = a[r];
		set<int>s;
		while(x!=1)
		{
			int y = spf[x];
			s.insert(y);
			x/=y;
		}	
		b[r]=s.size();
		bool perfect= false;
		for(auto z:s)
		{
			v.push_back(z);
			dp[z]++;
			if(dp[z]==1 && z!=0)almost++;
			if(dp[z]==r-l+1)perfect=true;
		}
	    while(almost>k && l<n)
		{
			int u = b[l];
			for(int j=0;j<u;j++)
			{
				dp[v[j]]--;
				if(dp[v[j]]==0 && v[j]!=0)
					almost--;		
			}
			l++;
			v.erase(v.begin(),v.begin()+u);	
		}
		if(almost == k && !perfect)
			mx_sz=max(mx_sz,r-l+1);	
	}
	cout<<"Case "<<t<<": "<<mx_sz<<"\n";		
}
int main()
{
	sv();
	int T=1;
	cin>>T;
	for(int t=1;t<=T;t++)solve(t);
	return 0;	
}

To solve this problem, there are only two repeated patterns inside the range $$$lcm(a,a-1)$$$. And another matter is , Value of range $$$lcm(a,a-1)$$$ also repeats because whole patterns is same. So the formala is

Value of range $$$lcm(a,a-1)$$$ is

It's equal to

Here $$$n = a-2 $$$ and $$$b = a-1$$$ Do the same process if there is quotient of $$$\frac{n}{ab}$$$.

#include <iostream>
#define int long long 
using namespace std;

int eq(int n, int x) 
{
    return n * (n + 1) * 0.5 * (2 * x - 1) + (n + 1) * x - n * (n + 1) * (2 * n + 1) / 3;
}

int32_t main() 
{
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) 
    {
        int a, n;
        cin >> a >> n;
        int b = a - 1;
        int l = a * b;
        int p = n / l;
        int q = n % l;
        int r = (q + 1) / a;
        int s = (q + 1) % a;
        int ans = p * eq(b - 1, b);
        
        if (q != 0)
        {
            if (r > 0) 
                ans += eq(r - 1, b);
            
            if (s == 0) 
            {
               cout << "Case " << i + 1 << ": " << ans << "\n";
               continue ;
            }
            if (b - r >= s) 
                ans += s * r;
             
            else 
                ans += r * (b - r) + (s - b + r) * (b - r);
            
        }
        
        cout << "Case " <<i<< ": " << ans << "\n";
    }
    return 0;
}

def eq(n,x):
    return n*(n+1)*0.5*(2*x-1)+(n+1)*x-n*(n+1)*(2*n+1)/3
for i in range(int(input())):
    a,n = map(int,input().split())
    b = a-1
    l = a*b
    p = n//l
    q = n%l
    r = (q+1)//a
    s = (q+1)%a
    ans = p*eq(b-1,b)
    if q!=0:       
        if r>0:
            ans+=eq(r-1,b)
        if s==0:
            continue
        if b-r >= s:
            ans+= s*r
        else:
            ans+= r*(b-r)+(s-b+r)*(b-r)
    print(f'Case {i+1}: {int(ans)}')

#include <iostream>
using namespace std;
#define N 1000
using ll=long long;
string arr[N];
ll dp[N][N];

ll fn(ll x,ll n,ll k)
{
	ll y=0,u=0,w=0;
	ll a = (x+1)/(n*k*k);
	ll b = (x+1)%(n*k*k);
	if(a>0)
	{	
		u = a;
	    w = dp[a-1][n-1];
        y += w*k*k;
	}
	if(b==0)
		return y;
    ll c = b/(n*k);
    ll d = b%(n*k);
	if(c>0)
		y += (dp[u][n-1]-w)*k*c;
	if(d==0)
		return y;
	ll e = d/k;
    ll f = d%k;
	if(e != 0)
		y += (dp[u][e-1]-w)*k;
	if(f != 0)
		y += (arr[u][e]-'0')*f;
	return y;
}
	
void solve(int t)
{
	ll n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>arr[i];
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(i==0 && j==0)
			    dp[i][j]=arr[i][j]-'0';
			else if(j==0)
			    dp[i][j]=(arr[i][j]-'0')+dp[i-1][n-1];
			else
			    dp[i][j]=(arr[i][j]-'0')+dp[i][j-1];
		}
	}
	int q;
	cin>>q;
	cout<<"Case "<<t<<":\n";
	while(q--)
	{
		ll l,r;
		cin>>l>>r;
		ll z = fn(r,n,k);
		if(l!=0)
		   z-= fn(l-1,n,k);	
		cout<<z<<"\n"; 
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	for(int t=1;t<=T;t++)solve(t);
}
	

To solve this problem, from the problem's description a beautiful subarray consists atleast two different element. So there atleast two elements exist in a subarray to fulfill this condition. Then the total combinations of subarray is

Then remove all the subarray which has no atleast two different elements. To do it, we count the adjacent same element and substitute it's combination value from the total subarray.then repeat it from previous count number index. Until we reach last index of the array, repeat.

#include <iostream>
using namespace std;
using ll = long long;
ll f(int x){
	return (ll)x*((ll)x-1)/2;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	for(int t=1;t<=T;t++)
	{
		int n;
		cin>>n;
		ll sum = f(n);
		int a[n];
		for(int& i:a)cin>>i;
		int j = 0;
		while(j<n)
		{
			int key = a[j];
			int m = 1;
			while(j<n-1 && key == a[j+1])
			{
				m++;
				j++;
			}
			sum-=f(m);
			j++;
		}
		cout<<"Case "<<t<<": "<<sum<<"\n";
	}
	return 0;
}

def fn(x) -> int :
	return int(x*(x-1)*0.5)
for i in range(int(input())):
	n = int(input())
	s = fn(n)
	l = [int(i) for i in input().split()]
	j = 0
	while j<n:
		key = l[j]
		m = 1
		while j<n-1 and key == l[j+1]:
			m+=1
			j+=1
		s -= fn(m)
		j+=1
	print(f'Case {i+1}: {s}')

This problem is super simple and easiest problem of this contest. To solve this problem, count wicket and run by looping all over the string and make a funtion to check the values of over,run and wicket have singular or plural. Then just print according to output's format.

#include <iostream>
#include <cmath>
using namespace std;
void c(int n)
{
	if(n>1)cout<<'s';
}
int main(){
	int t;
	cin>>t;
	while(t--)
	{
		string s;
		cin>>s;
		int r=0,o=s.size(),w=0;
		int x = ceil((float)o/6);
		for(auto i:s)
		{
			if(i=='W')w++;
			else r+=i-'0';
		}
		cout<<o/6<<'.'<<o%6<<" "<<"Over";
		c(x);
		cout<<" "<<r<<" "<<"Run";
		c(r);
		cout<<" "<<w<<" "<<"Wicket";
		c(w);
		cout<<".\n";
		
	}
	return 0;
}

def c(n):
	return n>1 and 's' or ''
for _ in [0]*int(input()):
	s = input()
	o,r,w=len(s),0,0
	for j in s:
		if j=='W':w+=1
		else:r+=int(j)
	print(f'{o//6}.{o%6} Over{c(o/6)} {r} Run{c(r)} {w} Wicket{c(w)}.') 

Setter:

• Shafaet Ashraf

  Tester & Alter writers:

• Nafis Sadique

• Aleksa Plavsic

  Problem type:

• Game Theory, DP

  Solution idea:

  If you're familiar with Grundy Numbers, you can use the divide and conquer technique to solve it. To do this, loop through the columns of the grid and place a box in all possible positions. Whenever a box is placed, it divides the whole grid into two parts. Solve each sub-problem recursively by calculating the Grundy number. The base case is when the grid size is less than 1. This solution has a time complexity of O(N^3) and will pass the time limit.