🗳️ Problem Statement

There is an election going on, and there is a single central authority (which gives the results) and two voting districts.

Each district collects and counts its votes, ranks the results (effectively, running a single-district version of the elections), and sends them up to the central authority for the final results.

The Trick: The results from the voting districts are truncated. Specifically: only the Top N (e.g., N=5) ranked candidates get sent to the central authority (along with their vote counts).

The Task: Implement the central authority algorithm, which is to designate the winner or declare that it is impossible to do that.

📝 Example Scenarios

Scenario 1: The "Impossible" Case (Close Race)

In this case, the hidden votes create enough uncertainty that we cannot be sure who won.

District A

aa = 10
bb = 9
cc = 9
dd = 8
jj = 3

(Threshold A = 3)

District B

mm = 11
nn = 9
oo = 8
jj = 7
dd = 4

(Threshold B = 4)

Result: Impossible (Candidate 'aa' might have won, or 'mm', or 'dd'. The range of uncertainty overlaps).

Scenario 2: The "Possible" Case (Clear Winner)

In this case, the winner's lead is larger than the maximum possible hidden votes.

District A

Alice = 100
Bob = 10
Charlie = 5
Dave = 5
Eve = 2 (Threshold A = 2)

District B

Alice = 80
Frank = 8
George = 8
Harry = 7
Ivy = 5 (Threshold B = 5)

Result: Alice

Alice Min: 100 + 80 = 180.
Bob Max: 10 + 5 (Max hidden in B) = 15.
Outsider Max: 2 (Threshold A) + 5 (Threshold B) = 7.
Since 180 > 15, Alice is the definitive winner.

1. The Core Logic: Range Analysis

Since we receive partial data, we cannot calculate a single exact score for every candidate. We must calculate a score range [Min, Max].

📉 Lower Bound (MinScore)

This is the "Guaranteed" score.

Principle: Sum the votes we explicitly see in the Top N lists.
Missing Data: If a candidate is missing from a district's Top N, we assume they got 0 votes in that district.
Formula: MinScore(C) = Sum(Votes Explicitly Seen)

📈 Upper Bound (MaxScore)

This is the "Potential" score.

Principle: We must give the candidate the maximum benefit of the doubt.
The Threshold Rule: The vote count of the N-th (last visible) person in a district is the Threshold (T). If a candidate is missing from that district, they could have received any number of votes up to T.
Formula: MaxScore(C) = MinScore(C) + Sum(Thresholds of districts where C is missing)

🏆 The Condition for Victory

To declare a definitive winner, one candidate must be mathematically "untouchable." Candidate W is the winner if and only if:

\[MinScore(W) > MaxScore(O)\]

For all other candidates O (including potential unknown outsiders).

2. Example Walkthrough (Scenario 1)

Let's trace the logic using the "Impossible" example input above.

District A (Top 5)	District B (Top 5)
aa: 10	mm: 11
bb: 9	nn: 9
cc: 9	oo: 8
dd: 8	jj: 7
jj: 3	dd: 4
Threshold A = 3	Threshold B = 4

📊 Analysis Table

Candidate	Dist A	Dist B	Min Total (Guaranteed)	Max Total (Potential)	Logic
aa	10	?	`10 + 0 = 10`	`10 + 4 = 14`	Missing in B (Max hidden = 4)
mm	?	11	`0 + 11 = 11`	`3 + 11 = 14`	Missing in A (Max hidden = 3)
dd	8	4	`8 + 4 = 12`	`12 + 0 = 12`	Present in both (Exact score)
jj	3	7	`3 + 7 = 10`	`10 + 0 = 10`	Present in both (Exact score)

🏁 Conclusion

dd (Min 12) is the leader based on guaranteed votes.
However, aa could have up to 14 votes (if they got 4 hidden votes in District B).
And mm could have up to 14 votes (if they got 3 hidden votes in District A).
Since Max(aa) > Min(dd) and Max(mm) > Min(dd), we cannot declare dd the winner.
Result: Impossible

3. Extension: Handling N-Districts

If there are K districts instead of 2, the logic remains linear O(K * N).

Step 1: Precompute thresholds[i] for all districts i = 0...K-1.
Step 2: Start with MinScore (sum of visible votes).
Step 3: Iterate through all districts. If the candidate is missing from district i, add thresholds[i] to calculate the MaxScore.

4. Follow Up: The "Eligibility Constraint" (P Districts)

This variation adds a rule: A candidate can only receive votes in at most P districts.

Best for: Scenarios with strict registration rules.
Logic Change: We switch from a "Sum All Missing" approach to a Greedy Approach.

🧠 The Greedy Logic

Track Presence: Count how many districts (K_seen) the candidate explicitly appears in.
Calculate Remaining Slots: R = P - K_seen.
Greedy Selection:
- If R <= 0, they get 0 hidden votes.
- If R > 0, identify all districts where they are missing.
- Sort the thresholds of those districts.
- Pick the Top R largest thresholds and add them to the score.

Practice & Edge Cases

