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.

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

Leave a Reply

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