Petr's blog

A power of two week
By Petr, history, 16 months ago, In English

https://petr-mitrichev.blogspot.com/2023/08/a-power-of-two-week.html

  • 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.

→ Reply
  • »
    »
    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.

    → Reply
    • »
      »
      »
      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

      → Reply
      • »
        »
        »
        »
        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).

        → Reply
        • »
          »
          »
          »
          »
          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 ;)

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

69 minutes lololol

→ Reply
»
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.

→ Reply