Tigerrymander
SRM 823 · 2022-02-01 · by misof
Problem Statement
To celebrate the Lunar New Year that starts the Year of the Tiger, the problems in this set feature tigers.
Absurdistan has always been famous for having a population of oxen and tigers living peacefully together. However, recently there has been an issue of contention: how to celebrate the Lunar New Year? The tigers want huge fireworks while the oxen consider it a waste of money. As always, the final decision will be decided by a referendum: a nation-wide vote.
The tigers really want the fireworks, so they decided to help their issue by cunningly manipulating the voting system. Instead of simply counting all the votes, they will divide the country into several exactly equally large districts. Each district will take its own vote on the issue and then it will nominate one delegate (either a tiger or an ox) to represent the opinion that won in the district. Those delegates will then cast the votes that will determine the final outcome of the referendum.
And the tigers are not required to stop at one level of hierarchy. For the next step, each district can now be divided into sub-districts. The sub-districts must again have exactly the same size, all over the country, so that everything seems as fair as possible. Each sub-district will take a vote and nominate one sub-delegate for the district vote, and then each district will evaluate the votes of those sub-delegates and nominate one delegate for the country vote.
Obviously, the above process can be continued recursively arbitrarily many times. Again, we emphasize that on each level of the election hierarchy all sub*-districts across the whole country must have exactly the same size.
One final peculiarity of the voting system in Absurdistan is that a tiger is TV / OV times more powerful than an ox, and therefore a tiger's vote is worth TV and an ox's vote is worth OV.
As tigers are the ones who want change, they must have a strict majority in order for the motion to pass. (If in some vote the total weight of the tigers' votes is the same as the total weight of the votes of the oxen, an ox is nominated as the delegate.)
The total population of Absurdistan is N. Assume that tigers have perfect control over how to divide the country into districts - they get to choose the depth of the hierarchy, the district sizes, and they also decide which inhabitants belong into which districts. Calculate and return the minimal number of tigers in the population needed to get the fireworks.
Constraints
- N will be between 1 and 5 * 10^12, inclusive.
- TV will be between 1 and 10, inclusive.
- OV will be between 1 and 10, inclusive.
4 1 1 Returns: 3
There are 4 animals in Absurdistan, and the votes of tigers and oxen count the same. The tigers could divide the country into four districts of size 1, but that's the same as not dividing it at all: each district would simply nominate its only member. The tigers could also divide the country into two districts of size 2. This isn't exactly helpful: whenever there are two votes, both voters must be tigers in order for the tigers' motion to win. And thus if there are two districts of size 2, the tigers will only get fireworks if all four animals are tigers. Perhaps surprisingly, the best strategy here is to have everyone vote in the same election. Then three tigers can already outvote one ox.
13 2 1 Returns: 5
Again, the optimal solution is that there are no districts. Four tigers are not yet enough to win against nine oxen, but five tigers already have a stronger total vote than eight oxen.
12 7 7 Returns: 6
If everyone voted together, at least seven tigers would be needed. However, six tigers can still win the referendum by splitting the country cleverly. Using T and O to represent tigers and oxen, one optimal solution is to form four districts: TTO, TTO, TTO and OOO. Three districts will nominate a tiger while only one will nominate an ox, so in the final vote the tigers win 3:1. (There is one other solution that also allows six tigers to win the election.)
28 3 1 Returns: 2
Yes, you read that correctly, two tigers who cleverly manipulate the system can win the whole election here.
21 1 10 Returns: 20
Submissions are judged against all 225 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Tigerrymander with a public method long long minTigers(long long N, int TV, int OV) · 225 test cases · 2 s / 256 MB per case