In this blog, I’m sharing my solutions for Problems A to E from the recent Codeforces round. I have included step-by-step approaches, clean C++ code, and complexity analysis for each problem. Hopefully, it helps others understand the ideas and techniques used.
Problem A – Maple and Multiplication
Summary: Given two integers a and b, we can multiply either number by any positive integer any number of times. Determine the minimum number of operations to make a = b.
Approach:
If a == b, 0 operations are needed.
If one divides the other (a % b == 0 or b % a == 0), 1 operation suffices.
Otherwise, 2 operations are always enough.
C++ Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while(t--) {
int a, b; cin >> a >> b;
if(a == b) cout << 0 << "\n";
else if((a > b && a % b == 0) || (b > a && b % a == 0)) cout << 1 << "\n";
else cout << 2 << "\n";
}
return 0;
}
Time Complexity: O(1) per test case Space Complexity: O(1)
Problem B – Cake Collection
Summary: Given n ovens baking a_i cakes per second and m seconds, find the maximum cakes Maple can collect by teleporting to ovens.
Approach:
Always collect from the ovens with highest cake production.
Sort oven rates descending and pick the top min(n, m) ovens.
Multiply cakes by remaining seconds to get total.
C++ Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while(t--) {
int n; long long m; cin >> n >> m;
vector<long long> ovens(n);
for(int i = 0; i < n; i++) cin >> ovens[i];
sort(ovens.begin(), ovens.end());
long long totalCakes = 0;
int ovensToUse = min((long long)n, m);
for(int i = 0; i < ovensToUse; i++)
totalCakes += ovens[n-1-i] * (m - i);
cout << totalCakes << "\n";
}
return 0;
}
Time Complexity: O(n log n) per test case Space Complexity: O(n)
Problem C – Cake Assignment
Summary: Redistribute 2k+1 cakes so Chocola ends up with x cakes. Two operations are allowed: give half of cakes to the other if even. Find minimum steps and sequence.
Approach:
Keep adjusting Chocola/Vanilla counts by doubling/halving and record operations.
Reverse the sequence at the end to get chronological order.
C++ Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while(t--) {
long long k, x; cin >> k >> x;
long long total = 1LL << (k + 1);
long long chocola = x, vanilla = total - x;
vector<int> operations;
while(chocola != vanilla) {
if(chocola < vanilla) {
operations.push_back(1);
vanilla -= chocola;
chocola *= 2;
} else {
operations.push_back(2);
chocola -= vanilla;
vanilla *= 2;
}
}
reverse(operations.begin(), operations.end());
cout << operations.size() << "\n";
for(size_t i = 0; i < operations.size(); i++)
cout << (i ? " " : "") << operations[i];
cout << "\n";
}
return 0;
}
Time Complexity: O(k) per test case Space Complexity: O(k)
Problem D – Antiamuny Wants to Learn Swap
Summary: Given a permutation a, determine if a subarray is perfect (using at most one swap of distance 2 does not reduce the number of adjacent swaps needed).
Approach:
Compute prevGreater and nextSmaller indices using monotonic stacks.
Preprocess minimal R for each start index L.
Answer each query in O(1) using minRight.
C++ Solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while(t--) {
int n, q; cin >> n >> q;
vector<int> arr(n+1);
for(int i=1; i<=n; i++) cin >> arr[i];
vector<int> prevGreater(n+1,0), nextSmaller(n+1,n+1);
deque<int> mono;
for(int i=1; i<=n; i++){
while(!mono.empty() && arr[mono.front()]<arr[i]) mono.pop_front();
prevGreater[i]=mono.empty()?0:mono.front();
mono.push_front(i);
}
mono.clear();
for(int i=n; i>=1; i--){
while(!mono.empty() && arr[mono.front()]>arr[i]) mono.pop_front();
nextSmaller[i]=mono.empty()?n+1:mono.front();
mono.push_front(i);
}
vector<int> y(n+2,n+1);
for(int i=1;i<=n;i++){
int L=prevGreater[i],R=nextSmaller[i];
if(L>0 && R<=n && R<y[L]) y[L]=R;
}
vector<int> minRight(n+2,n+1);
minRight[n+1]=n+1;
for(int i=n;i>=1;i--) minRight[i]=min(y[i],minRight[i+1]);
while(q--){
int l,r; cin >> l >> r;
cout << (minRight[l]<=r?"NO\n":"YES\n");
}
}
return 0;
}
Time Complexity: O(n + q) per test case Space Complexity: O(n)
Problem E1 – Maple and Tree Beauty (Easy Version)
Summary: Given a rooted tree with n vertices labeled 0 or 1 (k zeros), determine maximum beauty (length of LCS of all leaf names).
Approach:
Compute depth of all nodes using DFS.
Count leaves at each depth → leafCount[depth].
Use subset sum DP to check if k zeros can be assigned to achieve maximum beauty.
C++ Solution:
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1005];
int depth[1005], leafCount[1005], n, k;
void dfs(int node, int d){
depth[node]=d;
if(adj[node].empty()) leafCount[d]++;
for(int child:adj[node]) dfs(child,d+1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while(t--){
cin >> n >> k;
for(int i=1;i<=n;i++){
adj[i].clear();
leafCount[i]=0;
}
for(int i=2;i<=n;i++){
int parent; cin >> parent;
adj[parent].push_back(i);
}
dfs(1,0);
int minLeafDepth=INT_MAX;
for(int i=1;i<=n;i++) if(adj[i].empty()) minLeafDepth=min(minLeafDepth,depth[i]);
int sumLeaves=0, extraNodes=0;
for(int i=0;i<=minLeafDepth;i++) sumLeaves+=leafCount[i];
for(int i=1;i<=n;i++) if(depth[i]>minLeafDepth) extraNodes++;
vector<bool> dp(sumLeaves+1,false);
dp[0]=true;
for(int i=0;i<=minLeafDepth;i++)
for(int j=sumLeaves;j>=leafCount[i];j--)
if(dp[j-leafCount[i]]) dp[j]=true;
bool feasible=false;
for(int s=0;s<=sumLeaves;s++)
if(dp[s] && s<=k && k-s<=extraNodes) {feasible=true; break;}
cout << (feasible ? minLeafDepth+1 : minLeafDepth) << "\n";
}
return 0;
}
Time Complexity: O(n^2) per test case Space Complexity: O(n)
