# algorithms – Proving existence of an optimal substructure for the DP problem “Equal” from HackerRank

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_mrangle$$. We need to show that $$langle o_1, o_2, dots, o_mrangle$$ 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_mrangle$$ 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$$.

Posted on Categories Articles