I became bit lost between "C is a constant that determines the probability of success" and then they set C between 4 and 8. Probability should be between 0 and 1, how it relates to C?

It's the epsilon^-2 term that actually talks about success, but that is tightly linked with the C term. If you want to decrease epsilon, C goes up.