ARRYRR - Editorial

PROBLEM LINK:

Code Venture Contest

Author and Editorialist: Aadarsh A

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Arrays, Math, Observation

PROBLEM:

Given an number N, construct an array such that sum of cubes of the array elements is equal to difference of any 2 perfect squares (p^2 and q^2). Also, the sum of the array should be minimum, and the sum of square roots of the perfect squares is also minimum.

QUICK EXPLANATION:

The minimum array that can be constructed is [2, 3, 4 .... N+1].
The sum of the square roots is minimum for the array when p and q are \dfrac{(n+1)(n+2)}{2} and 1.

EXPLANATION:

This problem revolves around the following identity:
n^3 = \left(\dfrac{n(n+1)}{2}\right)^2 - \left(\dfrac{n(n-1)}{2}\right)^2

To satisfy the condition imposed by the question, we can observe that any array with consecutive elements will satisfy the condition.

Example:
For n=3, the array [3,4,5] will satisfy the condition, with 225 and 9 being the perfect squares.

3^3 = 6^2 - 3^2
4^3 = 10^2 - 6^2
5^3 = 15^2 - 10^2
\implies 3^3 + 4^3 + 5^3 = 15^2 - 3^2

So, to obtain minimum possible sum of elements, we need to choose an array of consecutive elements starting from 2 till N-1.

2^3 = 3^2 - 1^2
3^3 = 6^2 - 3^2
4^3 = 10^2 - 6^2
\implies 2^3 + 3^3 + 4^3 = 10^2 - 1^2

It can be also proved that \dfrac{(n+1)(n+2)}{2} and 1 give the minimum possible sum of square roots.

Proof

Let the sum of cubes obtained from the constructed array be S.
Let the perfect sqaures be p^2 and q^2.
p^2 - q^2 = S
p = \sqrt{S-q^2}
p + q = \sqrt{S-q^2} + q
Since, \sqrt{S-q^2} is an increasing function on q \geq 1.
So, minimum value of q is obtained only at 1.
Hence, the value of p = \sqrt{S-1} = \dfrac{(n+1)(n+2)}{2}

SOLUTIONS:

Setter's Solution (C++)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define vi vector<int>
#define pb push_back
#define MOD 1000000007

using namespace std;
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int sum_perfect_sq = ((n+1)*(n+2)/2 + 1)%MOD;
        cout << sum_perfect_sq << endl;
        for (int i=2; i<=n+1; i++) {
            cout << i << " ";
        }
        cout << endl;
    }
}