# Solution to boron2013 (Flags) by codility

27 Jan

Question Name: boron2013 or Flags

The official solution is here.

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

### 25 Replies to “Solution to boron2013 (Flags) by codility”

1. Jurko GospodnetiÄ‡ says:

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:

• Sheng says:

FYI: O(log(sqrt(N))) = O(log(N) * 1/2) = O(log(N))

• Jurko GospodnetiÄ‡ says:

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Ä‡

• Sheng says:

Updated, and thank you again! Enjoy coding!

• Jurko GospodnetiÄ‡ says:

heh, missed one at the start of the whole comment ðŸ™‚

• Sheng says:

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

• Jurko GospodnetiÄ‡ says:

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:

Got and fixed it. Thanks!

• my solution in java(100/100)

2. Pedro Borges says:

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.

• Pedro Borges says:

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.

• Pedro Borges says:

Oh got it by myself, was still thinking in peak mode ðŸ™‚

• Sheng says:

That is totally fine. And thanks a lot for visiting my blog ðŸ™‚

3. Ishaq says:

here’s my solution:

4. micropentium6 says:

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…

• micropentium6 says:

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

• Sheng says:

I think so.

• micropentium6 says:

Thank you for the confirmation! ðŸ™‚

• Sheng says:

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

5. micropentium6 says:

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!

• micropentium6 says:

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

• Sheng says:

Yes, you got the bug!

6. 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.

• Sheng says:

The problem with your (temp variable, using OR) solution is: the indentation of your “return” statement is wrong~