### night.watchman's blog

By night.watchman, 4 months ago, ## 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?? div3, Comments (1)