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](https://en.wikipedia.org/wiki/Newton's_law_of_universal_gravitation#Vector_form). 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
↵
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](https://en.wikipedia.org/wiki/Newton's_law_of_universal_gravitation#Vector_form). 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
