Answers to: MXM Editorialhttps://discuss.codechef.com/questions/141070/mxm-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/MXM">Practice</a> <br>
<a href="https://www.codechef.com/LTIME66/problems/MXM">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Rahim Mammadi</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/arpa">Amir Reza PoorAkhavan</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p>Binary Search</p>
<h1>PROBLEM:</h1>
<p>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.</p>
<p>$2 \leq N \leq 10^5$</p>
<h1>EXPLANATION:</h1>
<p>Let's suppose we have a number <strong>N</strong> and we want to split it into <strong>a,b</strong> such that <strong>a+b=N</strong> and <strong>a × b</strong> is maximum. The cut point would be exactly <strong>N/2</strong>. This can be proved by solving the quadratic equation <strong>N*(N-x)</strong> or deriving the function.</p>
<p>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.</p>
<p>So we need to find 1 point:</p>
<p>Maximum possible <strong>i</strong> such that <strong>Sum(1,i) < Sum(i+1,n)</strong></p>
<p>It can be found with a binary search. How exactly?</p>
<p>While examining a breakpoint <strong>M</strong> during our binary search, let's write a number in the <strong>K-th</strong> numeral system which is equal to the sum of the first <strong>M</strong> numbers. Also, we write the number which is equal to the sum of the last <strong>n-M</strong> numbers. We can compare them lexicographically digit by digit.</p>
<p>Now after we found our point <strong>i</strong>. We need to check if we can split the sequence to 2 equal parts. So we check if <strong>Sum(1,i+1)=Sum(i+2,n)</strong>. In such a case, the answer is <strong>i+1</strong>.</p>
<p>Now, we have 2 cases we need to pick the best among. We can split it at the point <strong>i</strong> or at the point <strong>i+1</strong>. 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.</p>
<p>If <strong>Sum(i+1,n) <= Sum(1,i+1)</strong> the answer is <strong>i</strong> otherwise it's <strong>i+1</strong></p>
<p>Complexity: $O(N log N)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/LTIME66/setter/MXM.cpp"><strong>AUTHOR's solution</strong></a></p>
<p><a href="http://www.codechef.com/download/Solutions/LTIME66/tester/MXM.cpp"><strong>TESTER's solution</strong></a></p>
<p><a href="http://www.codechef.com/download/Solutions/LTIME66/editorialist/MXM.cpp"><strong>Editorialist's solution</strong></a></p>enTue, 25 Dec 2018 22:22:22 +0530Answer by smeagolhttps://discuss.codechef.com/questions/141070/mxm-editorial/142887<p>Help me find the mistake. <a href="https://www.codechef.com/viewsolution/22085874">https://www.codechef.com/viewsolution/22085874</a></p>smeagolTue, 25 Dec 2018 22:22:22 +0530https://discuss.codechef.com/questions/141070/mxm-editorial/142887Answer by chinmaysama_99https://discuss.codechef.com/questions/141070/mxm-editorial/142219<p>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.</p>
<h1>include<bits stdc++.h=""></h1>
<p>using namespace std;</p>
<p>int main()
{</p>
<pre><code>int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
int arr[n];
for (int i=0;i<n;i++)
{
cin>>arr[i];
}
vector<pair<int,int> > v;
int sum=0,s=0;
for (int i=0;i<n;i++)
{
s+=arr[i];
}
for(int i=0;i<n;i++)
{
sum+=arr[i];
v.push_back(make_pair(i+1,sum*(s-sum)));
}
int l=v[0].second,g;
for (int i=0;i<n;i++)
{
if(v[i].second>l)
g=v[i].first;
}
cout<<g<<endl;
}
</code></pre>
<p>}
i am first timer so please help</p>chinmaysama_99Mon, 17 Dec 2018 23:20:26 +0530https://discuss.codechef.com/questions/141070/mxm-editorial/142219Answer by danyshman07https://discuss.codechef.com/questions/141070/mxm-editorial/141312<p>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 <a href="https://www.codechef.com/viewsolution/21717574">https://www.codechef.com/viewsolution/21717574</a></p>danyshman07Thu, 29 Nov 2018 21:23:20 +0530https://discuss.codechef.com/questions/141070/mxm-editorial/141312Answer by vipin1407https://discuss.codechef.com/questions/141070/mxm-editorial/141157<p>since the editorial has no links to the solution so I found a very simple and easy to understand solution as per editorial approach <a href="https://www.codechef.com/viewsolution/21702150">here</a> by <a href="/users/83644/swakansh">@swakansh</a>. Hope it helps.</p>vipin1407Mon, 26 Nov 2018 14:14:01 +0530https://discuss.codechef.com/questions/141070/mxm-editorial/141157Answer by rahul_ghttps://discuss.codechef.com/questions/141070/mxm-editorial/141156<p>How to write a number in the Kth numeral form? And support addition and subtraction on it?</p>rahul_gMon, 26 Nov 2018 14:09:36 +0530https://discuss.codechef.com/questions/141070/mxm-editorial/141156Answer by oleg_bhttps://discuss.codechef.com/questions/141070/mxm-editorial/141145<p>The binary search is not really needed for this problem.</p>
<p>Here's a solution without the binary search part and with the worst run-time 0.08 sec:
<a href="https://www.codechef.com/viewsolution/21706372">https://www.codechef.com/viewsolution/21706372</a></p>
<p>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 <em>i-th</em> 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.</p>
<p>Let's imagine for a moment that the given array of numbers <em>A[i]</em> are not the powers of <em>K</em> but just regular numbers. In this case the proposed solution looks like this:
</p><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 <em>2A[i]</em> in two steps in order to determine whether to choose the current or the previous split as the closest to zero difference.<p></p>
<p>The proposed solution has <em>N</em> additions, <em>2N</em> subtractions, and <em>2N</em> comparisons with zero. It becomes only a matter of finding an efficient structure to represent a number with the following operations:</p>
<ul>
<li>Add a power of <em>K</em></li>
<li>Subtract a power of <em>K</em></li>
<li>Compare it with zero</li>
</ul>
<p>That's what the <em>Number</em> structure in my solution does.</p>oleg_bMon, 26 Nov 2018 01:40:57 +0530https://discuss.codechef.com/questions/141070/mxm-editorial/141145Answer by fake_herehttps://discuss.codechef.com/questions/141070/mxm-editorial/141132<p>editorialist & author's solution missing</p>fake_hereSun, 25 Nov 2018 19:51:03 +0530https://discuss.codechef.com/questions/141070/mxm-editorial/141132