Binary Cafe — "Bruteforce Solution"

I guess, I’ve come up with a “Bruteforce” Solution of Problem B (Binary Cafe) from the Latest Codeforces Round 878 (Div. 3). At first glance, it may look a bit complex but actually it isn’t that complex.

My Submission

First, I’ve kept the costs of desserts in a vector. I stored it optimally, I mean, I obviously don’t need to store values like ($$$ 2^{32}, 2^{33}, 2^{34} $$$) etc. Besides If Toma’s coins aren’t enough to buy after some types of desserts, the I don’t need to store further.

Then I make a Prefix Sum vector. The idea is to check how many desserts Toma can choose from the beginning. An interesting fact, here the i-th value of Prefix Sum vector is always 1 less than (i+1)-th value of the main vector. Because $$$ 2^0 + 2^1 + 2^2 + .... + 2^n = 2^{n+1}-1 $$$

Now I iterate the Prefix sum vector to determine how many desserts Toma can choose from the beginning. Let’s call it P. Toma can choose any combination from these P values. That means I need to calculate ($$$ C_{0}^{P} + C_{1}^{P} + C_{2}^{P} +....+ C_{P}^{P} $$$). Another interesting fact is that this sum is equal to ($$$ 2^{P}-1 $$$).

At last, I fixed some values which were not taken and do the same thing. I can perform a nested loop also as I know that maximum size of the vector is around 30. Don’t Forget to add 1 with the answer if Toma choose 0 deserts. Can I call it a Bruteforce solution??

Useless Talks Alert

I can’t solve this in Contest time. But I was determined to solve this one without seeing any tutorial or hints & finally did so. Then I saw the tutorial, there is short code & smart thing obviously. I am a learner of CP. Currently struggling to raise my ratings above 1350. If any well wisher comes out here, suggest me some tips considering my CF profile. Thank You!