### PROBLEM LINK:

**Author:** Rahim Mammadi

**Primary Tester:** Amir Reza PoorAkhavan

**Editorialist:** Hussain Kara Fallah

### DIFFICULTY:

Easy-Medium

### 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 non-empty 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(N-x)** 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 **K-th** 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 **n-M** 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)