×

MXM Editorial

Primary Tester: Amir Reza PoorAkhavan
Editorialist: Hussain Kara Fallah

Easy-Medium

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)$

AUTHOR'S AND TESTER'S SOLUTIONS:

AUTHOR's solution

TESTER's solution

Editorialist's solution

This question is marked "community wiki".

1181234
accept rate: 0%

19.8k350498541

Time Complexity ??

(25 Nov '18, 19:04)
1
(25 Nov '18, 19:10)

 0 Help me find the mistake. https://www.codechef.com/viewsolution/22085874 answered 25 Dec '18, 22:22 2★smeagol 1 accept rate: 0%

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() {

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;

}


11
accept rate: 0%

 0 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 1 accept rate: 0% Definitely possible. See https://www.codechef.com/viewsolution/21694533 The solution is 100 points but with Python2. The worst run-time is 1.01 sec. (29 Nov '18, 23:28) oleg_b7★
 2 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 214●6 accept rate: 10% Thanks. Because of this only I understood the solution. (27 Nov '18, 00:31) cis_pie5★ 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) cis_pie5★
 0 How to write a number in the Kth numeral form? And support addition and subtraction on it? answered 26 Nov '18, 14:09 5★rahul_g 133●4 accept rate: 25%
 2 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: int solve(const vector& A) { const int N = A.size(); int agg = 0; for(int i=0; i
 0 editorialist & author's solution missing answered 25 Nov '18, 19:51 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,820
×1,056
×56

question asked: 25 Nov '18, 02:30

question was seen: 1,617 times

last updated: 25 Dec '18, 22:22