Editorial for THICC '17 P2 - Molly and Product

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

For $30\%$ ~30\%~ of points, it is possible to loop all $\mathcal O(N^2)$ ~\mathcal O(N^2)~ pairs and find their sum.

Time Complexity: $\mathcal O(N^2)$ ~\mathcal O(N^2)~

For the remaining $70\%$ ~70\%~ of points, we have to do some basic math. Let $\Sigma$ ~\Sigma~ be the sum of all $N$ ~N~ elements. Notice that

$\displaystyle \Sigma^2 = \text{our desired result} + A_0^2 + A_1^2 + \dots + A_{N-1}^2$

Thus we can find the square of the sum of all elements, and subtract the sum of the squares of all elements.

Time Complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

There are no comments at the moment.