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

Автор Hand1e, история, 9 лет назад, По-английски

I've been trying to solve this problem. I already read the editorial but it was too short for me to understand. Can anyone please explain how to solve this problem?

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

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Do binary search on X where X is the number of values in the matrix less than X. Thus initial low=1, high=n*m and then for every mid=(low+high)/2 calculate the number of values less than mid in the matrix and shift the low and high pointers accordingly.

To calculate the number of values less than mid in the matrix :-- num=0, then for each row i 1 to n: num+=min(m, (mid-1)/i)

I hope this gives you enough clarification of what to do! :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Have you tried reading this?

»
9 лет назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Hi!

I solved this problem quite recently. My algorithm matched the one in the editorial, here's my explanation.

First of all, brute force can't work, that would need O(n·m) time. So, that's out of question.

But we do know one thing, that the number of multiples of a number n strictly less than a value x are always equal to . It's not too tough to see the correctness of this, and can be proven using elementary math.

Using this observation, we can run a binary search for such number x such that the number of multiples of numbers 1 to n are equal to k. But because we only consider the first m multiples of these numbers(as the table doesn't have numbers greater than this), the number of values less than a number x in the multiplication table ultimately amount to

The above value can be calculated in O(n) time. The work left is implementing a binary search that searches the interval 1, 2, ... , 25·1010 as the maximum value of answer can be n·m. The final time complexity of solution amounts to O(n·log(n·m)).

I hope my explanation makes sense. Please point out any errors. My solution can be found at 13549897.