PROBLEM LINK:
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;
}
}