How should I practice Election District Budget Allocation Analysis?

Start by reading the full statement, solve the visible examples, then compare the pattern against related IMC Trading phone screen problems in FastPrep.

Is Election District Budget Allocation Analysis associated with IMC Trading?

FastPrep tags this as a IMC Trading phone screen coding practice problem when the problem catalog has that company and stage context.

Election District Budget Allocation Analysis

IMC Trading● HardNEW GRADPHONE SCREEN

Learn

Problem statement

Two campaigns allocate nonnegative integer funds across districts labeled districts. Your allocation must sum exactly to ownFunds; the opponent's must sum exactly to opponentFunds. You win a district when your funds are larger, lose when they are smaller, and tie when they are equal. You win the election exactly when the number of districts you win is greater than the number you lose. Tied districts are ignored.

For this exercise, assume the opponent follows the selected probability law:

opponentModel = 0: every labeled nonnegative integer allocation summing to the opponent's budget is equally likely.
opponentModel = 1: the opponent is as balanced as possible. Write its budget as q * districts + r; exactly r labeled districts receive q+1 funds and the rest receive q. Every distinct placement of those larger entries is equally likely.

Complete analyzeElection(districts, ownFunds, opponentFunds, opponentModel). For this exercise, assume a deterministic array of 5 + 2 * districts signed 64-bit integers combines all answers in this order:

The total number of possible opponent allocations under the selected model.
The maximum number of those allocations you can beat with your exact budget.
The minimum number of those allocations you can beat with your exact budget.
The smallest own budget that gives some allocation a positive chance of victory against a balanced opponent with the given opponentFunds, regardless of the selected model.
The smallest balanced opponent budget that makes victory impossible for every own allocation summing to the given ownFunds, regardless of the selected model.
The districts entries of a best allocation, then the districts entries of a worst allocation.

For this exercise, assume that ties between equally good best allocations, or equally bad worst allocations, are broken by choosing the lexicographically smallest full allocation. The maximum and minimum probabilities are the corresponding winning counts divided by the total opponent count. A positive chance means at least one possible opponent allocation can be beaten; it does not mean guaranteed victory.

Function

analyzeElection(districts: int, ownFunds: int, opponentFunds: int, opponentModel: int) → long[]

Examples

Example 1

districts = 3ownFunds = 4opponentFunds = 4opponentModel = 0return = [15,5,0,4,5,1,1,2,0,0,4]

Stars and bars gives 15 possible opponent vectors. The lexicographically smallest best allocation is [1,1,2], with probability 5/15; the worst is [0,0,4], which never wins. Against balanced opponents, the minimum own budget is 4, and the first blocking opponent budget for own budget 4 is 5.

Example 2

districts = 8ownFunds = 9opponentFunds = 9opponentModel = 1return = [8,3,0,9,12,0,0,0,1,2,2,2,2,0,0,0,0,0,0,0,9]

The opponent has one district with 2 funds and seven with 1, giving 8 possible vectors. The best own allocation is [0,0,0,1,2,2,2,2]: it wins when the opponent puts its 2 in one of your three zero districts, so the probability is 3/8. The minimum own budget with positive chance is 9, rather than 10; tied districts make a majority of all eight districts unnecessary. A balanced opponent budget of 12 blocks every own allocation of budget 9.

Example 3

districts = 1ownFunds = 0opponentFunds = 0opponentModel = 0return = [1,0,0,1,0,0,0]

Both campaigns allocate zero, so the only district ties and neither allocation wins. One own fund would beat a balanced zero-budget opponent. An own budget of zero is already blocked by opponent budget zero.

Example 4

districts = 1ownFunds = 2opponentFunds = 1opponentModel = 1return = [1,1,1,2,2,2,2]

In one district, the unique own allocation [2] beats the unique opponent allocation [1]. Both best and worst therefore win. The minimum winning own budget and the first blocking opponent budget are both 2.

Constraints

For this exercise, assume 1 <= districts <= 8, 0 <= ownFunds <= 12, and 0 <= opponentFunds <= 30.
opponentModel is 0 or 1. For model 0, additionally assume districts <= 4 so direct enumeration is practical.
Districts are labeled; opponent permutations count separately unless their full vectors are identical.
Output budget thresholds may exceed the input-budget bounds. Use exact integer counts, with no modulus and no floating-point probability rounding.