We have an integer number N, and have to find an array A satisfying following constraints:
1- A = 1
2- A[i-1] <= A[i] <= 2*A[i-1] for every i > 1
3- sum of elements of A equals to pre given N
4- sum of squares of A[i] is maximum possible
It's a competitive programming task that got in mind but I couldn't solve it and I didn't find it on any platform to discuss
My solution is as following:
The final array should be sorted in non-descending order and the last element should be as max as possible and the one before last should be as max as possible and so on but I'm not sure and I am not able to prove it.
Could someone help please how to solve this problem or validate my solution or at least how to solve such problem, What topic of math one should use
Sorry for poor formatting but I don't know how to add math symbols.