Editorial for Mock CCC '15 S1 - Dupvoting


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

If there are a dupvotes, b upvotes, and c downvotes, then this problem is asking for how many ordered triplets of (a, b, c) satisfy the following system of equations:

\displaystyle 2a + b - c = P \displaystyle a + b + c = U \displaystyle x:y = R1:R2

where x and y could be any two of a, b, and c.

No need to do anything fancy for the first problem. Just brute force all possibilities of upvotes, downvotes, and dupvotes and see how many of them add to the net points and satisfy the ratio. Don't be fooled! Although there are three unknowns, the solution is not \mathcal O(N^3). You only need to brute force a and b. Since U is given, c is already solved as U - a - b. Another thing to note is that the statement mentioned that all three values will be positive, so we need not worry about infinite ratios.

Real numbers are icky, and reducing the ratios is just too much work. To check if two ratios x:y and R1:R2 are equal, we can simply cross multiply and see if x \times R2 equals y \times R1.


Comments

There are no comments at the moment.