ArenaRating

# solved.ac Grand Arena #2

## Solution 1

Implement as given in the problem using a loop. The time complexity is $\mathcal O(N)$.

### Code (C++)

.css-dc0a13{background-color:#0b131b;color:#dddfe0;padding:1em;border-radius:4px;font-size:95%;width:100%;overflow-x:auto;}.css-dc0a13.language-text{background-color:#f7f8f9;color:inherit;}.css-dc0a13 .hljs-meta,.css-dc0a13 .hljs-comment,.css-dc0a13 .hljs-quote{color:#8a8f95;font-style:italic;}.css-dc0a13 .hljs-meta [class^="hljs-"]{color:#8a8f95;font-weight:normal;background:unset;text-shadow:none;}.css-dc0a13 .hljs-meta [class^="hljs-"]:hover{font-weight:normal;background:unset;}.css-dc0a13 .hljs-keyword,.css-dc0a13 .hljs-type,.css-dc0a13 .hljs-attr,.css-dc0a13 .hljs-variable,.css-dc0a13 .hljs-template-variable,.css-dc0a13 .hljs-selector-class,.css-dc0a13 .hljs-selector-attr,.css-dc0a13 .hljs-selector-pseudo{color:#ff3381;text-shadow:0 2px 4px rgba(255,0,98,0.5);}.css-dc0a13 .hljs-number{color:#efae33;text-shadow:0 2px 4px rgba(236,154,0,0.5);}.css-dc0a13 .hljs-symbol,.css-dc0a13 .hljs-bullet,.css-dc0a13 .hljs-link,.css-dc0a13 .hljs-selector-id,.css-dc0a13 .hljs-title{color:#ffffff;text-shadow:0 2px 4px rgba(255,255,255,0.5);font-weight:bold;}.css-dc0a13 .hljs-literal{color:#33c3fc;text-shadow:0 2px 4px rgba(0,180,252,0.5);}.css-dc0a13 .hljs-string,.css-dc0a13 .hljs-regexp,.css-dc0a13 .hljs-addition,.css-dc0a13 .hljs-attribute,.css-dc0a13 .hljs-meta-string{color:#45d761;background-color:rgba(23,206,58,0.1);}.css-dc0a13 .hljs-string:hover,.css-dc0a13 .hljs-regexp:hover,.css-dc0a13 .hljs-addition:hover,.css-dc0a13 .hljs-attribute:hover,.css-dc0a13 .hljs-meta-string:hover{background-color:rgba(23,206,58,0.4);font-weight:bold;}.css-dc0a13 ::selection{background:#8a8f95;}#include <iostream>
using namespace std;

int main()
{
int N;
cin >> N;
int sum_1 = 0, sum_3 = 0;
for (int i = 1; i <= N; i++)
{
sum_1 += i;
sum_3 += i * i * i;
}
cout << sum_1 << endl;
cout << sum_1 * sum_1 << endl;
cout << sum_3 << endl;
}


### Code (Python)

def main():
N = int(input())
print(sum(range(1, N+1)))
print(sum(range(1, N+1))**2)
print(sum(i**3 for i in range(1, N+1)))

if __name__ == '__main__':
main()


## Solution 2

$1+2+\cdots+N = \frac{N(N+1)}{2}$ and $1^3 + 2^3 + \cdots + N^3 = (1+2+\cdots+N)^2 = {\left(\frac{N(N+1)}{2}\right)}^2$ holds. The time complexity is $\mathcal O (1)$.

### Code (C++)

#include <iostream>
using namespace std;

int main()
{
int N;
cin >> N;
cout << N * (N + 1) / 2 << endl;
cout << (N * (N + 1) / 2) * (N * (N + 1) / 2) << endl;
cout << (N * (N + 1) / 2) * (N * (N + 1) / 2) << endl;
}


### Code (Python)

def main():
N = int(input())
print(N * (N + 1) // 2)
print((N * (N + 1) // 2) ** 2)
print((N * (N + 1) // 2) ** 2)

if __name__ == '__main__':
main()


### 증명

To prove $1+2+\cdots+N = \frac{N(N+1)}{2}$, let's calculate $2 \times (1 + 2+ \cdots + N)$.

When adding two sequences of $(1+2+\cdots+N)$, keep one sequence as it is, and reverse the other before adding. Then, upon inspecting each sum, combining $1$ with $N$ yields $N+1$, combining $2$ with $N−1$ yields $N+1$, and so on, until combining $N$ with $1$ also gives $N+1$. Hence, the total is equivalent to adding $N+1$ a total of $N$ times, which is $N(N+1)$.

Mathematically:

\begin{align*} & \ 2 \times (1 + 2 + \cdots + N) \\ = & \ (1 + 2 + \cdots + N) + (N + (N-1) + \cdots + 1) \\ = & \ ((1+N) + (2+(N-1)) + \cdots + (N+1)) \\ = & \ ((N+1) + (N+1) + \cdots+ (N+1)) \\ = & \ N(N+1) \end{align*}

Let's now prove the slightly more challenging relationship $(1+2+\cdots+N)^2 = 1^3+2^3+\cdots+N^3$. We will demonstrate that both expressions have the same value for $N=1$, and the difference between the values of the expressions for $N=i-1$ and $N=i$ are the same. This will prove the two expressions are equivalent. For $N = 1$, both expressions equal 1. Let's now look at the difference between the two expressions:

Utilizing the identity $a^2 - b^2 = (a-b)(a+b)$:

\begin{align*} & \ (1+2+\cdots+i)^2 - (1+2+\cdots+(i-1)^2) \\ = & \ \left(\frac{i(i+1)}{2}\right)^2 - \left(\frac{i(i-1)}{2}\right)^2 \\ = & \ \left(\frac{i(i+1)}{2} - \frac{i(i-1)}{2}\right) \times \left(\frac{i(i+1)}{2} + \frac{i(i-1)}{2}\right) \\ = & \ \left(\frac{i((i+1)-(i-1))}{2}\right) \times \left(\frac{i((i+1)+(i-1))}{2}\right) \\ = & \ \left(\frac{i \times 2}{2} \right) \times \left(\frac{i \times 2i}{2} \right) \\ = & \ i \times i^2 = i^3 \end{align*}

The difference between $1^3 + 2^3 + \cdots + (i-1)^3$ and $1^3 + 2^3 + \cdots + i^3$ is also $i^3$, so the two expressions must indeed be equivalent.

There's also a visual method to prove this.