# Solution to Tie-Ropes by codility

28 Jul

Question Name: Tie-Ropes or TieRopes

### 15 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:

• 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:

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

5. ortho says:

Hello!

I dont know why but my first intuition was to sort the ropes first. But then i was getting 25% on codility. Is it because sorting (for examples descending) will get minimum not maximum number of ropes?

• Sheng says:

From the challenge description: Two adjacent ropes can be tied

Sorting breaks the order. Please keep in mind that only “adjacent ropes” can be tied.

6. Mohd Faisal Ansari says:

Input: (3, [1, 2])
Actual: 1
Expected: 2