NDLVOTE - Editorial

editorial
, , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

The 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,
which is just the vote he clicked now. Also, if we can reach a score of S, we can also reach -S ( all votes reversed ). So, we will try to get the score T = abs(S). If we have N users already and to get a total score of T,

1.) T >= N : All N users vote +1, still we need score of (T-N) more, so we need (T-N) more users
2.) T < N : Let some T out of N users vote +1. The remaining (N-T) users should contribute zero, which is possible only if (N-T) is even, else we need just one more user.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

2

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 up-voted.

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 up-voted.

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 down-vote, then we will have :

     p p p p p p p p = 8

     p p m m m m m m = -4

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 up-voted. (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 down-vote, then we will have :

   p p p p p p p p = 8

   p p m m m m m m = -4

Second, If 7 out of original 8 down-vote, then we will have :

   p p p p p p p p = 8

   p m m m m m m m = -6

So in order to get score of -5, we need to introduce a new user who can down-vote (when it is -4) or, up-vote (when it is -6).