PROBLEM LINK:Author: Rahim Mammadi DIFFICULTY:EasyMedium PREREQUISITES:Binary Search PROBLEM:You are given a sequence of $N$ powers of an integer $K$.Let's denote the $i_{th}$ of these powers by $K^{A_i}$. You should partition this sequence into two nonempty contiguous subsequences, such that the product of (the sum of elements of the left subsequence) and (the sum of elements of the right subsequence) should be maximum possible. Find the smallest position at which you should split this sequence in such a way that this product is maximized. $2 \leq N \leq 10^5$ EXPLANATION:Let's suppose we have a number N and we want to split it into a,b such that a+b=N and a × b is maximum. The cut point would be exactly N/2. This can be proved by solving the quadratic equation N*(Nx) or deriving the function. Here we have the same problem with only one issue (the points where we can split the number are not concrete). We can only split it into $N$ ways as in the problem statement. So now we want to split it such that the difference between the two parts is minimum possible. So we need to find 1 point: Maximum possible i such that Sum(1,i) < Sum(i+1,n) It can be found with a binary search. How exactly? While examining a breakpoint M during our binary search, let's write a number in the Kth numeral system which is equal to the sum of the first M numbers. Also, we write the number which is equal to the sum of the last nM numbers. We can compare them lexicographically digit by digit. Now after we found our point i. We need to check if we can split the sequence to 2 equal parts. So we check if Sum(1,i+1)=Sum(i+2,n). In such a case, the answer is i+1. Now, we have 2 cases we need to pick the best among. We can split it at the point i or at the point i+1. The first case yields a positive difference between the right and the left part, and the second yields a negative difference. We need to pick the one with minimum absolute value. If Sum(i+1,n) <= Sum(1,i+1) the answer is i otherwise it's i+1 Complexity: $O(N log N)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 25 Nov '18, 02:30

The binary search is not really needed for this problem. Here's a solution without the binary search part and with the worst runtime 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_{N1}}$, $K^{A_N}$. There are $N1$ possible splits. We would like to find a split where the difference between the sums as an absolute value is minimal. For the ith 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 $N1$ 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:
We subtract 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:
That's what the Number structure in my solution does. answered 26 Nov '18, 01:40

since the editorial has no links to the solution so I found a very simple and easy to understand solution as per editorial approach here by @swakansh. Hope it helps. answered 26 Nov '18, 14:14
Thanks. Because of this only I understood the solution.
(27 Nov '18, 00:31)
Can someone explain to me why mid element is added in both left and right array in this solution here in the same solution? I don't know how but because of that we can skip checking i+1 position. Someone please explain! @swakansh @vipin1407
(27 Nov '18, 02:05)

How to write a number in the Kth numeral form? And support addition and subtraction on it? answered 26 Nov '18, 14:09

Guys, is it possible with python3.6 or PyPy3 do this problem for 100 points? I have done for 30 points. Please help me to optimize my solution. Here is solution https://www.codechef.com/viewsolution/21717574 answered 29 Nov '18, 21:23
Definitely possible. See https://www.codechef.com/viewsolution/21694533 The solution is 100 points but with Python2. The worst runtime is 1.01 sec.
(29 Nov '18, 23:28)

whats the problem with this solution? can anyone tell me what is the flaw in this logic?? what i have done is that i am storing the position of each point in the array and also the product of sums of elements before it and after it and after that i am just checking the maximum product in the vector. include<bits stdc++.h="">using namespace std; int main() {
} i am first timer so please help answered 17 Dec '18, 23:20

Help me find the mistake. https://www.codechef.com/viewsolution/22085874 answered 25 Dec '18, 22:22

Time Complexity ??
@aryanc403 fixed