Elections with Partial Information
Level: L3-L4 Topics: Greedy, Range Analysis, Logic, Edge Cases
Problem Statement
An election has multiple candidates and multiple voting districts. Each district counts its votes independently but only reports the top N candidates (with their vote counts) to the central authority. Candidates outside the top N in a district are not reported — their exact vote counts are unknown.
The central authority must determine the overall winner or declare that it is impossible to determine a winner given the incomplete information.
A candidate is the definitive winner if, no matter what the unreported votes could be, that candidate has strictly more total votes than every other candidate.
Background & Constraints
- Each district's top N list is sorted by vote count in descending order.
- The N-th (last) candidate in a district's list provides a threshold: any unreported candidate in that district received at most that many votes.
- A candidate's minimum total is the sum of votes explicitly reported across all districts.
- A candidate's maximum total is their minimum total plus the sum of thresholds from districts where they were not reported.
- A candidate not appearing in any district's list could still exist (an "outsider") with a maximum of the sum of all district thresholds.
Examples
District A (Top 3):
| Rank | Candidate | Votes |
|---|---|---|
| 1 | Alice | 50 |
| 2 | Bob | 30 |
| 3 | Carol | 20 |
Threshold A = 20
District B (Top 3):
| Rank | Candidate | Votes |
|---|---|---|
| 1 | Alice | 40 |
| 2 | Dave | 35 |
| 3 | Bob | 10 |
Threshold B = 10
Analysis:
| Candidate | Min Total | Max Total | Notes |
|---|---|---|---|
| Alice | 90 | 90 | Present in both |
| Bob | 40 | 40 | Present in both |
| Carol | 20 | 30 | Missing in B (+10) |
| Dave | 35 | 55 | Missing in A (+20) |
| Outsider | 0 | 30 | Missing in both (+20+10) |
Alice's minimum (90) exceeds everyone's maximum (Dave's 55 is highest). Winner: Alice.
Hints & Common Pitfalls
- Calculate two values for each candidate: minimum score (guaranteed votes) and maximum score (potential votes).
- A candidate wins if and only if their minimum exceeds every other candidate's maximum (strict inequality).
- Do not forget "outsider" candidates who appear in no list at all — their maximum is the sum of all thresholds.
- A common mistake is using average or most-likely estimates instead of worst-case bounds.
- Ties (minimum equals another's maximum) mean it is impossible to determine a winner.
Follow-Up Questions
- Complexity: What is the time complexity in terms of the number of districts
Dand the top-N size? Can you process this in O(D * N)? - More than 2 districts: The algorithm naturally extends to any number of districts. Walk through an example with 3 or more districts.
- Unlocked parameters: What if different districts report different numbers of top candidates (N varies per district)? How does this affect threshold computation?
- Can a fully invisible candidate win? Is it possible for a candidate who appears in zero top-N lists to be declared the winner? Under what conditions? (Hint: only if the sum of all thresholds exceeds the minimum of every visible candidate, AND no visible candidate's minimum exceeds this sum — this is extremely unlikely but theoretically possible with very small lists.)