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 \lt 200$$$.
Does anyone has ideas how to solve such problem?
Auto comment: topic has been updated by unbelievable (previous revision, new revision, compare).
Gaussian elimination ?
Can you elaborate please?
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/ )
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?
It's $$$\mathcal{O}(n^3 \log n)$$$ in the second case and most checks should fail early I believe.
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)
Your solutions probably works in $$$\mathcal{O}(n^3 \log n)$$$. $$$a_2 + a_3$$$ must be in first $$$n$$$ terms.
Yes, I tried it and it worked. Thanks!!
Can you explain how you would do that?