-1
$\begingroup$

Q: How one would prove the existence of an optimal substructure for the following DP problem "Equal" from HackerRank?

Problem statement:


enter image description here


My attempt:
Let $ A = [ a_1,a_2,...,a_n ] $ be our initial list where for all $ 1 \leq i \leq n $, $i$ is the $ith$ person and $ A[i] $ is the number of chocolates the $ ith $ person has.
Denote $ chocolate_{list} = [ 1,2,5] $. Suppose that in order to optimally distribute the chocolates in $ A $ there exists $ 1 \leq k_1 \leq m $ s.t. there exists $ 1 \leq q_1 \leq 3 $ s.t. we distribute $ chocolate_{list}[ q_1 ] $ to all workers except the $ k_1 th $ worker. Denote this newly created list as $ \hat{ A } $. Note that the number of ways to distribute the chocolates in $ \hat{ A } $ [by the rule that we distribute to all workers except one ] is itself the optimal number of ways to distribute the chocolates. Otherwise, we'd have $ 1 \leq k_2 \neq k_1 \leq n $ or $ 1 \leq q_2 \neq q_2 \leq 3 $ and distribute the chocolates in $ A $ [ according to the rules given in the problem description ] and denote this new array as $ A^{'} $ . [ I stopped here because I'm not sure how to continue to find a contradiction ].

Q: Does this DP problem even have an optimal substructure? If so what is the proof for the existence of it?

Notes:
Reminder to the steps used when showing the existence of optimal substructure ( from CLRS ) :

  1. You show that a solution to the problem consists of making a choice, such as choosing an initial cut in a rod or choosing an index at which to split the matrix chain. Making this choice leaves one or more subproblems to be solved.
  2. You suppose that for a given problem, you are given the choice that leads to an optimal solution. You do not concern yourself yet with how to determine this choice. You just assume that it has been given to you.
  3. Given this choice, you determine which subproblems ensue and how to best characterize the resulting space of subproblems.
  4. You show that the solutions to the subproblems used within an optimal solution to the problem must themselves be optimal by using a “cut-and-paste” technique. You do so by supposing that each of the subproblem solutions is not optimal and then deriving a contradiction. In particular, by “cutting out” the nonoptimal solution to each subproblem and “pasting in” the optimal one, you show that you can get a better solution to the original problem, thus contradicting your supposition that you already had an optimal solution. If an optimal solution gives rise to more than one subproblem, they are typically so similar that you can modify the cut-and-paste argument for one to apply to the others with little effort.

( since it might help, i'm providing an example for proof of the existence of optimal substructure of different problem: ) Example of proving the existence of an optimal substructure for the matrix parenthization problem ( CLRS , chapter 15.2 ):
enter image description here

Thanks in advance for any help!

$\endgroup$
5
  • $\begingroup$ We require you to credit hte original source of all copied material: cs.stackexchange.com/help/referencing This appears to be copied from hackerrank.com/challenges/equal/problem without attribution. $\endgroup$
    – D.W.
    Sep 5, 2021 at 22:52
  • $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. Don't forget to give proper attribution to your sources! $\endgroup$
    – D.W.
    Sep 5, 2021 at 22:54
  • $\begingroup$ I wrote down the problem's from "HackerRank" ,was that extremely hard to miss the attribution? . $\endgroup$
    – flamel12
    Sep 6, 2021 at 7:02
  • $\begingroup$ I didn't miss that. We expect you to provide a more specific attribution, including a link to the original source. See the guidelines that I already linked to: cs.stackexchange.com/help/referencing $\endgroup$
    – D.W.
    Sep 6, 2021 at 7:41
  • $\begingroup$ Ok, I'll add the links themselves next time. $\endgroup$
    – flamel12
    Sep 6, 2021 at 7:44

1 Answer 1

1
$\begingroup$

Let $\langle o_1, o_2, o_{m+1}\rangle$ be a non-empty optimal sequence of operations that distributes the chocolates evenly, i.e., such that the final distribution is $[k,k,k, \dots, k]$.

Let $\alpha_i$ be the number of candies given to the $i$-th person by operation $o_{m+1}$ and consider the subsequence of operations $\langle o_1, o_2, \dots, o_m\rangle$. We need to show that $\langle o_1, o_2, \dots, o_m\rangle$ is an optimal sequence of operations to obtain the final distribution $[k-\alpha_1, k-\alpha_2, \dots, k-\alpha_n]$.

The proof is by contradiction. Suppose that $\langle o_1, o_2, \dots, o_m\rangle$ is not optimal, hence there is some sequence of operations $\langle o'_1, o'_2, \dots, o'_\ell \rangle$ that yields the final distribution $[k-\alpha_1, k-\alpha_2, \dots, k-\alpha_n]$ and such that $\ell < m$. Therefore, the sequence $\langle o'_1, o'_2, \dots, o'_\ell, o_{m+1} \rangle$ yields the distribution $[(k-\alpha_1) + \alpha_1, (k-\alpha_2) + \alpha_2, \dots, (k-\alpha_n) + \alpha_n] = [k, k, \dots, k]$. The number of operations of the above sequence is $\ell + 1$ and, by the optimality of $\langle o_1, o_2, \dots, o_{m+1}\rangle$, we know that $\ell+1 \ge m+1$ since every sequence that yields $[k,k,\dots,k]$ must consist of at least $m+1$ operations.
This results in the contradiction $m+1 \le \ell+1 < m+1$.

$\endgroup$
3
  • $\begingroup$ Marvelous!, a question: why $ o'_{m+1} $ isn't necessarily $ o_{m+1} $? or are they the same? $\endgroup$
    – flamel12
    Sep 6, 2021 at 7:30
  • $\begingroup$ @hazelnut_116, you are right, that was a typo. I fixed it. Thanks. $\endgroup$
    – Steven
    Sep 6, 2021 at 9:13
  • $\begingroup$ Last question: do you know of good books that teach how to apply pure math and proof techniques to programming concepts? besides CLRS? $\endgroup$
    – flamel12
    Sep 6, 2021 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.