Hello Everyone,
This tutorial should have been published 3 months ago, but I only got some free time to write it today. I'm 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)
B. 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
We may iterate over the string from left to right and try to swap the current letter with another one that is smaller in the alphabetical order, if such letter doesn't exist in the string, we move to the next index. Otherwise, we update the string and print it. This solution would fail on this simple case: ab, as it allows the letter b to be swapped with a. To fix this, we should only allow swapping letter A with letter B if the first occurrence of A is before the first occurrence of B and B comes first in the alphabetical order.
We can build an array F where F[c] is the position of the first occurrence of the letter c, or - 1 if it doesn't exist in the string. Then the solution would be:
for (int i = 0; i < s.length(); ++i) { if (F[s[i]] != i) // this's just to improve the complexity from O(26*N) to O(26*26+N). continue; for(int j = 'a'; j < s[i]; ++j) if (F[j] > F[s[i]]){ // No need to check that F[j] != -1 as -1 isn't greater than F[i]. // exchange the letter s[i] with the letter j, print the string, and exit both loops. } }
Complexity: O(26 * 26 + N)
G. Notes
We will start with the brute force solution and see if it's going to work. Here are some notes:
We won't need more than 8 notes of the first type (1 JD). If we want to pay 9 JDs, we may use one note of the second type and four notes of the first type (5 + 4 = 9).
We won't need more than 2 notes of the second type (5 JDs) or the third type (10 JDs).
We won't need more than 4 notes of the forth type (20 JDs). Do we need four? Yes, when we have -for example- 80 JDs and need to be able to pay 40 and 80.
Now we can have 4 for loops that try all possible answers for the first four types, [0-8] × [0-2] × [0-2] × [0-4], in O(405). We know that the remaining amount of money should be a multiple of 50. This leaves only 9 possible solutions in the worst case (http://ideone.com/QrdG5D).
So now we have a number of notes of each type, we should check if it is possible to pay for every item in the input. We may solve this problem using Dynamic Programming for each of the nine possible solutions.
Complexity: O(9 * (8 + 2 + 2 + 4) * N)
H. Cinema
First, let's increase K by one to include Rami in the required number of empty seats. Then we may check if there's a substring of length K that consists only of zeros as follows:
int count=0;
for (int i = 0; i < C; ++i){
if (str[i] == '0')
++count;
else
count = 0;
if(count == k)
break;
}
if (count == k)
printf("yes\n");
else
printf("no\n");
Complexity: O(C)
I. Simple Robot
Note that the answer for each dimension is not affected by the other one, so we may write one function that solves the 1D version and call it twice. The first time with the left/right instructions and the second time with the up/down instructions.
To solve the problem for one dimension, we may start at 0 and follow the instructions while keeping the min and the max position we reached. We ignore any instruction that will make maxX - minX ≥ N, where N is the size of the dimension.
Another solution is using ternary search as moving away from the optimal position would increase the number of skipped instructions.
Complexity: O(strLength) or O(strLength * (logR + logC))
