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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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 |

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:

Here is the explanation:

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

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ć

Updated, and thank you again! Enjoy coding!

heh, missed one at the start of the whole comment 🙂

Which line? I doucle checked. The content is the same as your attachment in email.

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

Got and fixed it. Thanks!

my solution in java(100/100)

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.

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.

Oh got it by myself, was still thinking in peak mode 🙂

That is totally fine. And thanks a lot for visiting my blog 🙂

here’s my solution:

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…

Can I say: T(N)=T(N/2)+N, therefore, according to the Master Theorem, we will have big-theta(N)?

I think so.

Reference: https://en.wikipedia.org/wiki/Master_theorem

Thank you for the confirmation! 🙂

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!

Only because practically it is hard/impossible to automatically distinguish O(N) and O(NlogN). (Even when N is 1 billion, logN is 30)

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!

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

Yes, you got the bug!