Team split-wrong answer

general
1

getting wrong answer.Link to my solution is http://www.codechef.com/viewsolution/3615465.Please help

2

first of all according to the question you will have to sort your s[] array and then do the even odd thing. but you can optimize it by the fact that since you will have to take “mod” by 1000000 hence you can take a buckets and increment the count of the corresponding bucket. (eg. bucket[s[i]]++). Then traverse in the bucket in decreasing order. here is my code snippet

    a[0]=d;
    for(i=1;i<n;i++)
{
	s=(A*s*s+b*s+c)%mod;
	// cout<<s<<' ';
	a[s]++;
}
j=1;
s=0;
for(i=1000000;i>=0;i--)
{
	a[i]%=2;
	if(a[i]>0)
	{
	if(j==1)
	{
	s+=i;
	j=-1;
	}
	else
	{
	s-=i;j=1;
	}
	}
}
just keep a flag while coming down as to who will get the number. if there are even numbers in the bucket then they will cancel out else you have to check the flag to put the remaining number in one of the teams
3

how can u assume that numbers are in increasing order in ur array…u r taking mod by 1000000…the values can fluctuate…and hence the array may not be sorted…hope this helps…:slight_smile:

2 Likes
4

@qwerty1 can u pls explain why you have used a[i]%=2; in the 2nd loop i mean the need for it …

5

If there are 0 or 2 or 4… pairs of same numbers, equal number of players of equal strength would go to each team and would cancel out. So you are interested in just knowing whether number of players in bucket are even or odd.