You are not logged in. Please login at www.codechef.com to post your questions!

×

NDLVOTE - Editorial

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.

This question is marked "community wiki".

asked 23 Nov '12, 14:49

admin's gravatar image

0★admin ♦♦
15.9k347484508
accept rate: 35%


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).

link

answered 21 Apr '16, 19:53

mesksr's gravatar image

5★mesksr
3
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,580
×2,608
×7
×1

question asked: 23 Nov '12, 14:49

question was seen: 2,109 times

last updated: 08 Oct, 01:48