Solution to Tie-Ropes by codility

28 Jul


Question Name: Tie-Ropes or TieRopes

11 Replies to “Solution to Tie-Ropes by codility

  1. Hey Sheng,

    codility expected N space complexity. My solution is the same as yours (1), yet I am a bit skeptical about the proof of correctness.

    Are you sure that it offers the best possible solution?

    • Hello Martin! Nice to see you again!

      I cannot make sure that, our solution is the best one. But I think it shoud be the right one.

      Consider FINALLY there are N minimum-length (means if we can remove the first or last tied rope, try to remove the last one firstly and then try to remove the first) AND qualified (means larger than or equal to K) ropes (tied or not, does not matter), and we SHIFT these ropes as leftward as they can. Then we can see each qualified rope (QR) has a heading useless rope (ULR, might be none). One QR with its ULR is a section.

      (During the shifting, we cannot get more qualified ropes. Because we assume FINALLY there are N.)

      sum(ULR) or sum(ULR + part of QR) will be less than K, because the QR cannot be moved toward left anymore. And QR + ULR is larger than or equal to K, because QR is already large enough.

      Using our algorithm, we scan from left to right. So firsly we scan the zone in ULR, and cannot get a qualified rope. When we tied the ULR and QR together, we get the whole section as a qualified rope.

      The proof is not strict. But hope it be helpful!

  2. Given this input A = [1,1,1,2,2,2] , K = 3, above solution returns 2, but 3 is the right answer (we have 3 couples of (1,2) ). I think greedy cannot turn out the right answer in some cases.

  3. I feel suspicious with greedy algorithms w/o mathematical proof for the correctness of the algorithm.
    Here is my solution that seems semantically different than the shorter one you provided.

    • It’s true that I cannot prove it. While the question belongs to the chapter “Greedy Algorithms”, it’s reasonable to have a greedy solution 🙂

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!