Solution to boron2013 (Flags) by codility

27 Jan

January 27, 2014 Sheng 30

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

Question Name: boron2013 or Flags

The official solution is here.

UPDATE 2014-10-02: thanks to Piotrek Martynowicz, a bug is found and fixed.

def solution(A):

from math import sqrt

A_len = len(A)

next_peak = [-1] * A_len

peaks_count = 0

first_peak = -1

# Generate the information, where the next peak is.

for index in xrange(A_len-2, 0, -1):

if A[index] > A[index+1] and A[index] > A[index-1]:

next_peak[index] = index

peaks_count += 1

first_peak = index

else:

next_peak[index] = next_peak[index+1]

if peaks_count < 2:

# There is no peak or only one.

return peaks_count

max_flags = 1

max_min_distance = int(sqrt(A_len))

for min_distance in xrange(max_min_distance + 1, 1, -1):

# Try for every possible distance.

flags_used = 1

flags_have = min_distance-1 # Use one flag at the first peak

pos = first_peak

while flags_have > 0:

if pos + min_distance >= A_len-1:

# Reach or beyond the end of the array

break

pos = next_peak[pos+min_distance]

if pos == -1:

# No peak available afterward

break

flags_used += 1

flags_have -= 1

max_flags = max(max_flags, flags_used)

return max_flags

30 Replies to “Solution to boron2013 (Flags) by codility”

This is a solution with better upper complexity bounds:
– time complexity: O(sqrt(N) * log(N))
– space complexity: O(1) (over the original input storage)
Here is the Python implementation:

from math import sqrt

def transform(A):

peak_pos = len(A)

last_height = A[-1]

for p in range(len(A) - 1, 0, -1):

if (A[p - 1] < A[p] > last_height):

peak_pos = p

last_height = A[p]

A[p] = peak_pos

A[0] = peak_pos

def can_fit_flags(A, k):

flag = 1 - k

for i in range(k):

# we plant the next flag at A[flag + k]

if flag + k > len(A) - 1:

return False

flag = A[flag + k]

return flag < len(A) # last flag planted successfully

def solution(A):

transform(A)

lower = 0

upper = int(sqrt(len(A))) + 2

assert not can_fit_flags(A, k=upper)

while lower < upper - 1:

next = (lower + upper) // 2

if can_fit_flags(A, k=next):

lower = next

else:

upper = next

return lower

Here is the explanation:

`O(N)` preprocessing (done inplace):

A[i] := next peak or end position after or at position i

(i for a peak itself, len(A) after last peak)

If we can plant `k` flags then we can certainly plant `k' < k` flags as well.

If we can not plant `k` flags then we certainly can not plant `k' > k` flags either.

We can always set 0 flags.

Let us assume we can not set `X` flags.

Now we can use binary search to find out exactly how many flags can be planted.

Steps:

1. X/2

2. X/2 +- X/4

3. X/2 +- X/4 +- X/8

...

log2(X) steps in total

With the preprocessing done before, each step testing whether `k` flags can be planted can be performed in `O(k)` operations:

* flag(0) = next(0)

* flag(1) = next(flag(1) + k)

...

* flag(k-1) = next(flag(k-2) + k)

total cost - worst case - when `X - 1` flags can be planted:

> == X * (1/2 + 3/4 + ... + (2^k - 1)/(2^k))

> == X * (log2(X) - 1 + (<1))

> <= X * log(X)

Using `X == N` would work, and would most likely also be sublinear, but is not good enough to use in a proof that the total upper bound for this algorithm is under `O(N)`.

Now everything depends on finding a good `X`, and it since `k` flags take about `k^2` positions to fit, it seems like a good upper limit on the number of flags should be found somewhere around `sqrt(N)`.

If `X == sqrt(N)` or something close to it works, then we get an upper bound of `O(sqrt(N) * log(sqrt(N)))` which is definitely sublinear.

Let's look for a more exact upper bound on the number of required flags around `sqrt(N)`:

* we know `k` flags requires `Nk := k^2 - k + 3` flags

