unbelievable's blog

Interesting task from UVa online judge
By unbelievable, history, 2 years ago, translation, In English

Hello everyone. Recently I found interesting problem from UVA online judge.

Short statement. There is an array $$$a$$$ of size $$$n$$$. You are given pairwise product of elements of $$$a$$$ ($$$n \cdot (n-1)/2$$$) products in total). You should find lexicographically minimal array $$$a$$$. $$$n < 200$$$.

Does anyone has ideas how to solve such problem?

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

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

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

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

Gaussian elimination ?

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

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/ )

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

    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?

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

      It's $$$\mathcal{O}(n^3 \log n)$$$ in the second case and most checks should fail early I believe.

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

      (if I look for a1 in all elements)

      Can you explain how you would do that?

      → Reply