HusseinFarhat's blog

By HusseinFarhat, history, 14 months ago, In English

I came up with 2 problems, an "easy" version and a hard version

The easier version is:

If you have an array A composed of n integers, compute the array B under O(n^2), where $$$B_{i} = \displaystyle\sum_{j=1 \atop j \neq i}^{n} \frac{1}{(A_{i} - A_{j})^2} (where j \neq i)$$$. It seems like this problem should be solved by getting a common denominator, but the rest gets very confusing. It becomes: $$$\frac{\sum_{k = 1 \atop k \neq i}^{n} \Pi_{j = 1 \atop j \neq k j \neq i}^{n} (A_{i} - A_{j})^2}{\prod_{j = 1 \atop j \neq i}^{n} (A_{i} - A_{j})^2}$$$

The harder (or maybe even impossible) version is:

If you have an array A composed of n 3d vectors, and an array M composed of n real numbers, compute the array F of n 3d vectors, where each element is the total newtonian gravity force. $$$A_{i}$$$ is the current position of the particle i, and $$$M_{i}$$$ is the mass of the particle i. You can brute force this by just iterating through all possible pairs, then calculating this. Is it possible to do it under O(n^2)?

Note that these two problems, or the second one, may be impossible to solve. If that's the case, there might be a way to approximate it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the second problem, this is a stackoverflow page which asks the same questions, the solutions don't look optimal though, they're mostly estimation. So it seems like it's impossible to get an exact result lower than O(n^2) in the second problem. But, for the first problem, there's still hope

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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