* by solving the equation `k^2 - k + 3 - N = 0` over `k` we find that if `k >= 3`, then any number of flags <= the resulting `k` can fit in some sequence of length N and a larger one can not; solution to that equation is `1/2 * (1 + sqrt(4N - 11))`

* for `N >= 9` we know we can fit 3 flags

==> for `N >= 9`, `k = floor(1/2 * (1 + sqrt(4N - 11))) + 1` is a strict upper bound on the number of flags we can fit in `N`

* for `N < 9` we know 3 is a strict upper bound but those cases do not concern us for finding the big-O algorithm complexity

> floor(1/2 * (1 + sqrt(4N - 11))) + 1

> == floor(1/2 + sqrt(N - 11/4)) + 1

> <= floor(sqrt(N - 11/4)) + 2

> <= floor(sqrt(N)) + 2

==> `floor(sqrt(N)) + 2` is also a good strict upper bound for a number of flags that can fit in `N` elements + this one holds even for `N < 9` so it can be used as a generic strict upper bound in our implementation as well

If we choose `X = floor(sqrt(N)) + 2` we get the following total algorithm upper bound:

O((floor(sqrt(N)) + 2) * log(floor(sqrt(N)) + 2))

{floor(...) <= ...}

O((sqrt(N) + 2) * log(sqrt(N) + 2))

{for large enough N >= 4: sqrt(N) + 2 <= 2 * sqrt(N)}

O(2 * sqrt(N) * log(2 * sqrt(N)))

{lose the leading constant}

