MXM Editorial

general
, ,
1

PROBLEM LINK:

Practice
Contest

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)

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

Editorialist’s solution

2

Time Complexity ??

3

@aryanc403 fixed

1 Like
4

editorialist & author’s solution missing

5

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<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;
}

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:

  • Add a power of K
  • Subtract a power of K
  • Compare it with zero

That’s what the Number structure in my solution does.

2 Likes
6

How to write a number in the Kth numeral form? And support addition and subtraction on it?

7

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.

2 Likes
8

Thanks. Because of this only I understood the solution.

9

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

10

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

11

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.

12

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;


}

}
i am first timer so please help

13

Help me find the mistake. https://www.codechef.com/viewsolution/22085874