0
$\begingroup$

Background

Hello everyone! I am trying to solve a problem from CSES which uses greedy algorithm. I wanted to prove the correctness of the solution formally, but I’ve found it quite challenging. I’d really appreciate any guidance or thoughts to help me think through the proof.

Here is the link to my original coding problem: https://cses.fi/problemset/task/1092/

Problem

Given the set $\{1,2,\ldots,n\}$ and a target sum $S$ (where $S\le \sum_{i=0}^n i$), find a subset of distinct elements that adds up to $S$, which contains the largest possible elements

Question

I designed a greedy algorithm that works like this:

Start from $n$. While the remaining sum is not 0, at each step, if the current number is less than or equal to the sum, include it in the subset and subtract it from the sum. Repeat until the remaining sum becomes zero.

I’ve tested this algorithm and it seems to work well, but I’m struggling to prove its correctness formally. Specifically:

  • Why this greedy approach always leads to a valid subset (one in which the elements add up to $S$, using the largest possible elements)?
  • How to write a clear proof (e.g., termination + correctness/invariant)?
$\endgroup$
2
  • $\begingroup$ Your problem statement doesn't match the linked challenged unless you mean S=n(n+1)/4 always, otherwise it's a different question. The CSES problem is solvable as described iff n=3 or 0 mod 4. $\endgroup$ Commented Apr 20 at 17:14
  • $\begingroup$ Thank you for replying. Yes, I am referring to S=n(n+1)/4. I restated the problem so that I could try to prove the correctness of my greedy algorithm. $\endgroup$ Commented Apr 21 at 1:34

2 Answers 2

Reset to default
0
$\begingroup$

Let $S_k$ represent the sum of the k largest elements of the set {1,...,n}. Clearly,

$S_{k+1} - S_k = n-k$

Choose $S : n \lt S \le S_n$, as the subset sum we wish to find, then

$(S - S_k > n - k) \Rightarrow S - S_{k+1} = S - (n - k + S_k) > 0$

Therefore,

$\exists K : 0 < S - S_K \le n - K$

leaving one of the remaining elements to include to make the sum up to S.

$S = (S - S_K) + S_K$

For $S \le n$, just choose S from the set.

$\endgroup$
0
$\begingroup$

You're working in steps. So you need to prove that each step maintains some invariant, that the number of steps is finite, and that you reach the correct answer at the last step.

In this case, let $C_i$ be the subset constructed at step i. Also consider $RS_i = S - \sum_{x \in C_i} x$. This is your "state" at each step.

You start with $C_0=\{\}$ and $RS_0=S$

Your stopping condition is $RS_n = 0$

Now see how $C_0$ and $RS_0$ evolve with each step. Two things to prove:

  1. $RS_i$ decreases by at least 1 in each step
  2. There is at least one valid way to move forward when you're in some valid step $i$

Then since S is a finite integer, in at most $n=S$ steps you will conclude.

(e.g. invariant could be that at each step $RS_i + C_i = S$, and that since you reach $RS_n = 0$ in the last step, your $C_i$ is a correct answer)

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.