||Ok, now before the next operation of rounding, lets talk a bit more about what the green zone, red zone theory means about the philosophy of using floating point numbers. Lets say do a calculation and mathematically the end result should be exactly 1. That's all fine and dandy, but in the real world we'll end up with a number with a green zone and a red zone. Lets assume that the green zone has 7 digits. So the question is, what actual value can the stored data have? Well, the answer to the question is easy, because we can just put the highest and lowest values for the red zone:
1.0000000999 to 0.9999999000Namely, the stored number can never be more that 1e-7 away from the value of 1. In fact this value, 1e-7 is quite special. Special enough to give it a name, epsilon (the name comes from mathematicians practice of calling a small positive number by the same greek letter). Also note that the only thing special about the actual number "1e-7" is that in this case the green zone happens to be 7 digits, if your green zone has a different size, then your epsilon should too (TopCoder usually wants you to have an epsilon of 1e-9). Why is the epsilon important? Because we know from the green zone/red zone arguments the validity of this important fact:
true value - epsilon < stored value < true value + epsilon
This is just a restatement of what the possible stored values are. But really if you think about it, that question isn't the one we usually want to ask. In fact we know the stored value; just check the contents of the variable you're using. The question is, what is the true value? If you fiddle around with the previous inequalities and try to solve them for the true value, then you'll end up with this similar fact:
stored value value - epsilon < true value < stored value + epsilon
Now there are two notable things about this equation. The first is that the true value is never epsilon away from the stored value. This should be obvious because the stored value should be less than a small amount away from the true value. But the second thing is more important. If we know the stored value then we know a range of values that the true value lies in. We don't know the true value exactly, but we have the set of possible values it could be. This is the whole reason for using epsilon in floating point comparisions, because if the ranges of two variables overlap, then the two values could be equal.
Ok, now that that's through, back to the point of rounding. Let's say we want to round the variable x to the nearest integer less than or equal to x. For a simple first look, assume that x contains the exact value (before you realized that floating point computations were exact you assumed this exact same thing, so think of this as your code before learning the magic that is floating point). Well, you say, this is a simple task. This is just truncation, which is what casting to an integer does. (int) x is the desired value! Well, this is not quite so. Why? look above. If the true value of x is exactly 1 then x could be as low as 0.9999999000. When this number gets truncated it's going to go straight down to 0, be dead wrong, and get you that exact score in the SRM. The cure is plain and simple, just add epsilon to x before you do the cast. This way if x is anywhere near an actual integer(and so we must assume that the true value of x is that integer), then it will be gauranteed to get rounded to the right place. On the other hand if x is not close to any integer, then adding epsilon won't change the result.