SEAVOTE - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Shiplu Hawlader
Editorialist: Lalit Kundu

DIFFICULTY:

EASY-MEDIUM

PRE-REQUISITES:

Maths

PROBLEM:

Sereja conducted a voting about N of his opinions. Ai percent of people voted for opinion number i. This statistics is called valid if sum of all Ai is equal to 100.

Now let us define rounding up of a statistics A.

  • If Ai is not an integer, it will be rounded up to next integer.
  • Otherwise it will be left as it is.

Now let us consider a statistics B of size N in which each of Bi is an integer. Now he wants to know whether there exists some valid statistic A of size N (may contain real numbers) such that after rounding it up, it becomes same as B?

1 ≤ N ≤ 10000

EXPLANATION:

Let’s define a small positive infinitesimal quantity e(epsilon).
For Bi, corresponding element in array A can be in range [Bi-1+e,Bi](both ranges included).
However, Bi = 0, the above range is invalid, so we’ll ignore all zero elements. Let’s say size of the remaining array B(after removing 0s) is N.
We now consider the lower and upper bounds on the sum of all numbers in A(note: any real number between these bounds can be generated). So, if 100 lies within these bounds, then answer is yes.

LOWER BOUND:

Now, what is the minimum possible sum? It’s S = [sum over all Bi] - N(number of non-negative elements in B) + e. So, we get condition for validity that S ≤ 100. If we ignore the e, we get S = [sum over all Bi] - N(number of non-negative elements in B) < 100.

UPPER BOUND:

Now, what is the maximum possible sum? It’s S = sum over all Bi. So, we get one more validity condition that S ≥ 100.

Complexity: O(N).

SOLUTIONS:

Setter’s solution
Tester’s solution

Note: Some people were confused about bounds on array A. A was not even in input.

2 Likes

“This XML file does not appear to have any style information associated with it. The document tree is shown below.” I am using Firefox.

Practice and Contest links are of CHEFSTON and are interchenged.
The solutions are also of CHEFSTON and are not working.

There is no need to report it for each editorial: “According to editorialist’s answer it will be available a little later (as I understood for all problems).” Try let say in an hour or download someone’s ACed solution :wink:

1 Like

Why is this wrong? Doesn’t it satisfy the bounds as given in the editorial?

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

Hi,

Links are incorrect and redirecting to CHEFSTON…

I am deeply saddened by this problem… I did countless submissions and this was the first one which I think, follows the idea of the editorial apart from removing zeroes…

Was this (or any other of my submissions) the correct way to go apart from removal of zeroes?

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

Best,

Bruno

1 Like

My solution was as simple as that:

	if ( sum < 100 || sum > 100 + gz - 1) {
		return false;
	}
	return true;

where sum is the sum af all B[i]s, gz is number of elements > 0. There is one important thing to check - if B[i] is bigger than 100 answer is false.

My solution in Java.

3 Likes

this is wrong because of your conditions:

Try this, n=5 : 0,34,34,35,0 correct anser is NO. Your code gives YES. http://ideone.com/hStNEd
Actually you didn’t check the number of terms which are non zero. Only they can be rounded, as 0 means the integed is already 0.

I was also getting frustrated, but then I realised that what if some elements are 0, they can NEVER be formed by rounding off as negative stats are invalid. It gave the right approach to AC:
http://www.codechef.com/viewsolution/5818080

thanks :slight_smile:

A very short solution relatively, easy to understand. got AC.

first calculate the sum, then subtract 100 from it. also calculate n as the no.of non zero numbers.

so now if sum is greater than or equal to zero and sum is lesser than n, then print “yes”, else print “no”.

It is really as simple as that. MY SOLUTION

There is no need of anything like upper bound or lower bound or anything like that…

Feel free to understand the logic behind, its actually very simple

1 Like

I think this one was difficult, because I do not know how to test it properly… Any idea someone? Something what can be used for let say 10-20 elements and always returns correct answer, but without the logic above (in case I had no such idea yet)?

I was thinking about something like for every number B[i], A[i] is in ( B[i] - 1, B[i] ] (interval). So try all possibilities let say B[i] and B[i] - 1 + 1/n for each element is not good, while for 51 51 it return. Problem also is, that generating 10-20 random numbers from [0-100] interval easily exceeds 100 + n sum limit…

What I can do, it to test YES answers - start with double 100 and divide it randomly = divide by some random factor to get two numbers (with sum 100) and repeat the process till I have n numbers, so I’ll have array A. But I feel like this is not very good test…

you are a genius!

3 Likes

I think my solution was an easy one, no involving anything like comparisons with epsilon and even easy to test.

 for(i=0;i<n;i++)
{
cin>>ele;
if(ele!=0)
sum+=(ele);
else
cnt++;
}
if(sum==100)
cout<<"YES\n";
else if(sum<100)
cout<<"NO\n";
else
{
// for all numbers as 0 and sum>100 -ve contirbution will give the minimum sum.
sum= sum- (n-cnt);
if(sum<100)
cout<<"YES\n";
else if(sum>100)
{
if((sum+cnt)<100)  // taking care of elements whose value is zero
cout<<"YES\n";
else
cout<<"NO\n";
}
else
cout<<"NO\n";
}

Its just the matter of fact that I took care of negative contributions of the elements in the array B which can be zero.

I tried something like this, but this created problems as I used comparisons with float and double variables. But then the fact that “it is the second question of the contest with so many submissions”, I just thought the only thing that I am not given any decimal precision value. It can be any number of digits after decimal and thus I’ll be able to make 100 if possible as per the sum. So, I thought the below thing(my answer below).

I implemented the exact same thing. Kudos!

1 Like

this should be the easiest method

Why the range of B is [0,1000].
When sum of A is 100 and B is derived from A. Shouldn’t B’s range be [0,100].

@Damn_me could You explain why have u taken the condition sum+cnt <100

Hi @king_of_hacker can you please how you got this approach and why are you counting no.of zeors ? i didn’t understand that much .

Thanks and Regards
Prasad

http://discuss.codechef.com/questions/61451/seavote-approach-of-sumcnt refer this.

//