If you are trying to understand the optimal strategy for E.
Busy Beaver, you can think of it like an RPG city-building game where your goal is to use greedy block merging and a min-heap to grind for cash and build the tallest skyscraper possible. You start with a small amount of carrots and need to complete profitable construction "quests" across various sites before dumping all your accumulated wealth into a single building. Since some individual floors make a profit while others lose money, you first merge any unprofitable floor with the floors directly above it until the combined block yields a strictly positive net profit, creating a "quest" with a specific peak money requirement to survive construction and a total net payout at the end. Once you have these strictly profitable quests, you throw the first available one from every building into a min-heap sorted by their entry requirement and greedily complete the cheapest ones you can afford. Because every quest is profitable, your bank account snowballs, allowing you to unlock and add the next quests for those buildings into the heap until you are either too poor to afford the remaining ones or the heap is entirely empty. Having reached the absolute maximum wealth possible in the game, you then take your massive pile of cash and simulate buying the remaining unbuilt floors of each partially-constructed building one by one until you go completely broke, simply keeping track of which building reaches the highest floor.
This entire process efficiently groups the floors and processes the optimal path in $$$O(\sum m_i \log N)$$$ time, which easily passes the two-second time limit!
To mathematically solve the "Busy Beaver" problem, you must model the construction process using four core formulas applied in a single continuous workflow. First, every individual floor $$$i$$$ has an upfront cost $$$A_i$$$ and a completion reward $$$B_i$$$, meaning its net profit is calculated as $$$P = B_i - A_i$$$ and its base money requirement to start construction is $$$R = A_i$$$. Because some floors lose money ($$$P \le 0$$$), you must mathematically merge them with the floors directly above them into a combined block; when joining a lower block (with requirement $$$R_1$$$ and profit $$$P_1$$$) to an upper block (with requirement $$$R_2$$$ and profit $$$P_2$$$), the combined net profit is simply the sum $$$P_{new} = P_1 + P_2$$$, while the new combined minimum requirement becomes $$$R_{new} = \max(R_1, R_2 - P_1)$$$ because you need enough starting capital to afford the first block and also enough to cover the second block's cost after accounting for the first block's net cash change. Once all floors are merged into strictly positive profit blocks ($$$P \gt 0$$$), you use a min-heap to repeatedly check if your current total money $$$M$$$ meets the cheapest available block's requirement ($$$M \ge R$$$), and if so, you build it and update your wealth to $$$M_{new} = M + P$$$. Finally, having reached your mathematical maximum wealth from these profitable groups, you simulate building the remaining individual floors one by one by checking if $$$M \ge A_i$$$ and updating your money to $$$M_{new} = M - A_i + B_i$$$ while simply tallying the total floors built for each building to find the absolute maximum height.
Love cp by — IBACKFORREVENGE
Полный текст и комментарии »
