PROBLEM LINK:Author: Praveen Dhinwa 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:
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 selfvotes. Let's handle first the case where a selfvote 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 selfvote 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 solutionThe author's solution starts from any voting satisfying the $c_i$s, but possibly with selfvotes. Let $F[i]$ be the person who $i$ voted. We will try to amend the assignment to remove the selfvotes 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 selfvote. 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 selfvotes, then set $F[i_1] = i_2$, $F[i_2] = i_3$, ... $F[i_{b1}] = i_b$ and $F[i_b] = i_1$. The editorialist's solutionHere 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_{n1}$. Now, iterate $i$ from $n1$ 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 selfvotes (assuming the person described above always exists). Second, $c_{s_{n1}} > 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} > ni$$ 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 MaxFlowThis 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:
This question is marked "community wiki".
asked 23 May '15, 16:16

Solution using MaxFlow 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. answered 23 May '15, 18:12

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. answered 23 May '15, 18:05
Yes, I know this problem but forgot its name. Thanks!
(23 May '15, 18:06)
1
I felt somewhat bad after seeing somewhat uglier in heading, when your solution description starts.
(23 May '15, 18:14)
I edited it. Thanks :)
(23 May '15, 18:19)

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.
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. answered 23 May '15, 17:31
By the way, I have removed the graph terms for the most part of the editorial so it's simpler to read. :)
(23 May '15, 18:24)
@kevinsogo: Yes, Thanks a lot. This renders this comment mostly useless.
(23 May '15, 19:00)

Can somebody point out my mistake? http://ideone.com/LHGfGD answered 23 May '15, 16:59

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 answered 23 May '15, 17:12

My solution got SIGABRT. Can someone point out the mistake? answered 23 May '15, 17:19

can some one point out the mistake in this? got a tle http://www.codechef.com/viewsolution/7005217 answered 23 May '15, 17:39

Cant we do this problem like this? http://pastebin.com/tA2hGeRX answered 23 May '15, 19:32

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 , All the 'assignments' mentioned in the above paragraph can be stored in the previously declared array 'ans[]'. k=0; for(i=N1;A[i].vote==0;i); //to find the last person with nonzero vote
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 answered 23 May '15, 19:55

I'am getting a runtime error(SIGSEGV) on submitting it while its working good on my system.can anyone help thanks in advance http://ideone.com/Drq8Y5 answered 23 May '15, 20:05

I passed it with a very very simple solution (in my mind). First I have two sets: One contains persons was voted V1[], the other contains persons wasn't voted V2[] (I have already checked whether sum of all is equal n or not, or whether there are any an element equals to n or not). Then with V1[], I will always have more than one element, then I will set this: The person V1[i] will voted V1[i+1] with V1.Size()>=i>=1. V1[V1.Size()+1]=V1[1], respectively. In this process, I'll decrease C[v1[i+1]] one. With V2[], For all ielement in V2[], I will set V2[i] voted V1[j], with C[v1[j]]>0. Time complexity: O(t * n * n) My code: http://ideone.com/LwkheX answered 23 May '15, 20:42

http://www.codechef.com/viewsolution/7000949. I used a simple method . Let's take a test case. 1 5 1 0 2 0 2 so we get 1 3 3 5 5,I stored this data in an array called cnt. Now I checked whether cnt is matching given sets of condition , if yes print the array, if no move first element to last and update our array i.e 3 3 5 5 1. Now we check again and this time condition is fulfilled so we need to print the array. By this method total n voting pattern are possible for n voters. Example 1 3 3 5 5 3 3 5 5 1 3 5 5 1 3 5 5 1 3 3 5 1 3 3 5 Before this step we need to check whether sum is equal to n or not and any element of array is not equal to n. Sorry for my bad English. answered 23 May '15, 22:46

This is working for all test cases .Still WA...It would be helful if anyone can tell the error.. include<bits stdc++.h="">using namespace std; struct data { int g; int pos; }; bool myfunc(struct data e,struct data d) { return e.g>d.g; } int main() { int t,n; scanf("%d",&t); while(t) { scanf("%d",&n); int a[n],b[n]; int visited[n],i,j,s=0,f=0; data c[n]; for(i=0;i<n;i++) {="" scanf("%d",&a[i]);="" c[i].g="a[i];" c[i].pos="i;" visited[i]="0;" s="s+a[i];" if(a[i]="">=n) f=1; } if(s!=n  f==1) printf("1\n"); else { sort(c,c+n,myfunc); /for(i=0;i<n;i++) printf("%d %d\n",c[i].g,c[i].pos);/ for(i=0;i<n;i++) { for(j=c[i].pos+1;j<n;j++) { if(c[i].g==0) break; if(visited[j]==0) { c[i].g; visited[j]=1; b[j]=c[i].pos+1; } } for(j=0;j<c[i].pos;j++) { if(c[i].g==0) break; if(visited[j]==0) { c[i].g ; visited[j]=1; b[j]=c[i].pos+1; } } } for(i=0;i<n;i++) printf("%d ",b[i]); printf("\n"); } } return 0; } answered 24 May '15, 11:08

hello sir. please help me where i made a mistake . i not able to know my mistake. after submitting my code i am getting wrong answer but i am not able to know where my mistake is? please help me . here is the link to my solution: http://www.codechef.com/viewsolution/7009808 answered 24 May '15, 13:56

can anyone point the mistake? http://www.codechef.com/viewsolution/7002864 answered 24 May '15, 18:13

I can't find mistake in following solution
answered 24 May '15, 19:59

answered 25 May '15, 05:07

@kevinsogo : Please, provide me test cases where this solution fails. answered 25 May '15, 05:20

@dpraveen : Please show me a test case where my solution fails. answered 25 May '15, 15:43

Somebody plz tell me the problem with this answer.i am getting wrong answer.i tried everything http://www.codechef.com/viewsolution/7068018 answered 02 Jun '15, 23:48

Somebody plz tell me the problem with this answer.i am getting wrong answer.i tried everything http://www.codechef.com/viewsolution/7068018 answered 02 Jun '15, 23:50

My soln can anybody clarify the testcase it will fail, my code is here https://ideone.com/nDTg7t thank you in advance P.S. i just need a test case on which it fails. answered 04 Jun '16, 17:41

https://www.codechef.com/viewsolution/13092836. can somebody tell me my mistake answered 14 Mar '17, 19:44

https://www.codechef.com/viewsolution/14414054 can someone tell what is wrong with my code i am using the simple algorithm for switching the no. if a[i] == i i am still betting wrong answer answered 06 Jul '17, 03:29

Hi , i don't know if anyone has done this question in this way or not ,but here is my solution : https://www.codechef.com/viewsolution/19279294 I have just continuously assigned each voter to the candidates in the same order 0,1,...n1 , and if the voter and the candidate turn out to be same, i have matched them with the next one .In this way ,what happens is there are only two possibilities either one of them is left with self voting or no one . if only one of them is left(say x) , we can easily just find a voter(say a) who didn't vote x and voted y and change the array in this way : x voted a, and a voted y. in this way , the remaining vote of a is used up and everything else remains in the same order . answered 20 Jul '18, 01:15

O(t*n^2) http://www.codechef.com/viewsolution/7011638 TLE please clarify what mistake i am doing