### maxifier's blog

By maxifier, history, 4 months ago,

I was solving this problem. While solving this problem i encountered a sub-problem.

We have an array of n length and we want to divide it into three parts such that after dividing the array sum of individual arrays should be as close to the power of 2 greater than or equal to the sum as possible.

More formally, let say sum1, sum2, sum3 are the sums of subarrays. Our answer is minimum possible value of (p1 — sum1) + (p2 — sum2) + (p3 — sum3). Here, p1, p2, p3 are the powers of two.

For Example : let say our array is [4, 1, 1, 2, 3, 1]

-> If we divide this array as [4, 1], [1, 2], [3, 1] then our answer is (8 — 5) + (4 — 3) + (4 — 4) = 0.

-> If we divide this array as [4], [1, 1, 2], [3, 1] the our answer is (4 — 4) + (4 — 4) + (4 — 4) = 0 which is optimal in this case.

Constraints: 1<= n <= 1e5, 1 <= ai <=n

I would be grateful if you help me to solve this Problem.

• +8

 » 4 months ago, # |   0 Auto comment: topic has been updated by maxifier (previous revision, new revision, compare).
 » 4 months ago, # |   +10 isn't that the task itself?
•  » » 4 months ago, # ^ |   0 Indeed this is a task which i encountered while solving that problem. If you know how to solve this or any resource which could help me solve the problem please share.
•  » » » 4 months ago, # ^ |   +6 There is an editorial: https://codeforces.com/blog/entry/99136 But I think this approach is easier: Let P[i] = sum on prefix of length i Just look at every size of every part This will be O(log(n)^3) because size of every part is power of 2 Then you can use binary search on P to find bounds of parts Total complexity is O(log(n)^4)https://codeforces.com/contest/1626/submission/143140319
•  » » » » 4 months ago, # ^ |   0 Thanks for the approach.
 » 4 months ago, # | ← Rev. 2 →   +6 your problem can be solved like this.let call nxt[x] : the next power of 2 greater than or equal x.if we split the array into three blocks lets say sum of blocks are x,y,z.the task is to minimize nxt[x]+nxt[y]+nxt[z]-x-y-z.so notice that if we fix x and increased y by value a without change nxt[y] then:it will be nxt[x]+nxt[y]+nxt[z]-x-(y+a)-(z-a)as you can see we said that nxt[y] didn't change so it will not make answer worse but after decreasing z it's possible for nxt[z] to decreaseso lets try to fix x as any point (n point total) then for each power of 2 (call it p)(there logn different power of 2) binary search for a last point where the sum of second block (called y) will be smaller than or equal p (you can pre process the array by a prefix sum so you can binary search) so the total complexity is O(n*log^2(n))
•  » » 4 months ago, # ^ |   +6 another optimization to work only in n*log(n) is to use different pointer for each power of 2 so logn pointer total, then while increasing x (the first block) move the pointers forward so each pointer will change at most n times so n*log(n) for pointers walk and also n*log(n) for trying each power of 2 so the total is ( 2*n*log(n) )
•  » » » 4 months ago, # ^ |   +3 Got it. Thanks