Virtual participation in a Div. 3 round can be a great mood booster. This article covers all problems from that contest, providing solutions and code.

A - Divisibility Problem

Straightforward implementation.

#include<bits/stdc++.h>
using namespace std;
void mian(){
	int a,b;
	cin>>a>>b;
	cout<<(a%b?b-a%b:0)<<"\n";
}
int main(){
	int testnum=1;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}

B - K-th Beautiful String

Enumerate the position of the leftmost 'b'. Compute how many strings have a given left 'b' position, then locate the k-th string.

#include<bits/stdc++.h>
using namespace std;
void mian(){
	int n,k;
	cin>>n>>k;
	for(int i=n-1;;i--){
		if(n-i>=k){
			for(int j=1;j<i;j++)putchar('a');
			putchar('b');
			for(int j=i+1;j<i+(n-i-k+1);j++)putchar('a');
			putchar('b');
			for(int j=i+(n-i-k+1)+1;j<=n;j++)putchar('a');
			puts("");
			return;
		}
		k-=n-i;
	}
}
int main(){
	int testnum=1;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}

C - Ternary XOR

Greedy approach: for digits before the first '1', split equally. At the first '1', one number gets '1', the other gets '0'. After that, assign all '0's to the larger number.

#include<bits/stdc++.h>
using namespace std;
void mian(){
	int n;
	string a,b,c;
	cin>>n>>a;
	for(int i=0;i<n;i++)if(a[i]=='1'){
		for(int j=0;j<i;j++){
			if(a[j]=='0')b+='0',c+='0';
			else b+='1',c+='1';
		}
		b+='1',c+='0';
		for(int j=i+1;j<n;j++){
			if(a[j]=='0')b+='0',c+='0';
			else if(a[j]=='1')b+='0',c+='1';
			else b+='0',c+='2';
		}
		cout<<b<<"\n"<<c<<"\n";
		return;
	}
	for(int j=0;j<n;j++){
		if(a[j]=='0')b+='0',c+='0';
		else b+='1',c+='1';
	}
	cout<<b<<"\n"<<c<<"\n";
}
int main(){
	int testnum=1;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}

D - Carousel

Greedy assign colors 1 and 2. If the first and last animals conflcit, try to flip a consecutive pair of same-type animals. If no such pair exists, use a third color.

#include<bits/stdc++.h>
using namespace std;
const int N=200000;
int a[N+1];
int ans[N+1];
void mian(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	ans[1]=1;
	for(int i=2;i<=n;i++)
		if(a[i]==a[i-1])ans[i]=ans[i-1];
		else ans[i]=3-ans[i-1];
	int mx=0;
	for(int i=1;i<=n;i++)mx=max(mx,ans[i]);
	if(a[1]!=a[n]&&ans[1]==ans[n]){
		bool used=false;
		for(int i=2;i<=n;i++)
			if(a[i]==a[i-1])
				if(!used)ans[i]=3-ans[i-1],used=true;
				else ans[i]=ans[i-1];
			else ans[i]=3-ans[i-1];
		if(a[1]!=a[n]&&ans[1]==ans[n]){
			cout<<mx+1<<"\n";
			ans[1]=mx+1;
			for(int i=1;i<=n;i++)printf("%d ",ans[i]);
			puts("");
		}
		else{
			cout<<mx<<"\n";
			for(int i=1;i<=n;i++)printf("%d ",ans[i]);
			puts("");
		}
	}
	else{
		cout<<mx<<"\n";
		for(int i=1;i<=n;i++)printf("%d ",ans[i]);
		puts("");
	}
}
int main(){
	int testnum=1;
	cin>>testnum;
	while(testnum--)mian();
	return 0;
}

E - Tree Queries

Condition: all given nodes' parents must lie on a single root-to-leaf path. Use DFS timestamps to check ancestry.

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200000;
int n,qu;
vector<int> nei[N+1];
int fa[N+1],dep[N+1];
int dfn[N+1],nowdfn,mxdfn[N+1];
void dfs(int x=1){
	dfn[x]=mxdfn[x]=++nowdfn;
	for(int i=0;i<nei[x].size();i++){
		int y=nei[x][i];
		if(y==fa[x])continue;
		fa[y]=x;
		dep[y]=dep[x]+1;
		dfs(y);
		mxdfn[x]=mxdfn[y];
	}
}
int cmp(int x,int y){return dep[x]<dep[y];}
void mian(){
	cin>>n>>qu;
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		nei[x].pb(y);nei[y].pb(x);
	}
	dfs();
	while(qu--){
		int m;
		scanf("%d",&m);
		vector<int> v;
		for(int i=1;i<=m;i++){
			int x;
			scanf("%d",&x);
			v.pb(max(1,fa[x]));
		}
		sort(v.begin(),v.end(),cmp);
		bool flg=true;
		for(int i=0;i+1<v.size();i++)flg&=dfn[v[i]]<=dfn[v[i+1]]&&dfn[v[i+1]]<=mxdfn[v[i]];
		puts(flg?"YES":"NO");
	}
}
int main(){
	int testnum=1;
	while(testnum--)mian();
	return 0;
}

F - Make k Equal

Optimal strategy: move elements from both ends toward some target value existing in the array. Precompute prefix and suffix costs, then evaluate three scenarios: only left, only right, both sides.

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
const int inf=0x3f3f3f3f3f3f3f3f;
const int N=1000000;
int n,m;
int a[N+1];
vector<int> nums;
int cnt[N+1];
int d[N+1];
void discrete(){
	sort(nums.begin(),nums.end());
	nums.resize(unique(nums.begin(),nums.end())-nums.begin());
	while(nums.size()<n)nums.pb(nums.back()+1);
	for(int i=1;i<=n;i++)a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin(),cnt[a[i]+1]++;
	for(int i=1;i<n;i++)d[i]=nums[i]-nums[i-1];
}
int Cnt[N+1],cnT[N+1];
int Tim[N+1],tiM[N+1];
void mian(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%lld",a+i),nums.pb(a[i]);
	discrete();
	for(int i=1;i<=n;i++)Cnt[i]=Cnt[i-1]+cnt[i];
	for(int i=n;i;i--)cnT[i]=cnT[i+1]+cnt[i];
	for(int i=2;i<=n;i++)Tim[i]=Tim[i-1]+Cnt[i-2]+Cnt[i-1]*(d[i-1]-1);
	for(int i=n-1;i;i--)tiM[i]=tiM[i+1]+cnT[i+2]+cnT[i+1]*(d[i]-1);
	int ans=inf;
	for(int i=1;i<=n;i++)
		if(m<=cnt[i])ans=0;
		else{
			if(Cnt[i-1]>=m-cnt[i])ans=min(ans,Tim[i]+m-cnt[i]);
			if(cnT[i+1]>=m-cnt[i])ans=min(ans,tiM[i]+m-cnt[i]);
			ans=min(ans,Tim[i]+tiM[i]+m-cnt[i]);
		}
	cout<<ans;
}
signed main(){
	int testnum=1;
	while(testnum--)mian();
	return 0;
}