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;
}
}
}
}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.
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.
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.
Cant we do this problem like this?
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 : CodeChef: Practical coding for everyone
I’am getting a runtime error(SIGSEGV) on submitting it while its working good on my system.can anyone help
thanks in advance
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: LwkheX - Online C++ Compiler & Debugging Tool - Ideone.com
CodeChef: Practical coding for everyone.
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.
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;
}
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:- CodeChef: Practical coding for everyone
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;
}// int a[n]- is the input array for each test case
// int k[n] - is the array which stores the output.
vector 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++
Somebody plz tell me the problem with this answer.i am getting wrong answer.i tried everything
http://www.codechef.com/viewsolution/7068018