# Solution to Tie-Ropes by codility

28 Jul

Question Name: Tie-Ropes or TieRopes

### 11 Replies to “Solution to Tie-Ropes by codility”

1. Martin says:

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?

• Sheng says:

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. Binh Yen says:

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.

• Sheng says:

I think you did not read the challege carefully :-): two adjacent ropes can be tied together with a knot.

We do not have tree couples of adjacent (1,2).

• Binh Yen says:

Ah hah, i was mistaken. Thank you for your reply. ðŸ™‚

• Sheng says:

You are welcome! And enjoy coding!

• Soley says:

I forgot the adjacent part! then it is easy to solve!

3. I got another solution for this problem in VB.NET

• Sheng says:

Please read the “Guideline for Comments” before posting any commment! Thanks!

4. M.A says:

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.
https://codility.com/demo/results/trainingUXHC5R-HQ4/

• Sheng says:

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 ðŸ™‚