Solution to Min-Max-Division by codility

6 Apr

April 6, 2014 Sheng 21

Question: https://codility.com/demo/take-sample-test/min_max_division

Question Name: Min-Max-Division or MinMaxDivision

Logically, it seems to be similar with the boron2013 (Flags) challenge by Codility. And the following is my Python solution.

UPDATE – 2014/09/19: thanks to Martin Kysel. The function signature is changed to:
def solution(K, M, A):
Don’t be confused by the new parameter M. Ignore the M, use the original solution, and you will pass all the test.

def blocksNo(A, maxBlock):

# Initially set the A[0] being an individual block

blocksNumber = 1 # The number of blocks, that A could

# be divided to with the restriction

# that, the sum of each block is less

# than or equal to maxBlock

preBlockSum = A[0]

for element in A[1:]:

# Try to extend the previous block

if preBlockSum + element > maxBlock:

# Fail to extend the previous block, because

# of the sum limitation maxBlock

preBlockSum = element

blocksNumber += 1

else:

preBlockSum += element

return blocksNumber

def solution(K, A):

blocksNeeded = 0 # Given the restriction on the sum of

# each block, how many blocks could

# the original A be divided to?

resultLowerBound = max(A)

resultUpperBound = sum(A)

result = 0 # Minimal large sum

# Handle two special cases

if K == 1: return resultUpperBound

if K >= len(A): return resultLowerBound

# Binary search the result

while resultLowerBound <= resultUpperBound:

resultMaxMid = (resultLowerBound + resultUpperBound) / 2

blocksNeeded = blocksNo(A, resultMaxMid)

if blocksNeeded <= K:

# With large sum being resultMaxMid or resultMaxMid-,

# we need blocksNeeded/blocksNeeded- blocks. While we

# have some unused blocks (K - blocksNeeded), We could

# try to use them to decrease the large sum.

resultUpperBound = resultMaxMid - 1

result = resultMaxMid

else:

# With large sum being resultMaxMid or resultMaxMid-,

# we need to use more than K blocks. So resultMaxMid

# is impossible to be our answer.

resultLowerBound = resultMaxMid + 1

return result

In addition, thanks to @Guillermo (StackOverflow Profile), here is the C++ solution from @Guillermo, which inspired me. Thanks again for his sharing!

#include <cmath>

int TestLargeSum(const std::vector < int > &A, int K,int LargeSum)

