You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFVOTE - Editorial

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

This question is marked "community wiki".

asked 23 May '15, 16:16

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 25 May '15, 00:15

admin's gravatar image

0★admin ♦♦
19.8k350498541

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

(24 May '15, 21:11) ankursmooth3★

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.

link

answered 23 May '15, 18:12

fauzdar65's gravatar image

2★fauzdar65
29114
accept rate: 21%

edited 23 May '15, 18:13

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.

link

answered 23 May '15, 18:05

freeman92's gravatar image

3★freeman92
2804711
accept rate: 0%

edited 23 May '15, 18:09

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

(23 May '15, 18:06) kevinsogo7★
1

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

(23 May '15, 18:14) freeman923★

I edited it. Thanks :)

(23 May '15, 18:19) kevinsogo7★

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.

link

answered 23 May '15, 17:31

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 23 May '15, 18:59

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) kevinsogo7★

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

(23 May '15, 19:00) dpraveen ♦♦4★

Can somebody point out my mistake? http://ideone.com/LHGfGD

link

answered 23 May '15, 16:59

azix6's gravatar image

2★azix6
102
accept rate: 0%

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

link

answered 23 May '15, 17:12

baljitsingh's gravatar image

3★baljitsingh
643719
accept rate: 0%

edited 23 May '15, 17:13

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

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

link

answered 23 May '15, 17:19

MSKD96's gravatar image

3★MSKD96
1
accept rate: 0%

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

link

answered 23 May '15, 17:19

Sandeepripping's gravatar image

4★Sandeepripping
1
accept rate: 0%

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

(23 May '15, 17:24) dpraveen ♦♦4★

yes me too... it is much cleaner

(23 May '15, 18:04) fauzdar652★

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;
            }
        }
    }
}
link

answered 23 May '15, 17:30

jaswanthi's gravatar image

2★jaswanthi
11
accept rate: 0%

edited 23 May '15, 18:46

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.

(23 May '15, 18:54) kevinsogo7★

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

link

answered 23 May '15, 17:39

harpreetpec's gravatar image

3★harpreetpec
1
accept rate: 0%

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

link

answered 23 May '15, 19:32

urdarinda's gravatar image

3★urdarinda
8116
accept rate: 0%

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

link

answered 23 May '15, 19:55

sharad07's gravatar image

4★sharad07
20711
accept rate: 3%

edited 23 May '15, 19:57

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

link

answered 23 May '15, 20:05

ankur_dhir95's gravatar image

4★ankur_dhir95
303
accept rate: 0%

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 i-element 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

link

answered 23 May '15, 20:42

leduongtuananh's gravatar image

2★leduongtuananh
12528
accept rate: 16%

edited 23 May '15, 20:45

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.

link

answered 23 May '15, 22:46

drathi5's gravatar image

3★drathi5
40310
accept rate: 6%

@baljitsingh check for ->
1
6
0 0 0 2 2 2

link

answered 24 May '15, 00:43

glow's gravatar image

3★glow
6312
accept rate: 0%

link

answered 24 May '15, 00:59

glow's gravatar image

3★glow
6312
accept rate: 0%

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; }

link

answered 24 May '15, 11:08

saurabhnit's gravatar image

3★saurabhnit
-21
accept rate: 0%

edited 24 May '15, 11:09

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

link

answered 24 May '15, 13:56

sutejadla's gravatar image

0★sutejadla
1
accept rate: 0%

can anyone point the mistake? http://www.codechef.com/viewsolution/7002864

link

answered 24 May '15, 18:13

sweetsammy's gravatar image

3★sweetsammy
1
accept rate: 0%

I can't find mistake in following solution

using namespace std;



int main()
{
    int T = 0;

    int N = 0;
    int sum = 0;
    int tmp = 0;
    bool flag = false;
    int arr[100];
    int arr1[100];
    cin >> T;

    for (int i = 0; i < T; i++)
    { 
        flag = false;
        sum = 0;

        cin >> N;
        for (int j = 0; j < N; j++)
        {
            cin >> arr[j];
            //sum += tmp;

            //if (sum>N || tmp >= N)
            //{
            //  flag = true;
            //}
        }

        for (int a = 0; a < N; a++)
        {
            sum += arr[a];

            if (arr[a] >= N)
            {
                flag = true;
                break;
            }


            if (sum > N)
            {
                flag = true;
                break;
            }

        }

        if (sum < N)
            flag = true;
        if (flag)
        {
            cout << -1 << "\n";
        }

        else
        {
            int count1 = 0;
            for (int a = 0; a < N; a++)
            {

                for (int b = 0; b < N; b++)
                {
                    if (b != a)
                    {
                        if (arr[b]>0)
                        {
                            arr[b]--;
                            cout << b + 1<<"\t";
                        }
                    }
                }


                /*
                if (arr[a] != 0 && a!=N-1)
                {
                    cout << a + 2<<" ";
                }
                else if (arr[a] != 0 && a == N - 1)
                {
                    cout << 1;
                }*/
            }
            cout << "\n";

        }

    }



    return 0;
}
link

answered 24 May '15, 19:59

v4_adi's gravatar image

2★v4_adi
11358
accept rate: 0%

   // int a[n]- is the input array for each test case
   // int k[n] - is the array which stores the output. 
    vector<int> k (n);
    fill (k.begin(),k.end(),-1);
    for(int j=n-1;j>=0;j--){
        int x=a[j];
        int m;
        m=j-1;
        if(k[0]!=-1)
            m=n-1;
        for (; m>=-1; m--){
            if(x==0)
                break;
            if(m==-1){
                m=n;
                continue;
            }                                                 
            if(k[m]==-1){
                k[m]=j;
                --x;
            }
        }
    } 
    // ans is printing k[j] + 1; in a loop from 0 <= j < n, j++
link

answered 25 May '15, 05:07

codecheftian's gravatar image

1★codecheftian
1
accept rate: 0%

@kevinsogo : Please, provide me test cases where this solution fails.

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

link

answered 25 May '15, 05:20

codecheftian's gravatar image

1★codecheftian
1
accept rate: 0%

@dpraveen : Please show me a test case where my solution fails.

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

link

answered 25 May '15, 15:43

codecheftian's gravatar image

1★codecheftian
1
accept rate: 0%

Somebody plz tell me the problem with this answer.i am getting wrong answer.i tried everything http://www.codechef.com/viewsolution/7068018

link

answered 02 Jun '15, 23:48

missbharti's gravatar image

2★missbharti
1
accept rate: 0%

Somebody plz tell me the problem with this answer.i am getting wrong answer.i tried everything http://www.codechef.com/viewsolution/7068018

link

answered 02 Jun '15, 23:50

missbharti's gravatar image

2★missbharti
1
accept rate: 0%

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.

link

answered 04 Jun '16, 17:41

int_aashish's gravatar image

4★int_aashish
1
accept rate: 0%

https://www.codechef.com/viewsolution/13092836.

can somebody tell me my mistake

link

answered 14 Mar '17, 19:44

akshay29's gravatar image

2★akshay29
894
accept rate: 0%

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

link

answered 06 Jul '17, 03:29

hardik0007's gravatar image

2★hardik0007
1
accept rate: 0%

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,...n-1 , 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 .

link

answered 20 Jul '18, 01:15

agniva_basak's gravatar image

3★agniva_basak
212
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×1,236
×968
×46
×14
×11

question asked: 23 May '15, 16:16

question was seen: 6,471 times

last updated: 20 Jul '18, 01:15