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.

Complexity: O((N + M) * W)

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.

Complexity: O(10N)

C. Bored Judge

We can simulate what's happening in the scoreboard using a set, as we need the erase method to remove the team from the set, update it's score, and insert it back to the set. After each event, if the team at set.begin() has changed, we update our answer.

I used a set<pair<int,int> >, where the pair.first is the score of the team multiplied by -1 to make the maximum score comes first in the set, and pair.second is the index of the team. This way the team with the maximum score will be at set.begin(), and if there are multiple teams with the same score, the one with the smallest index will come first. You can create a struct or a class with an operator to sort them correctly instead of multiplying by -1, that would be more clean.

To update the score of a team in the set, you need to know it's current score:

set.erase(make_pair(-currentScore[x], x))); // remove
currentScore[x] += y; // update
set.insert(make_pair(-currentScore[x], x))); // insert

Complexity: O(QlogN)

D. Rectangles

E. Ya Rajaie and Books

The answer is ceil{N / 5}. To use only integers, you may output (N + 4) / 5.

Complexity: O(1)

F. Exchange

Complexity: O(QlogN)