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!
Full text and comments »