### bhishma's blog

By bhishma, history, 4 years ago, , Problem Link : PMARK

Can anyone please help me with an approach to this problem . I was thinking about it for about 2 days but I couldn't come up with a solution . And is there a general approach to these type of problems .

UDP: Thank you guys for clarifying my doubts. easy, help, Comments (14)
 » 4 years ago, # | ← Rev. 2 →   You can do this problem by simple math , say we have n subjects then ( sum of n subjects mark ) % n == 0 we can say we can set equal marks for all n subject otherwise here n — 1 is always possible .
•  » » How can we say that we can make n-1 subjects when ( sum of n subjects mark ) % n != 0
•  » » » suppose we have two values a, b. Can you change b to any value you desire using a?
•  » » » » I just tried your solution it resulted in Wrong answer
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   yeah dustbite , because even negative marks are allowed
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   I will give you an intuitive explanation.
•  » » » » » 4 years ago, # ^ | ← Rev. 7 →   Suppose the array is A = {a1, a2, a3, a4, ...., an}. The only operation allowed is take two elements ai, aj and replace ai by ai-1 and aj by aj+1 or vice versa. Let's take sum S = a1 + a2 + .... + an. We can see that after each such operation, sum remains same because we increase one element whereas decrease the other by 1.Also notice that if we fix an element a1, we can use it to set rest of the elements to a given value. So, we can make at least (n-1) elements same. Can we achieve n?Now, since we know that after such set of operations, final sum will be same and to achieve all equal we must have a1 = a2 = .... = an = k. Then k * n = S, which means sum must be divisible by n. This is a necessary condition. To see that it is sufficient too, we use previous knowledge. Lets make all a2, a3, ...., an to 0. Since sum is constant, we will have a1 = S after making rest of the elements 0. Now, we have found previously that using a1, we can make any of the element equal to some value which means we can use a1 to make a2 = k = S / n. Similarly we can make a3 = k = S / n. Finally after making all a2, a3,....an to S/n, a1 will be equal to S — (n-1)S/n = S/n. Thus all of them are equal. This proves (S % n == 0) is sufficient too.
•  » » » » » » Thanks for the great explanation !So the soln should be if(sum % n == 0) return n; else return n-1; But when I submitted it it resulted in WA
•  » » » » » » » Your sum might have overflowed.You may use long long / int64_t or use int to compute mod using modular arithmetic since (a1 + a2+a3...+an) % n = ((a1+a2) % n + rest) % n. and you won't need 64 bit integers.
•  » » » » » » » » Thanks a lot dude !! It finally worked , yeah the overflow caused the problem. Thanks for explaining it very clearly.
 » At first I didn't read that the elements could go negative and thought about the problem for sometime but could not come up with anything. Any Suggestions on how to solve the problem if all numbers had been positive and you could not make the an element < 0 ?
•  » » That won't change anything. The previous idea can still be applied.
•  » » » Yeah because sum can be written as sum = (sum/n)*n + (sum%n) so if sum% == 0 all the subjects can be made equal or else n-1 subjects can be made equal
 » Auto comment: topic has been updated by bhishma (previous revision, new revision, compare).