Hello Everyone,

This tutorial should have been published 3 months ago, but I only got some free time to write it today, sorry for that.

A. Coins

Instead of having one DP table that combines all states for both Hasan and Bahosain, and having too many parameters (and therefore, huge complexity), we can build two tables, one for each person.

Let A[0][i] be the number of ways in which Hasan can pay i dollars using all coins from index 0 to the end, and B[0][i] similar but for Bahosain, then we can compute the final answer by using these two tables as follows:

for (int hasan = 0; hasan <= W; ++hasan) {
   int bahosain = W - hasan;
   if (abs(hasan - bahosain) <= K)
      res += A[0][hasan] * B[0][bahosain];
}

Building each table is a simple DP problem.

The Little Match Girl

Instead of trying to move some sticks as the problem suggests, let's count the total number of matchsticks we have and build the maximum possible number of N digits using all these sticks.

We can fill the N digits starting from the left using a simple greedy algorithm. We try to put 9 in the current digit if it is possible to to fill the remaining digits with the remaining sticks, if that's not possible, we try 8, then 7 and so on...

How do we check if it's possible to fill X digits using Y sticks? The digit 1 requires two sticks, so Y should be at least 2X to be able to fill all the digits with at least two sticks. Also, since we can't fill a digit with more than 7 sticks (the digit 8), Y should not exceed 7X, otherwise we will have some unused sticks at the end.

Digit 3 requires one more stick than 1, digit 4 requires two more, digit 5 requires 3 more, and digit 6 requires 4 more. So the conditions Y ≥ 2X and Y ≤ 7X are sufficient as we can use any remaining number of sticks to fill one digit that is not 8.