Codeforces 1048 (Div 2) Problem B: Cake Collection

Ishmaam

5 min read

·

Nov 7, 2025

--

Listen

Share

Hi guys, for a long time, I have been wanting to deep dive into Codeforces problems! As I solve them, I want to share with you what I learnt and how I implemented with simpler explanations! Today I want to start with B. Cake Collection (Codeforces 1048 Div 2).

First let’s introduce you with the question and the sample test cases for your convenience:

Press enter or click to view image in full size

Press enter or click to view image in full size

The code implementation has been given:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void solve()
{
    long long n, m;

    long long sum = 0;

    cin >> n >> m;
    vector<long long> arr(n);

    for (long long i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end(), greater<>());

    for (int i = 0; i < n && m; i++)
    {
        sum += arr[i] * (m--);
    }

    cout << sum << endl;
}

int main()
{
    long long t;
    cin >> t;
    for (long long i = 0; i < t; i++)
    {
        solve();
    }
}

Now let’s break each down to understand how and why we are doing each part of the code with some solid examples that I faced during my test cases!

For the first test case, we could have gone to the ovens producing 1 cake, 2 cakes, 3 cakes, any of them. But we chose to go to the oven producing smallest cakes first. Why?

See, the play here is we should let the biggest oven accumulate more and more cakes before we pick them. Why? We can take greater number of cakes from the bigger oven all in one second if we let them accumulate!

If you picked the third/biggest oven for all the 4 seconds,

t=1, sum=3,
t=2, sum=3+3,
t=3, sum= 3+3+3,
t=4, sum= 3+3+3+3=12

yes you will get 12 cakes. Again, if you picked the third oven at the 4th second all at once as it accumulates:

t=1, sum= 1,
t=2, sum=1+1,

t=3, sum=1+1+(2*3),
why 2*3? 3 seconds passed and so far, 2+2+2 in 2nd oven

t=4, sum=1+1+(2*3)+(3*4)= 1+1+6+12 why 3*4? 4seconds passed and so far, 3+3+3+3 in 3rd oven

But what’s the point of getting all the 12 cakes by 4 seconds, if you would eventually get it by the 4th second altogether no matter what? Collecting other cakes besides these 12 cakes at the 4th second will maximise the number of cakes right?

So before we begin, I’m sure you have noticed we first sorted the array in descending order:

sort(arr.begin(), arr.end(), greater<>());

This allows us to give the greater value of m to the greater oven and the smaller value of m to the smaller oven as we decrease m, that’s our goal! To maximize the number of cakes:

for (int i = 0; i < n && m; i++)
    {
        sum += arr[i] * (m--);
    }

There are 3 edge cases to solve in this problem:

First, n>m

If n>m,
e.g. n=3, m=2 and arr[n]= {1,2,3}
what do we do?

Obviously we have to choose the two largest producing ovens, choosing the smallest one here will always give you smaller than the maximum! Instead we keep on adding the m largest ovens only once.

With m<n, this for loop will break easily before the loop runs out due to m becoming 0.

Let’s see the simulation:

Initially at i=0, sum=0 and arr[i]=3, m=2
sum= sum + arr[i] * m
sum= 0 + 3*2= 6
m- - now causes m to be 1

Now,
here’s the catch! After this part, decrementing m to the point of 0 causes the loop to break at some point since we have the condition i<n && m i.e. till m=true or m>0.

Next, when i=1,
sum= sum + arr[1] * m, where m=1 now after decrementing by 1
sum= 6 + 2*1= 8,
m- - now causes m to be 0

Next when i=2 ,
m=0 so one of the conditions of the and (i<n && m) is now false, hence we don’t do further loop and cakes from two of the largest ovens have been added together!

Second, n==m

Here we just let all the ovens’ cakes accumulate one by one with the largest oven’s cake being picked up at the end and the smallest oven’s cakes being picked up first to maximize the collection!

e.g. n=3, m=3 and arr[n]= {1,2,3}

Initially at i=0, sum=0 and arr[i]=3, m=3
sum= sum + arr[i] * m
sum= 0 + 3*3= 9
m- - now causes m to be 2

Next, when i=1,
sum= sum + arr[1] * m, where m=1 now after decrementing by 1
sum= 9+ 2*2= 13,
m- — now causes m to be 1

Next when i=2 ,sum= sum + arr[1] * m, where m=1 now after decrementing by 1
sum= 13+ 1*1= 14,
m- — now causes m to be 0

m=0 and at the same time i=3 so both of the conditions (i<n && m) are now false, hence we don’t do further loop and cakes all of the ovens have been added together once!

And the last edge case, n<m, trickiest one.

Note that, here adding the larger values more than once do no good! suppose 1+2+2+3 does no good, 1+2+3+3 does no good either! Remember our first point- “ We can take greater number of cakes from the bigger oven all in one second if we let them accumulate”

We do exactly this in this case too! We let the bigger ovens -> 2 and 3 accumulate before taking them out and instead we keep on picking the smallest ovens till (m-n) seconds. After (m-n) seconds we pick all the ovens once!

E.g. e.g. n=3, m=5 and arr[n]= {1,2,3}
For the first m-n= 5–3= 2 seconds we pick 1 then we pick each oven once, so in total Oven 1 comes 3 times and then Oven 2 and 3 once
So the number of cakes -> (1*1)+(1*1)+(1*1)+(2*4)+(3*5)= 26

Why (1*1)+(1*1)+(1*1) ? Because we let Oven 1 produces only 1 cake and accumulate for only 1 second and Oven 2 produces 2 cakes each second and it could accumulate for 4 seconds so (2*4). While Oven 3 produced 3 cakes for 5 seconds so (3*5).

Initially at i=0, sum=0 and arr[i]=3, m=5
sum= sum + arr[i] * m
sum= 0 + 3*5= 15
m- — now causes m to be 4

Next, when i=1,
sum= sum + arr[1] * m, where m=1 now after decrementing by 1
sum= 15+ 2*4= 23,
m- — now causes m to be 3

Next when i=2 ,sum= sum + arr[1] * m, where m=1 now after decrementing by 1
sum= 23+ 1*3= 26,
m- — now causes m to be 2

m=2 but at the same time i=3 so the first condition of (i<n && m) is now false, hence we don’t do further loop and cakes all of the ovens have been added together!

If you understood the solution, please do give a clap and follow me for more contents on Codeforces and development related articles. I wish to bring you more content on simpler explanations. This was my first article on Medium!

Please if you have any queries on understanding this problem, do let me know in the comment section! And get connected me on Codeforces- my handle- yondaime_hokage