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

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

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

2 Likes

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ā€¦

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.

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

Can someone explain thisā€¦
if n=11 : 10 10 10 10 10 10 10 10 10 10 10
Then how the ans is ā€œYESā€ā€¦ !

Was getting WA because of lower bound inequality. Changed it to strict inequality and got AC

I have big problem debugging my code

(WA) CodeChef: Practical coding for everyone
(AC) CodeChef: Practical coding for everyone

The only difference between two codes is ā€˜is there is break or notā€™
if(t > 100) {
invalid = true;
break;
}

But I think this break shouldnā€™t change the output because once invalid becomes true, it should print ā€œNOā€ whatever the value of sum or cut is. So I donā€™t understand why the first code and the second code is making different output.
Can someone help me please?

My solution is not passing test case 6 and 7. Help me with a test case. A link to my


[1]


  [1]: https://ideone.com/DtkObn

Thank you.

Just see if the sum of all the elements of the array b is 100,greater than 100 or less than 100.

case 1: If itā€™s 100,just print YES.

case 2: If itā€™s less than 100,then print NO as while rounding off the elements of A will be less than(marginally) with respect to B. Hence itā€™s not possible to come up with any array A whose sum will be equal to 100.

case 3:If itā€™s greater than 100,then we have to see by how much does it exceeds 100. Then we would calculate the number of non-zero elements in the array B.Note: We calculate non-zero numbers in array B because the element 0 cannot be manipulated to anything. After that we divide the extent by which sum of elements exceeds 100 by total number of non-zero elements. That would give us the number by which we will have to decrease each element. Now we know each element cannot be decreased by more than 0.999. If the number by which we need to decrease each of the element is less than 1 ,then print YES else print NO.

4 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

this is wrong because of your conditions:

Try this, n=5 : 0,34,34,35,0 correct anser is NO. Your code gives YES. hStNEd - Online C++ Compiler & Debugging Tool - Ideone.com
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: