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

A power of two week
Автор Petr, история, 16 месяцев назад, По-английски

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

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

»
16 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Or even

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

      to handle small negative fractions as well

      → Ответить
      • »
        »
        »
        »
        15 месяцев назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        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 месяцев назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

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

          → Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

69 minutes lololol

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

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.

→ Ответить