Very difficult problem

Revision en2, by HusseinFarhat, 2023-10-21 16:12:47

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

Tags math, summation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English HusseinFarhat 2023-10-21 16:12:47 165 Tiny change: 's: $\fraq{}{\Pi_{j =' -> 's: $\fraq{1}{\Pi_{j ='
en1 English HusseinFarhat 2023-10-21 11:11:05 1100 Initial revision (published)