0
$\begingroup$

We have an integer number N, and have to find an array A satisfying following constraints:

1- A[0] = 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.

$\endgroup$
2
  • $\begingroup$ Hi! I assume we know the size of the array? $\endgroup$
    – cjferes
    May 1 at 21:00
  • $\begingroup$ Hi! the size of the array isn't known, and no conditions on it, Whatever the array that match the 4 condition it's ok whatever its size, but anyway I 'think' the optimal array has size of log2(N) rounded up to natural number $\endgroup$
    – ahmad alghadban
    May 1 at 21:18

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .