CHEFVOTE - Editorial

[kevinsogo]

PROBLEM LINK:

Contest
Practice

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 \not= 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[i] be the person who i voted. Assign F[i] 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] = i. Let j be another person such that F[j] \not= i (we can show that such a person always exists). Then swap F[i] 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 \not= 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[i] 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[i] = 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] = i. Let j be another person such that F[j] \not= 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[i] and F[j], i.e. set F[i] = 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

c_{s_{i+1}} + c_{s_{i+2}} + \cdots + c_{s_n} > n-i

This can be easily proven by induction and handling two cases: c_{s_i} = 0 and c_{s_i} \not= 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)

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

[azix6]

Can somebody point out my mistake?

Ideone.com

[baljitsingh]

My solution got tle. it has O(n^2) complexity. The editorialist has mentioned that O(n^2) solution should pass. Please point out the mistake. Thanks in advance
http://ideone.com/u8iyTF

[MSKD96]

My solution got SIGABRT. Can someone point out the mistake?

http://www.codechef.com/viewsolution/7005761

[Sandeepripping]

I used max-flow to solve this problem… :P. it just goes to show that there is yet one more solution .

[dpraveen]

oh, thats cool I also once used max flow in tc for Div 2 level 2 problem

[jaswanthi]

Can you make the solutions source code accessible ( the links pointing to S3)

I couldn’t figure out the case where the following will fail.

int res[] = new int[tn];
for(int i = 0; i < tn; i++ ) {
	int j =( i+1) %tn;
	for(int k = 0; k < tn; j = (j +1) % tn, k++) {
		if( i != j) {
			if(a[j] > 0) {
				res[i] = j + 1;
				a[j]--;
				break;
			}
		}
	}
}

[dpraveen]

Please find my first editorial draft for the problem. In strict sense, it is just kind of repetition of Kevin’s editorial’s “Author’s solution” section.

For creating a real voting for a given distribution, I do the following.

Let us first create a random voting which respects just the count of number of votes of persons (i.e. just the voting distribution only). We want to make it to correspond to some actual voting.

Let call a vote of a person bad, if he has voted to himself. Let b denotes number of bad votes in current distribution of votes. Now, we will iteratively reduce value of b until it becomes 0 which is what we want.

• If b \geq 2, then we pick any two people i, j who have voted to themselves. We will interchange their votes, it will make both the votes valid and reduce value of b by 2. Note that it does not effect the count of votes at all.

• If b = 1, Let the person who has voted to himself be person i. Now, we will find a person j such that j does not vote to i. This will not exist in the case when there is only a single person and also in the case, when all persons voting for a single person. So answer in those cases is -1. Now, we will swap votes of these two persons as done in the previous step.

The algorithm will terminate in at most n iterations because in each iteration it reduces b by at least 1 (As maximum value of b could be n).

This can be implemented in \mathcal{O}(n^2). Even worse implementations are also considered e.g. \mathcal{O}(n^3). Please note that this can also be implemented in \mathcal{O}(n) by using the trick of making \lfloor \frac{b}{2} \rfloor swaps in a single step which is mentioned more clearly in the editorial.

[harpreetpec]

can some one point out the mistake in this? got a tle
http://www.codechef.com/viewsolution/7005217

[fauzdar65]

yes me too… it is much cleaner

[freeman92]

I think the editorialist’s solution is somewhat in the lines of Digraph realization problem.
And this problem is specific case of digraph realization problem where out degree of each vertex is one. May be we can add this as a prerequisite in the editorial.

[kevinsogo]

Yes, I know this problem but forgot its name. Thanks!

[fauzdar65]

Solution using Max-Flow

Create two sets of the n persons and 2 more vertices, sink and source. The capacity of all edges from source to first set would be 1, since 1 vote is available to each person.
The capacity of each vertex from the second set to the sink would be the no. of votes the person corresponding to that vertex got.

Capacity of all vertices from first set to second set would be 1, except for vertices with same index,they would be zero since a person can’t vote for themselves.

Finally, compute maximum flow in this graph, it should be equal to N if solution is possible. Possible solution can be generated using the status of capacities of edges after computing max flow.

[freeman92]

I felt somewhat bad after seeing somewhat uglier in heading, when your solution description starts.

[kevinsogo]

I edited it. Thanks

[kevinsogo]

By the way, I have removed the graph terms for the most part of the editorial so it’s simpler to read.

[kevinsogo]

Try the case n = 3, c1 = 0, c2 = 1 and c3 = 2 . Your code will assign 1 to 2, but the only solution is to assign 1 to 3, 2 to 3 and 3 to 2.

[dpraveen]

@kevinsogo: Yes, Thanks a lot. This renders this comment mostly useless.

[urdarinda]

Cant we do this problem like this?
http://pastebin.com/tA2hGeRX

[sharad07]

I just used basic sorting technique.

Assume ‘A’ containing votes distribution : 2 2 0 1 0

index(person number) : 1 2 3 4 5

Bind these two into a structure namely ‘distr’ (this is the structure name that I have used in my code).

Now sort the array of the above type.

After sorting, A[].vote has : 2 2 1 0 0

A[].index has : 1 2 4 3 5

let there be another array namely ‘ans[]’.
now ,
Since person 1 ie, A[1].index has 2 votes we assign this index number to the next two persons.With this we assumed that person 2 and person 4 has voted for person 1. Next person 2 has got 2 votes.So, we assign this index number to the next 2 persons and with this we assume that person 3 and person 5 has voted for person 2 and so on…And for the first person ie, the one at index 1,we assign him the person with the last non zero index ie, person 4 in this case.

All the ‘assignments’ mentioned in the above paragraph can be stored in the previously declared array ‘ans[]’.
k=0;
for(i=N-1;A[i].vote==0;i–); //to find the last person with non-zero vote

    ans[A[0].index-1]=A[i].index;
    for i=1 to N-1
       if(A[k].vote==0) k++;
       ans[A[i].index-1]=A[k].index;
       A[k].vote--;

ans[] : 4 1 2 1 2

ie, person 1 voted for 4th one…person 2 voted for 1st one and so on… print this array.

(Other constraints which result in -1 must be handled separately)

Link to my solution : http://www.codechef.com/viewsolution/7006678