{

int i,n,j;

n= A.size();

long long sum;

sum=0;

j=0;

for (i=0;i < n;i++)

{

sum += A[i];

if (sum > LargeSum)

{

j++;

if (j > (K-1)) return 0;

sum =A[i];

}

return 1;

}

int solution(int K, vector < int > &A)

{

int i,n,Amax,LargeSum;

int r,b,e,LargeSumR;

n = A.size();

LargeSum=0;

for (i=K-1; i < n; i++) LargeSum += A[i];

Amax=0;

for (i=0;i < n;i++) if ( A[i] > Amax ) Amax=A[i];

if (K==n) return Amax;

LargeSum= max(Amax,LargeSum);

b= Amax;

e= LargeSum;

if (e < b) swap(e,b);

LargeSumR=e;

// BinSearch

while (b <= e)

{

LargeSum = (b+e)/2;

r = TestLargeSum(A,K,LargeSum);

if ( r )

{

e = LargeSum -1;

LargeSumR= LargeSum;

}

else

{

b = LargeSum +1;

}

return LargeSumR;

}

21 Replies to “Solution to Min-Max-Division by codility”

Java solution, greedy checking :

class Solution {

public int solution(int K, int M, int[] A) {

int N = A.length;

int max = M*N, min = 0, mid=-1;

int total = 0;

for(int i=0;i min){

mid = (max + min) / 2;

if(check(K, mid, A, total)){

max = mid;

} else {

min = mid+1;

}

if(check(K,min,A,total)) min--;

return min;

}

boolean check(int K, int max, int[] A, int total){

int cur = 0, i=0, rest = total;

while(K > 0 && i < A.length){

while(i < A.length && cur + A[i] < max )

cur += A[i++];

K--; cur = 0;

}

return i==A.length;

}

Sheng says:
August 29, 2014 at 2:35 pm
Thanks for sharing your solution. If it was with some key comments, it would be more helpful.
Reply
Sheng says:
August 29, 2014 at 2:41 pm
I am sorry. Everytime I access your website with Firefox, the page makes FF die. I have to remove it for security consideration for my visitors.
Reply

Martin Kysel says:
September 19, 2014 at 6:12 am
Hey Sheng,
there has been a change to the function signature which I fixed but your solution nevertheless no longer works https://codility.com/demo/results/demoDJSP8K-U9H/
I get the same errors and can not explain them.
Reply
- Martin Kysel says:
  September 19, 2014 at 6:49 am
  Fixed:
  http://www.martinkysel.com/codility-minmaxdivision-solution/
  https://codility.com/demo/results/demo2T4UKQ-EPS/
  They introduced M to confuse us! 😀
  Your implementation is correct, I made false assumptions when porting it!
  Reply
  - Sheng says:
    September 19, 2014 at 10:45 am
    That is fine. And thank for telling me the change to the function signature.
    I will add some explanation to help the others to understand the solutions.
    Reply
Zheng Xu says:
April 1, 2015 at 8:05 pm
I’m confused regarding the time complexity. Why is the time complexity O(N*log(N+M)) instead of O(N*log(N*M))? The upper bound of the binary search is equal to the sum of the elements in A, which is at most N*M.
Reply
- Sheng says:
  April 5, 2015 at 8:24 pm
  Yes, you are right. The complexity is not exactly O(N*log(N+M)). O(N*log(N*M)) = O(N*(log(N) + log(M))). Therefore, when N is close to M, O(N*log(N*M)) is the same as O(N*log(N+M)). In generaly case, I do not know the answer.
  Reply
  - Yixuan Wang says:
    March 3, 2016 at 7:13 pm
    “when N is close to M, O(N*log(N*M)) is the same as O(N*log(N+M))”
    this seems wrong…
    Reply

Thank you very much for your solution. Really enlightening 🙂
Here’s the Java version of your Python solution:

class Solution {

public int solution(int K, int M, int[] A) {

int lower = max(A);

int upper = sum(A);

while(true){

int mid = (lower+upper)/2;

int blocks = calculateBlockCount(A, mid);

if(blocks < K){

upper = mid-1;

}else if(blocks > K){

lower = mid+1;

}else{

return upper;

}

private int calculateBlockCount(int[] a, int maxSum) {

int count = 0;

int sum = a[0];

for(int i=1; i<a.length; i++){

if(sum + a[i] > maxSum){

count++;

sum = a[i];

}else{

sum += a[i];

}

return count;

}

private int sum(int[] a) { int sum = 0; for(int i:a){ sum+=i; } return sum; }

private int max(int[] a) { int max = -1; for(int i:a){ if(i > max){ max = i; } } return max; }

}

Raf says:
October 3, 2015 at 11:22 am
What is throwing me off is that the exercise is asking for “expected worst-case time complexity is O(N*log(N+M))”
If I’m reading your solution correctly you’re first looping through all the elements followed by the binary search section. Isn’t that O(n) + log(n+m) ?
Reply
- Sheng says:
  October 16, 2015 at 10:30 pm
  You are partly right. The binary search at #37 is inside the while loop around #35: so the complexity is O(N) * O(log(N+M)) = O(N*log(N+M)).
  Reply

I was tricked by M…”no greater than M” made me made the assumption that the largest element in the array must be M, which is not true, well, at least in Codility test cases. I got 43% just because of failing to recognize this “fact”…
If we consider the smallest max as a monotonic sequence, the lower bound of the sequence is the largest element in the array, and the higher bound is the sum of all elements. Then we choose the possible “smallest max” at the middle of the sequence and always greedily drops half of of the sequence by comparing the number of partitions based upon current “smallest max” with the proposed K. If our partition L is less than K, we probably can find a even smaller “smallest max” by dropping the lager half of the sequence, otherwise, drop the smaller half…

#include <cassert>

#include <vector>

#include <algorithm>

#include <numeric>

using namespace std;

int solutionMinMaxDivision(int K, int M, vector<int> &A) {

int len = A.size();

assert(len > 0);

long long high=std::accumulate(A.begin(), A.end(),0ll);

long long low = *std::max_element(A.begin(), A.end());

long long m, sum;

int partition;

while (low < high)

{

m = low + (high - low) / 2;

partition = 1;

sum = 0;

for (int i = 0; i < len; ++i)

{

if (sum + A[i] <= m)

sum += A[i];

else

{

++partition;

sum = A[i];

}

if (partition <= K)

high = m;

else

low = m+1;

}

return (int)low;

}

Sheng says:
December 11, 2015 at 11:30 pm
Agree that the parameter M is misleading.
Reply

Sailingfish says:
August 18, 2017 at 12:52 pm
M is not misleading. In fact it can be proved that the result is between (mean，mean+M).
Updated by Sailingfish on Aug 19, 2017.
Reply
Boshu says:
September 19, 2017 at 5:46 am
The initial lower bound could be max( sum(A)/K, max(A) )
Reply
tripe 101 says:
January 19, 2018 at 8:42 am
In the sample given in the question; K=3, A=[2, 1, 5, 1, 2, 2, 2] should the answer not be 5 instead of the given answer 6? You can group the elements as [2,2,1].[2,2,1],[5]
Reply
- Sheng says:
  January 21, 2018 at 10:09 pm
  >> “You should divide this array into K blocks of consecutive elements.”
  You cannot shuffle the input array. Thanks!
  Reply
Evgenii says:
April 24, 2018 at 3:48 am
Sheng, thank you for great work!
I have one question, how can you prove that resultMaxMid is the minimal large sum?
Reply
- Sheng says:
  April 26, 2018 at 11:36 pm
  Essentially, the solution is a binary search among all possible answers. So yes, we get the right answer 🙂
  To better understand the solution, you could read the official answer for a very similar question boron2013 (Flags) : https://codility.com/media/train/solution-flags.pdf
  Reply
ruisong says:
October 13, 2021 at 1:26 pm
Great work. I am always inspired by your ideas and skills.
For those who are still studying in 2021, you need to get the ceiling value of the average like this (using the ceil from math)
1
resultMaxMid = ceil((resultLowerBound + resultUpperBound) / 2)

Reply

21 Replies to “Solution to Min-Max-Division by codility”

Leave a Reply Cancel reply