Question: https://codility.com/demo/take-sample-test/tie_ropes
Question Name: Tie-Ropes or TieRopes
1 2 3 4 5 6 7 8 9 10 11 12 | def solution(K, A): # The number of tied ropes, whose lengths # are greater than or equal to K. count = 0 # The length of current rope (might be a tied one). length = 0 for rope in A: length += rope # Tied with the previous one. # Find a qualified rope. Prepare to find the # next one. if length >= K: count += 1; length = 0 return count |
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!
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.
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).
Ah hah, i was mistaken. Thank you for your reply. 🙂
You are welcome! And enjoy coding!
I forgot the adjacent part! then it is easy to solve!
I got another solution for this problem in VB.NET
Please read the “Guideline for Comments” before posting any commment! Thanks!
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/
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 🙂
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?
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.
Input: (3, [1, 2])
Actual: 1
Expected: 2
Please explain ?
Please re-read the question: given an integer K and a non-empty array A of N integers, returns the maximum number of ropes of length greater than or equal to K that can be created.
from [1, 2], we can only create ONE rope (as 1 + 2 = 3), whose length is equal to K (3)