### PROBLEM LINK:

**Author:** Praveen Dhinwa

**Tester:** Kevin Atienza

**Editorialist:** Kevin Atienza

### PREREQUISITES:

Graphs, ad hoc, digraph realization

### PROBLEM:

Each person votes for another person. Let c_i be the number of people who voted for i, for 1 \le i \le n. Find a possible voting (i.e. who each person voted) that will match the $c_i$s, or report that it is impossible.

For those who are curious, we can translate this into a graph problem: Given c_i for 1 \le i \le n, find a simple directed graph of n nodes where each node has an outdegree of 1 and an indegree of c_i, or report that it is impossible. The terms I used in the previous sentence are pretty standard and I’m sure you can search them online if you’re unfamiliar

### QUICK EXPLANATION:

If \sum_i c_i ot= n or \max_i c_i = n, it is impossible. Otherwise, it can be shown to be possible.

There are many possible constructions of the voting itself, but here is a simple one:

- Let F* be the person who i voted. Assign F* in any way to satisfy the c_i (it’s easy to do this), allowing people to vote for themselves for now.
- Let b be the number of people who voted for themselves. If b = 0, then we are done.
- If b \ge 2, then take all such people and set them all in a cycle among themselves. After this, we are done.
- Finally, if b = 1, then there is only one person who voted for himself. Let that be person i, i.e. F* = i. Let j be another person such that F[j] ot= i (we can show that such a person always exists). Then swap F* and F[j]. After this, we are done!

### EXPLANATION:

There are n voters and S := \sum_i c_i votes. Each person votes exactly once, hence for any valid voting, we must have n = S. Therefore, if n ot= S, then we immediately output -1 (impossible), and in the following, we assume n = S.

If n = S, it is easy to find and voting that satisfies the $c_i$s. However, it is possible that in the assignment we got, some people voted for themselves, and so our goal is to find a voting without any self-votes.

Let’s handle first the case where a self-vote is unavoidable: if \max_i c_i = n, it follows that there is exactly one nonzero c_i, and its value is n. Thus, all n people voted for i, so a self-vote from i to i is unavoidable. In this case, we also immediately output -1.

The remarkable thing is that in all other cases, there is a solution! We will describe a few possible constructions here.

# The (elegant) author’s solution

The author’s solution starts from *any* voting satisfying the $c_i$s, but possibly with self-votes. Let F* be the person who i voted. We will try to amend the assignment to remove the self-votes while still maintaining the other requirements.

Let b be the number of people who voted for themselves.

If b \ge 2, then we pick two such people i and j, and have them vote each other, i.e. set F* = j and F[j] = i. It can be seen that this does not violate the c_i constraints, but it reduces b by 2, so we do this step \lfloor b/2 \rfloor times until b becomes either 0 or 1. If b = 0, then we are done

Finally, if b = 1, then there is only one self-vote. Let that be person i, i.e. F* = i. Let j be another person such that F[j] ot= i (we will show that such a person always exists), and let k := F[j] (which is not equal to i and j). Then swap F* and F[j], i.e. set F* = k and F[j] = i. It can be seen that this does not violate the c_i constraints, but it reduces b to 0, and we’re done

Why does the person j in the previous paragraph exist? Well, if it didn’t, then all people j would have F[j] = i. This means that c_i = n, but we already excluded that case

The correctness of this algorithm easily follows from the things said above. This algorithm can be implemented in O(n) (but more naïve O(n^2) or O(n^3) implementations also pass).

Note that in the case b \ge 2, we can replace the \lfloor b/2 \rfloor steps above with a single step: just set the b people in a cycle amongst themselves, i.e. if i_1, i_2, \ldots, i_b are the people with self-votes, then set F[i_1] = i_2, F[i_2] = i_3, … F[i_{b-1}] = i_b and F[i_b] = i_1.

# The editorialist’s solution

Here we describe the editorialist’s solution which is not as simple as the author’s solution, but you may still find interesting nonetheless This just shows that there really are a lot of possible solutions to this problem.

First, if \max_i c_i = 1, then it can be seen that c_1 = c_2 = \cdots = c_n = 1, so we can just make a cycle among the n people.

Otherwise, sort the people according to c_i. let the sorted order of the people be s_1, s_2, \ldots s_n, i.e. c_{s_1} \le c_{s_2} \le \cdots \le c_{s_n} (note that 1 < c_{s_n} < n). First, have s_n vote for s_{n-1}. Now, iterate i from n-1 to 1, and for each i, assign s_i to some person later in the list s_j (i.e. i < j) such that the number of people we’ve currently assigned to vote for s_j is still less than c_{s_j}. It can be shown that such a person always exists.

Now, why is the algorithm above correct? First, we obviously don’t create any self-votes (assuming the person described above always exists). Second, c_{s_{n-1}} > 0, because otherwise, we will have c_{s_n} = n, which we already excluded. Moreover, we only assign a vote to some person k if it will not exceed the desired number of votes c_k. Finally, since \sum_i c_i = n, we see that the final number of votes to each person are correct!

We are left with proving that the person s_j above exists. To do so, we only need to prove the following fact: For any 1 \le i < n, we have

This can be easily proven by induction and handling two cases: c_{s_i} = 0 and c_{s_i} ot= 0.

Now, given that claim, we can easily prove the existence of the person s_j by noting that at each iteration i, there would not have been enough people later than s_i to exhaust all the desired votes of the later people, so there is always a person s_j which we can assign s_i to!

The time complexity of this algorithm is O(n \log n) dominated by the sort, but can be reduced to O(n) by using counting sort.

# Another Solution using Max-Flow

This part is taken from fauzdar65’s comment in the thread.

Create two nodes for each of the n persons, plus two more nodes: a sink and a source. We add edges from the source to each node in the first set, each with capacity 1, since 1 vote is available to each person.

We also add edges from each node from the second set to the sink, and the capacity of each would be the number of votes the person corresponding to that node got, i.e. c_i.

We also add edges from nodes from the first set to nodes from the second set, each with capacity 1, but we don’t add edges to nodes representing the same person since a person can’t vote for themselves.

Finally, compute the maximum flow in this graph. It should be equal to n if a solution is possible. A possible solution can then be recovered by checking the flow from nodes from the first set to the second.

### Time Complexity:

O(n^3), O(n^2), O(n \log n), or O(n)