rek's blog

Strange problem
By rek, history, 8 years ago, translation, In English

Hello, Codeforces!

Recently I stumbled upon a certain problem. Given n pairwise distinct positive integers (let's say all of them are less than or equal to 109), you're ought to find such smallest possible k that these numbers modulo k will still be pairwise distinct.

I'll be thankful if someone suggests a non-naive solution (i.e. w/o explicitly calculating all the pairwise differences) or provides some ideas to start with.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by rek (original revision, translated revision, compare)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For each pair find a positive difference. Find all divisors of that difference — add them to global hash-table. Iterate numbers from 1 to infinity and check presence in hash-table. If it's not in hash-table, that's your k.

If you have pair 1 & 7, difference is 6, divisors are 1,2,3,6 (added to hash-table) — so the smallest k is 4. Keep adding divisors for other pairs and then find smallest k.

Complexity O(n * sqrt(m)), where n — number of pairs and m is 10^9 in your case.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your answer! Considering we have n numbers, we would get complexity, which is not much better than a naive solution, so I'm still looking for a better way to do this (if there's any).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah, I see n distinct numbers, not n pairs that got distinct numbers.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a constraint on k? Large k will always work

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, thank you for this message, I didn't point before that k must be as small as possible. My fault.

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can you please post the link?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Well, to tell the truth, there is no such competitive programming problem anywhere, my friend and I came up with the idea of it some days ago, and we have been looking for the solution for a few days, but we couldn't find anything similar either in archives or in Google, so I can't.

    → Reply