cbdb's blog

How to get better at "BASIC" Math? (Ft. Round 986 B)
By cbdb, history, 2 days ago, In English

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.

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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)
→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply