Petr's blog

By Petr, history, 15 months ago, In English
  • Vote: I like it
  • +109
  • Vote: I do not like it

»
15 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Now, some questions to the reader :) Do you routinely try to convert the sample answers from the "modulo prime" form to the fraction form? Did it ever help you solve a problem? Do you have some tricks on how to do this more reliably? If the problemsetters are reading this, did you consider this trick when choosing the samples for this problem?

I don't usually do this for sample answers (but quite often, I realize that I should have spent more time analyzing samples before thinking about the solution, so I am not a good example).

But my modulo struct, when printing value to debug, tries to represent it as a rational number with a small numerator/denominator. This helps debugging quite a lot and I really recommend everyone adding similar stuff to their template.

  • »
    »
    15 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    Makes sense :) One thing I discovered while writing my blogpost is that instead of doing

    for num in 1..MAX {
        if Self(num as i32, PhantomData) / Self(denum as i32, PhantomData) == *self {
    

    you can do (sorry, can't write Rust)

    num = denum * (*self)
    if num.value() <= MAX {
    

    Which might allow you to raise MAX to around sqrt(modulo), where the collisions start.

    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Or even

      num = denum * (*self)
      if num.value() <= MAX {
      } else if num.value() >= M::val() - MAX {
      }
      

      to handle small negative fractions as well

      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Nice!

        Though I am not sure how often it is helpful to know that your number is rational with a denominator of around several thousand (except for cases like in your blog, when it is a power of two or some other reasonable number).

        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          I agree, but still multiplication using a for loop and division looks weird ;)

»
15 months ago, # |
  Vote: I like it -16 Vote: I do not like it

69 minutes lololol

»
15 months ago, # |
  Vote: I like it +23 Vote: I do not like it

If the problemsetters are reading this, did you consider this trick when choosing the samples for this problem?

I didn't. I've tried to use this trick a few times in the past, but it never worked, so I thought it was useless and removed it from my mind. Actually, I didn't even remember about this trick when checking the samples.