Why is the greedy algorithm optimal?

Question

Codility, lesson 14, TieRopes task ( https://codility.com/demo/take-sample-test/tie_ropes ). In short, the problem is to split the list A positive integers into the maximum number of (adjacent) subscriptions having a sum of at least K

I just came up with a greedy solution, because that's the name of the lesson. It passes all the tests, but I do not know why this is the optimal solution (if it is optimal at all).

 int solution(int K, vector<int> &A) { int sum = 0, count = 0; for (int a : A) { sum += a; if (sum >= K) { ++count; sum = 0; } } return count; } 

Can someone tell me if and why this solution is optimal?

Answer 1

I may be naive or wrong here, but I think it is not too difficult (although not obvious) to see that the algorithm is really optimal.

Suppose you have an optimal list section with a maximum number of subscribers. You may or may not have all the list items, but since adding an item to a valid list also results in valid lists, it can be assumed that any possible “remaining” item that was not originally assigned to any subscriptions was randomly assigned to one of its related subscriptions; therefore, we have a proper optimal list partition, which we will call P1.

Now let's think about a section that would create a greedy algorithm, say, P2. There are two things that can happen for the first P2 subscriptions:

• It may be the same as the first subscription in P1.
• It may be shorter than the first subscriptions in P1.

In 1. you repeat the argument, starting with the next item after the first sublist. If each subsequent sub-list created by the algorithm is equal to that in P1, then P1 and P2 will be equal.

In 2. you also repeat the reasoning, but now you have at least one “additional” subject. So, the following sublist may:

2.1. Get to the next sublist in P1.
2.2. End before the next sublist in P1.

And repeat. So, in each case, you will have at least as many subscribers as P1. This means that P2 is at least as good as any possible section of the list and, in particular, any optimal section.

This is not a very formal demonstration, but I consider it valid. Please indicate what you think is wrong.

Answer 2

Here are ideas that lead to formal proof.

• If A is the suffix B , then the maximum partition size for A less than or equal to the maximum partition size for B , since we can expand the first count of section A to include new elements without decreasing its sum.

• Each correct prefix of each sublist in a greedy decision is added up less than K

• It makes no sense to have spaces, because we can add the missing elements to the adjacent list (I thought that my wording of the question excluded this possibility by definition, but I will say it anyway).

A formal proof can be carried out by induction to show that for any non-negative integer i there exists an optimal solution that is consistent with the greedy solution on the first subcrystals i each of them. It follows that when i is large enough, the only solution consistent with greedy is greedy, so the greedy solution is optimal.

The basis i = 0 is trivial, since an arbitrary optimal solution will be satisfied. The inductive step is to find the optimal solution that is consistent with the greedy one in the first subcristi i , and then shortens the i+1 th sublist according to the greedy solution (by observation 2, we really reduce this count, since it starts from the same position, as greedy, according to observation 1, we can accordingly expand the i+2 th subset of the optimal solution.