O(sqrt(N) * (log(2) + loq(sqrt(N)))

O(sqrt(N) * log(2) + sqrt(N) * log(sqrt(N)))

{lose the lower order bound}

O(sqrt(N) * log(sqrt(N)))

O(sqrt(N) * log(N))

Sheng says:
November 8, 2014 at 4:15 pm
Thanks for your high-quality comments, which makes the site more complete!
FYI: O(log(sqrt(N))) = O(log(N) * 1/2) = O(log(N))
Reply
- Jurko Gospodnetić says:
  November 8, 2014 at 5:21 pm
  Yup, you are correct… feel free to update the final big-O boundary in the text to O(sqrt(N) * log(N)) then. 🙂
  I would if I could… 🙂
  I guess my mind just felt happy when I finally proved that the solution satisfies the O(N) requirement and stopped looking for a shorter representation for the calculated big-O boundary. 😀
  Best regards,
  Jurko Gospodnetić
  Reply
  - Sheng says:
    November 8, 2014 at 5:26 pm
    Updated, and thank you again! Enjoy coding!
    Reply
    - Jurko Gospodnetić says:
      November 8, 2014 at 6:00 pm
      heh, missed one at the start of the whole comment 🙂
  - Sheng says:
    November 8, 2014 at 6:35 pm
    Which line? I doucle checked. The content is the same as your attachment in email.
    Reply
    - Jurko Gospodnetić says:
      November 8, 2014 at 6:46 pm
      It’s the same as in my e-main, but the line:
      – time complexity: O(sqrt(N) * log(sqrt(N)))
      should be updated to:
      – time complexity: O(sqrt(N) * log(N))
  - Sheng says:
    November 8, 2014 at 7:51 pm
    Got and fixed it. Thanks!
    Reply

my solution in java(100/100)

import java.util.*;

class Solution {

public int solution(int[] A) {

if(A.length==1) return 0;

ArrayList<Integer> al=new ArrayList<Integer>();

for(int i=1;i<A.length-1;i++)

{

if(A[i]>A[i-1] && A[i]>A[i+1])

{

al.add(i);

}

int s=al.size();

if(s==1) return 1;

if(s==0)return 0;

s=(int) Math.ceil(Math.sqrt(A.length));

while(s>=0) {

int lp=al.get(0);

int c=1;

for(int i=1;i<al.size();i++)

{

int d=Math.abs(al.get(i)-lp);

if(d>=s)

{

lp=al.get(i);

c++;

if(c==s)

return c;

}

s--;}

return 0;}

}

Rose says:
September 12, 2018 at 2:33 am
Hi. Time complexity of the function
1
transform

seems to be exactly O(N). Doesn’t that account in overall time complexity?
Reply

Pedro Borges says:
June 11, 2015 at 10:46 am
I was looking for an even better solution, but my math brain is a little rusty.
Can you think of a test case that fails the simple:
solution = min(maxDistanceBetweenFlags, (lastPeak – firstPeak + 1) / maxDistanceBetweenFlags) ?
Thanks, and congrats on a great site.
Reply
- Pedro Borges says:
  June 11, 2015 at 10:55 am
  sorry, should’ve used copy & past I meant:
  solution = min(maxDistanceBetweenFlags, (lastPeak – firstPeak + 1) / maxDistanceBetweenFlags + 1)
  I mean, if we know the maximum distance between flags, then we know for sure that there are flags in each and every maxDistance slice, regardless of the starting point (as long as it is between the first and the last flag) right?
  Assuming the statement above is true (please correct me if I’m wrong) then the only thing that might limit the result would be if the resulting number of flags is bigger than the maxDistance slice size.
  Reply
  - Pedro Borges says:
    June 11, 2015 at 11:05 am
    Oh got it by myself, was still thinking in peak mode 🙂
    Reply
    - Sheng says:
      June 15, 2015 at 11:32 pm
      That is totally fine. And thanks a lot for visiting my blog 🙂
      Reply

here’s my solution:

# you can use print for debugging purposes, e.g.

# print "this is a debug message"

def solution(A):

N = len(A)

peaks = []

for i in xrange(1, N-1):

if A[i] > A[i-1] and A[i] > A[i+1]:

peaks.append(i)

if len(peaks) == 0:

return 0

# the distance for k flags requires k(k-1) distance between first and last flag

max_flags_possible = len(peaks)

while max_flags_possible * (max_flags_possible - 1) > (peaks[-1] - peaks[0]):

max_flags_possible -=1

for k in xrange(max_flags_possible, 0, -1):

flags_set = 1

distance = 0

for i in xrange(1, len(peaks)):

distance += abs(peaks[i-1] - peaks[i])

if distance >= k:

flags_set += 1

distance = 0

if flags_set >= k:

return k

return 0

I have a history on this website to post dummy solution. Here it is again 🙂
However, again, I have trouble to tell the upper boundary of my algorithm. It should be better than NlogN.
Is it O(N)? I can’t prove it…

#include <cassert>

#include <vector>

#include <algorithm>

using namespace std;

int solution(vector<int> &A) {

int len = A.size(), maxcount = 0, k;

assert(len > 0);

vector<int> peaks;

for (int i = 1; i < len - 1; ++i)

{

if (A[i] > A[i - 1] && A[i] > A[i + 1])

peaks.push_back(i);

}

len = peaks.size();

if (len == 1)

return 1;

if (len > 1)

{

maxcount = 2;

int l = 2, h = peaks[len - 1] - peaks[0], m, b = 0;

while (l <= h)

{

k = m = l + (h - l) / 2;

--m;

for (int i = 1; m > 0 && i < len; ++i)

{

if (peaks[i] - peaks[b] >= k)

{

--m;

b = i;

}

maxcount = std::max(maxcount , k - std::max(m, 0));

if (m > 0)

h = k - 1;

else

l = k + 1;

b = 0;

}

return maxcount;

}

micropentium6 says:
January 3, 2016 at 6:45 pm
Can I say: T(N)=T(N/2)+N, therefore, according to the Master Theorem, we will have big-theta(N)?
Reply
- Sheng says:
  January 3, 2016 at 10:01 pm
  I think so.
  Reference: https://en.wikipedia.org/wiki/Master_theorem
  Reply
  - micropentium6 says:
    January 4, 2016 at 8:55 am
    Thank you for the confirmation! 🙂
    Reply
  - micropentium6 says:
    January 4, 2016 at 12:57 pm
    Hi Sheng,
    If we are right, why the first solution in the official pdf claims a bisection approach will take O(NlgN)?
    http://codility.com/media/train/solution-flags.pdf
    That has been said, I try this approach on the site:
    https://codility.com/demo/results/training4P79BJ-5CQ/
    OJ detected an O(N) solution.
    Can you solve the puzzle here for me?
    Many thanks!
    Reply
  - Sheng says:
    January 6, 2016 at 9:30 pm
    Only because practically it is hard/impossible to automatically distinguish O(N) and O(NlogN). (Even when N is 1 billion, logN is 30)
    Reply

micropentium6 says:
January 3, 2016 at 1:11 pm
Hi Sheng,
I need some help here:
https://codility.com/demo/results/trainingNDDXKZ-HMW/
Since there are no more than sqrt(N) peaks in a sequence with N elements, the second loop will take at most
O(sqrt(N)*sqrt(N)) = O(N) time. Why I got time out error on all larger sequences?
Could you please shed some light?
Many thanks!
Reply
- micropentium6 says:
  January 3, 2016 at 3:32 pm
  Hi Sheng,
  I think I know why. “no more than sqrt(N) peaks” is a false statement. It’ actually no more than O(N/2). Therefore, the time complexity bumped up to O(N^2)…
  Reply
- Sheng says:
  January 3, 2016 at 10:03 pm
  Yes, you got the bug!
  Reply
Emre Can Kucukoglu says:
January 13, 2018 at 1:31 pm
Hi Sheng, thank you for solution. Among the solutions I have looked, yours is the only one that I can understand. 🙂
However, I have an issue between line 29-35. If I try to write if statements together with ‘or’ using temp variable to hold ‘pos + min_distance’, then score drops to 40%.
40% (temp variable, using OR)-> https://app.codility.com/demo/results/training2BKSCX-HGC/
100% (w/o temp variable, using OR)-> https://app.codility.com/demo/results/trainingAJJGKN-G27/
100% (temp variable, seperate if)-> https://app.codility.com/demo/results/training7JQ3GN-TNR/
100% (w/o temp variable, seperate if)-> https://app.codility.com/demo/results/trainingJK2WRG-G3D/
Could you help me to understand the reason of that?
Thank you.
Reply
- Sheng says:
  January 16, 2018 at 7:26 am
  The problem with your (temp variable, using OR) solution is: the indentation of your “return” statement is wrong~
  Reply

Here’s the solution for this in Ruby:

def solution(a)

peaks = Array.new(a.length, false)

for i in 1..a.length - 2 do

peaks[i] = true if a[i - 1] < a[i] && a[i + 1] < a[i]

end

upper_guess = (Math.sqrt(a.length).ceil + 1)

lower_guess = 0

while lower_guess < upper_guess - 1

current_guess = (lower_guess + upper_guess) / 2

if can_place_flags(peaks, current_guess)

lower_guess = current_guess

else

upper_guess = current_guess

end

lower_guess

end

def can_place_flags(peaks, flags_to_place)

current_position = 0

total_flags = flags_to_place

while current_position < peaks.length - 1 && total_flags > 0

if peaks[current_position]

total_flags -= 1

current_position += flags_to_place

else

current_position += 1

end

total_flags == 0

end

Here is Java O(N) solution:

public int solution(int[] A){

//3 elements - 1 peak

//4 elements - 1 peak

//5 elements - 2 peaks

//6 elements - 2 peaks

//since we cannot have more than (A.length-1)/2 peaks

int[] peaks = new int[(A.length-1)/2];

int maxIndex = 0;

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

if(A[i-1]<A[i] && A[i]>A[i+1]) {

peaks[maxIndex++] = i;

}

if(maxIndex>0){

int maxNumberOfFlags = 1;

while (true){

int counter = 0;

int testNumberOfFlags = maxNumberOfFlags+1;

int currentFlagsSet = 1;

int el1 = peaks[counter];

while (counter<maxIndex-1 && currentFlagsSet<testNumberOfFlags){

counter++;

int el2 = peaks[counter];

if(Math.abs(el2-el1)>=testNumberOfFlags){

currentFlagsSet++;

el1 = el2;

}

if(currentFlagsSet != testNumberOfFlags){

return maxNumberOfFlags;

}

if(testNumberOfFlags>=maxNumberOfFlags){

maxNumberOfFlags = testNumberOfFlags;

}

return 0;

}

This is my solution in java. There’s a little redundancy just for clarity. If there’s less than 3 peaks it’s the solution. In case more than 2 it needs to be checked starting from 3 till it fails to be a successful solution.

public int solution(int[] A) {

int r = 0;

final int N = A.length;

int[] nextPeakIdx = new int[N];

int firstPeakIdx = 0;

int peakAmount = 0;

int curPeakIdx = 0;

for(int i = N-2; i > 0; i--){

if(A[i-1] < A[i] && A[i+1] < A[i]){

curPeakIdx = i;

peakAmount++;

}

nextPeakIdx[i] = curPeakIdx;

}

firstPeakIdx = curPeakIdx;

if(peakAmount < 3)

return peakAmount;

r = 2;

for(int i = 3; i <= peakAmount; i++){

if(possibleNb(firstPeakIdx, i, nextPeakIdx)){

r = i;

} else {

break;

}

return r;

}

private boolean possibleNb(int firstPeak, int minDistance, int[] nextPeakIdx) {

boolean r = true;

int curPeakIdx = firstPeak;

for(int i = 1; i < minDistance; i++ ){

if( curPeakIdx + minDistance < nextPeakIdx.length &&

nextPeakIdx[curPeakIdx + minDistance] > 0 ){

curPeakIdx = nextPeakIdx[curPeakIdx + minDistance];

} else {

r = false;

break;

}

return r;

}

Javascript 100%

function flags(A) {

let peaks = [];

if (A.length < 3) return 0;

for (let i = 1; i < A.length - 1; i++) {

if (A[i - 1] < A[i] && A[i] > A[i + 1]) peaks.push(i);

}

// the max number of flags is limited by the sqrt of the no. of elements in the array

// cus, if we wanna place i flags, distance between each flag should be at least i

// we need (i - 1) distances of i

// so, (i - 1) * i should be less than or equal to N, i.e. the no. of elements in the array

// or, i ^ 2 should be less than or equal to N

// or, i should be less than or equal to sqrt of N

// also, i should always be less than or equal to the no. of peaks

// so,

// condition 1: the max flags we can have should be less than or equal to "peaks"

// condition 2: the max flags we can have should be less than or equal to sqrt(N)

// so we set "limit" as the minimum of the two

// limit: max hypothetically possible no. of flags based on conditions 1 & 2

let N = A.length;

let limit = Math.min(peaks.length, Math.floor(Math.sqrt(N)));

// edge cases

if (peaks.length === 0) return 0;

else if (peaks.length === 1) return 1;

// if none of the edge cases pass, then there should be at least one flag, at the first peak

let res = 1;

// so we can start at the "limit" (+ 1 for redundancy) and keep testing, and keep decrementing the value of i

// checking each time, against the decremented value of "limit"

// i.e. the max hypothetically possible no. of flags

for (let i = limit + 1; i >= 0; i--) {

// if both our conditions (1 and 2) are satisfied,

// then we can proceed to check if the condition specified in the question is being satisfied

// i.e. if the distance between 2 flags <= no. of flags

if (i <= Math.floor(Math.sqrt(N)) && i <= peaks.length) {

// since none of the edge cases passed,

// then there should be at least 1 flag, at the first peak i.e. at peaks[0]

let flags = 1;

let lastFlagPos = 0;

for (let j = 1; j < peaks.length; j++) {

// remember: i = the max hypothetically possible no. of flags

if (peaks[j] - peaks[lastFlagPos] >= i && flags < i) {

flags += 1;

lastFlagPos = j;

}

// if the value of "flags" for this iteration is less than the last iteration

// then return the value we found in the last iteration i.e. res

// else set res = flags

if (flags < res) return res;

else if (flags > res) res = flags;

}

return res;

}

flags([1, 5, 3, 4, 3, 4, 1, 2, 3, 4, 6, 2]);

flags([1, 3, 2]);

flags([0, 0, 0, 0, 0, 1, 0, 1, 0, 1]);

30 Replies to “Solution to boron2013 (Flags) by codility”

Leave a Reply Cancel reply