unbelievable's blog

Interesting task from UVa online judge
By unbelievable, history, 3 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

»
3 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gaussian elimination ?

→ Reply
»
3 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

Unable to parse markup [type=CF_MATHJAX]

pair and deduce $$$a_1, a_2$$$ using it ( https://cses.fi/problemset/task/2414/ )
→ Reply
  • »
    »
    3 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
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      It's

      Unable to parse markup [type=CF_MATHJAX]

      in the second case and most checks should fail early I believe.
      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can this https://cses.fi/problemset/task/2414/ also be done in O(n^3 log n)?

        I was able to solve it in O(n^4 log n)

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

          Your solutions probably works in

          Unable to parse markup [type=CF_MATHJAX]

          .

          Unable to parse markup [type=CF_MATHJAX]

          must be in first $$$n$$$ terms.
          → Reply
    • »
      »
      »
      3 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