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

Интересная задача с UVA online judge
Автор unbelievable, история, 2 года назад, По-русски

Всем привет. Недавно я натолкнулся на задачу с UVA online judge.

Короткое условие: существует массив $$$a$$$ размера $$$n$$$. Вам заданы все попарные произведения элементов $$$a$$$ (всего $$$n \cdot (n-1)/2$$$) произведения). Вам нужно найти лексикографаически минимальный массив $$$a$$$. $$$n < 200$$$.

У кого-то есть идеи, как ее решить?

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

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

Auto comment: topic has been updated by unbelievable (previous revision, new revision, compare).

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

Gaussian elimination ?

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

If you know $$$a_1$$$ and $$$a_2$$$ you can restore the whole sequence. You can either try all divisor pairs of the smallest product or try to find $$$a_2 \cdot a_3$$$ pair and deduce $$$a_1, a_2$$$ using it ( https://cses.fi/problemset/task/2414/ )

→ Ответить
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks. I got the idea. I guess I could implement it in

    $$$O(divs(a_1) \ n ^2 \log n)$$$ (if I look for $$$a_1$$$ in divisors of first element)

    or $$$O(n^4 \log n)$$$ (if I look for $$$a_1$$$ in all elements)

    but both solutions does not seams good (There are 25 cases per test on UVa).

    Am i missing something?

    → Ответить