PROBLEM LINKSDIFFICULTYEASY EXPLANATIONThe score starts with 0 and we are given total score after each of Po's clicks and we need to find the minimum number of users other than Po that could have possibly voted. The important thing to notice is, we just need to maintain the total number of users so far that have voted at least once, and we have the freedom to assign +1 or 1 to each of them :). We can get the total score of users other than Po by just subtracting Po's vote, 1.) T >= N : All N users vote +1, still we need score of (TN) more, so we need (TN) more users SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 23 Nov '12, 14:49

Here are examples explaining the different cases : First Example: (for T >= N case) 2 P 4 P 9 Here, after removing Po's vote, we have score of 3. So, there must be 3 different users, who all have upvoted. Next, after removing Po's vote, we have score of 8. How can be go from 3 to 8?? We need to introduce 5 new users. Second Example: (for T < N case) 2 P 9 P 3 Here, after removing Po's vote, we have score of 8. So, there must be 8 different users, who all have upvoted. Next, after removing Po's vote, we have score of 4. How can be go from 8 to 4?? Since, (abs(8)abs(4)) = 4 is even, it is possible to get this score without introduction of any new user. If 6 out of original 8 downvote, then we will have :
Third Example: (for T < N case) 2 P 9 P 4 Here, after removing Po's vote, we have score of 8. So, there must be 8 different users, who all have upvoted. (Same as before) Next, after removing Po's vote, we have score of 5. How can be go from 8 to 5?? Since, (abs(8)abs(5)) = 3 is odd, it is NOT possible to get this score without introduction of any new user. Possible cases : First, If 6 out of original 8 downvote, then we will have :
Second, If 7 out of original 8 downvote, then we will have :
So in order to get score of 5, we need to introduce a new user who can downvote (when it is 4) or, upvote (when it is 6). answered 21 Apr '16, 19:53