🧪 Common Scenarios

1. The Clear Winner

Scenario: Candidate A leads by 100 votes. The thresholds of missing districts sum up to only 50.
Result: Alice (The gap is larger than the uncertainty).

2. The Short List (Threshold = 0)

Scenario: District B only reports 2 candidates, even though N=5.
Logic: This implies only 2 candidates received votes. The Threshold for District B is 0.
Result: Certainty increases (ranges become tighter).

3. The Empty District

Scenario: One district provides no data (empty list).
Logic: Threshold is 0. However, usually, if a district is empty, the logic holds. But note: if all districts are empty, Impossible.

4. The Outsider

Scenario: Can a candidate exist who is not on any list?
Logic: Yes. Their Max Score is Sum(All Thresholds). If the current leader's Min Score is less than this sum, the result is Impossible.

🛠️ Interview Toolkit: Key Checks

Here is a cheat-sheet for edge cases and clarifications during an interview.

Ambiguity of "Truncated": If list.size() < N, assume the list is complete (Threshold = 0).
Strict Inequality: Tie = Impossible.
Data Structure: Use unordered_map (Hash Map) for O(1) lookups.

💻 Appendix: Solution Code

A. Solution for N-Districts (General)

Click to expand solution code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

using namespace std;

struct VoteEntry {
    string name;
    int votes;
};

// Generalized function for N districts
string solveNDistricts(const vector<vector<VoteEntry>>& districts) {
    unordered_map<string, int> minTotal;
    vector<int> distThresholds;
    unordered_set<string> allNames;

    // 1. Precompute thresholds and sum guaranteed votes
    for (const auto& dist : districts) {
        distThresholds.push_back(dist.empty() ? 0 : dist.back().votes);
        for (const auto& entry : dist) {
            minTotal[entry.name] += entry.votes;
            allNames.insert(entry.name);
        }
    }

    // 2. Check every candidate against all others
    for (const string& cand : allNames) {
        int myMin = minTotal[cand];
        bool beatsAll = true;

        for (const string& opp : allNames) {
            if (cand == opp) continue;

            // Calculate opponent's theoretical MAX
            int oppMax = minTotal[opp];

            // Add potential votes from districts where opponent is missing
            for(size_t i=0; i<districts.size(); ++i) {
                bool present = false;
                // Opt: In production use map<string, set<int>> for O(1) checks
                for(const auto& v : districts[i]) {
                    if(v.name == opp) { present = true; break; }
                }

                if (!present) {
                    oppMax += distThresholds[i];
                }
            }

            if (myMin <= oppMax) {
                beatsAll = false;
                break;
            }
        }
        if (beatsAll) return cand;
    }

    return "Impossible";
}

B. Solution with P-Constraint (Eligibility Limit)

Click to expand solution code

string solveWithPConstraint(const vector<vector<VoteEntry>>& districts, int P) {

    // 1. Precompute thresholds for all districts
    vector<int> districtThresholds;
    for (const auto& d : districts) {
        if (d.empty()) districtThresholds.push_back(0);
        else districtThresholds.push_back(d.back().votes);
    }

    // 2. Aggregate Known Data
    unordered_map<string, int> minTotal;
    unordered_map<string, unordered_set<int>> districtsSeen;
    unordered_set<string> allCandidates;

    for (int i = 0; i < districts.size(); ++i) {
        for (const auto& entry : districts[i]) {
            minTotal[entry.name] += entry.votes;
            districtsSeen[entry.name].insert(i);
            allCandidates.insert(entry.name);
        }
    }

    // 3. Compute Max/Min using Greedy Logic
    struct Range { int minS; int maxS; };
    unordered_map<string, Range> ranges;

    for (const string& cand : allCandidates) {
        int currentScore = minTotal[cand];
        int seenCount = districtsSeen[cand].size();

        int slotsRemaining = max(0, P - seenCount);
        int potentialHiddenVotes = 0;

        if (slotsRemaining > 0) {
            // Collect thresholds of districts where this candidate is MISSING
            vector<int> availableThresholds;
            for (int i = 0; i < districts.size(); ++i) {
                if (districtsSeen[cand].find(i) == districtsSeen[cand].end()) {
                    availableThresholds.push_back(districtThresholds[i]);
                }
            }

            // GREEDY: Sort descending to pick the biggest potentials
            sort(availableThresholds.rbegin(), availableThresholds.rend());

            for(int i=0; i < availableThresholds.size() && i < slotsRemaining; ++i) {
                potentialHiddenVotes += availableThresholds[i];
            }
        }

        ranges[cand] = { currentScore, currentScore + potentialHiddenVotes };
    }

    // 4. Determine Winner
    for (const auto& [candName, candRange] : ranges) {
        bool distinctWinner = true;
        for (const auto& [oppName, oppRange] : ranges) {
            if (candName == oppName) continue;

            if (candRange.minS <= oppRange.maxS) {
                distinctWinner = false;
                break;
            }
        }
        if (distinctWinner) return candName;
    }

    return "Impossible";
}