Editorial for THICC '17 P2 - Molly and Product - Olympiads Online Judge

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)$ $O (N^{2})$ pairs and find their sum.

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

For the remaining $70\%$ $70 %$ of points, we have to do some basic math. Let $\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$ $Σ^{2} = 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)$ $O (N)$

Comments

There are no comments at the moment.