Solution to boron2013 (Flags) by codility

27 Jan

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.

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

  1. 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ć

    • my solution in java(100/100)

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

  3. here’s my solution:

  4. 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…

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!