The binary search is not really needed for this problem.
Here's a solution without the binary search part and with the worst run-time 0.08 sec:
https://www.codechef.com/viewsolution/21706372
As suggested in the Editorial above, let's analyze all the possible splits of the sequence of numbers $K^{A_1}$, $K^{A_2}$, $K^{A_3}$, ... , $K^{A_{N-1}}$, $K^{A_N}$. There are $N-1$ possible splits. We would like to find a split where the difference between the sums as an absolute value is minimal. For the *i-th* split the difference is $\sum^N_{n=i+1}K^{A_n} - \sum^i_{n=1}K^{A_n}$ which is equivalent to $\sum^N_{n=1}K^{A_n} - \sum^i_{n=1}2K^{A_n}$. We can start by calculating the total sum $\sum^N_{n=1}K^{A_n}$, and then for every $n$ between $1$ and $N-1$ subtract $2K^{A_n}$ and check whether the result is at or below zero. Once the result reaches zero or below, we are done, since the optimal split is either the current or the previous one.
Let's imagine for a moment that the given array of numbers *A[i]* are not the powers of *K* but just regular numbers. In this case the proposed solution looks like this:
<pre><code>int solve(const vector<int>& A)
{
const int N = A.size();
int agg = 0;
for(int i=0; i<N; ++i) {
agg += A[i];
}
for(int i=0; i < N-1; ++i) {
agg -= A[i];
if (agg ≤ 0) return i;
agg -= A[i];
if (agg ≤ 0) return i + 1;
}
return N-1;
}
</code></pre>
We subtract ~~*A[i]* ~~*2A[i]* in two steps in order to determine whether to choose the current or the previous split as the closest to zero difference.
The proposed solution has *N* additions, *2N* subtractions, and *2N* comparisons with zero. It becomes only a matter of finding an efficient structure to represent a number with the following operations:
- Add a power of ~~*k*
~~*K*
- Subtract a power of ~~*k*
~~*K*
- Compare it with zero
That's what the *Number* structure in my solution does.