# MXM Editorial

#PROBLEM LINK:
[Practice][1]
[Contest][2]
**Author:** [Hasan Jaddouh][3]
**Primary Tester:** [Amir Reza PoorAkhavan][4]
**Editorialist:** [Hussain Kara Fallah][5]
#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 in $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 ~~2 points:
~~1 point:
Maximum possible **i** such that **Sum(1,i) < Sum(i+1,n)**
~~Minimum possible **j** such that **Sum(1,j) >= Sum(j+1,n)**
Each one ~~It can be found with a binary search. ~~Let's take the first case.
~~How ~~to find the maximum possible **i** ?
~~exactly?
While examining a ~~break point ~~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 ~~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.
~~Only one part is left, ~~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 case the answer is **i**.
Now, we have ~~now ~~2 ~~choices and ~~cases we need to pick the ~~one with the least difference.
~~best among. We can split it at the point **i** or at the point **i+1**. The first case ~~is:
**Sum(1,j) = Sum(j+1,n)** thus the answer is **j**.
otherwise we compare (look at definition of **i,j** in the part above):
if ~~yields a positive difference between the right and the left part, and the second yields a negative part. We need to pick the one with minimum absolute value.
If **Sum(i+1,n) ~~< Sum(1,j)** ~~<= Sum(1,i+1)** the answer is **i** otherwise ~~the answer is **j**.
~~it's **i+1** .
#AUTHOR'S AND TESTER'S SOLUTIONS:
**AUTHOR's solution**: [Here] [7]
**TESTER's solution**: [Here] [8]
[1]: https://www.codechef.com/problems/MXM
[2]: https://www.codechef.com/LTIME66/problems/MXM
[3]: https://www.codechef.com/users/kingofnumbers
[4]: https://www.codechef.com/users/arpa
[5]: https://www.codechef.com/users/deadwing97
[6]: https://www.geeksforgeeks.org/sieve-of-eratosthenes/
[7]: http://www.codechef.com/download/Solutions/COOK83/Setter/ADACRA.cpp
[8]: http://www.codechef.com/download/Solutions/COOK83/Tester1/ADACRA.cpp