You are not logged in. Please login at www.codechef.com to post your questions!

×

MXM Editorial

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

This question is marked "community wiki".

asked 25 Nov '18, 02:30

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 04 Dec '18, 14:08

admin's gravatar image

0★admin ♦♦
19.8k350498541

Time Complexity ??

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

link

answered 25 Dec '18, 22:22

smeagol's gravatar image

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;


}

} i am first timer so please help

link

answered 17 Dec '18, 23:20

chinmaysama_99's gravatar image

2★chinmaysama_99
11
accept rate: 0%

edited 17 Dec '18, 23:26

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

link

answered 29 Nov '18, 21:23

danyshman07's gravatar image

2★danyshman07
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★

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.

link

answered 26 Nov '18, 14:14

vipin1407's gravatar image

5★vipin1407
2146
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★

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

link

answered 26 Nov '18, 14:09

rahul_g's gravatar image

5★rahul_g
1334
accept rate: 25%

edited 26 Nov '18, 15:11

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.

link

answered 26 Nov '18, 01:40

oleg_b's gravatar image

7★oleg_b
3195
accept rate: 16%

edited 27 Nov '18, 07:59

editorialist & author's solution missing

link

answered 25 Nov '18, 19:51

fake_here's gravatar image

3★fake_here
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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