Блог пользователя cbdb

Автор cbdb, история, 3 дня назад, По-английски

Hi everyone,

Today's codeforces round involved finding the number of occurrences of a certain AP in a range, for example 1,3,5,7... in a range of 0 to 99.

A lot of users have solved the problem with:

if((n-1)<c) return 0;

 return (n-1-c)/b + 1;

Although such one liners seem simple, basic maths, they are tricky and error prone to come up with during contests, with even some higher rated coders making mistakes in the same. How can I improve this aspect of my maths?

Thanks for your time.

PS: I still don't know why this formula works. Any further problems requiring similar ideas would be appreciated.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by cbdb (previous revision, new revision, compare).

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

It is not as hard as you think.
-The array is constructed using this formula b * i + c.
-An element of the array will be kept in the permutation if is in the range [0, n-1]
so for an element to be valid it should meet this condition :
b * i + c <= n-1.
so 0 <= i <= (n-1-c)/b, so valid numbers = (n-1-c)/b — 0 + 1.
-the remaining we need to add to permuatation will be n — valid ones, which is the answer to the problem

»
3 дня назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I'm not necessarily one to talk about this as I struggle with this myself, but I do suggest solving the 800-1000 rated problems in Codeforces as most of them have these types of problems, especially when tagged with "math."

For this particular problem, the algebra didn't trick me up as much as the casework for $$$b = 0$$$ is, but that's for another time. Also, I guess its good to make sure that you address possible floating point errors to avoid mistakes like this in the future.

Here's my code for reference (I used Python for big floats with relatively good enough precision)

startInd = ((n - c) / b) + 1
startInd = int(math.ceil(startInd))
startInd = max(startInd, 1)
»
3 дня назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i used bin search, i dont trust on my math skills