2023
Problemset
==================
A. Almost Perfect Prime Factor!
#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();
int perfect=0;
for(auto z:s)
{
v.push_back(z);
dp[z]++;
if(dp[z]==1 && z!=0)almost++;
if(dp[z]==r+1)perfect++;
}
while(almost-perfect>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 - perfect == k)
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;
}
B. Bob and Numbers
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)}')
E. Sub-Array
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}')
G. Bowling Figure
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)}.')
2022
Problem A: A Game with Grandma
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.