CSES problemset editorial

Put numbers in a set and print its size.

Sort the apartments array and the rooms array. If apartments[i] - room[i] <= k, then we got an answer.

for (int i=0,j=0;i<app.size()&&j<room.size();){
	if (abs(app[i] - room[j]) <= k) {
		i++; j++; ans++;
	}
	else {
		if (app[i]-room[j] > k) j++;
		else i++;
	}
}

Based on Two Pointer Approach.
Each gondola can have max two child in it whose total weight should be less than or equal x. We can rephrase the question as "Find number of pairs of numbers in array whose sum equals to target x". Once we have this number, we can simply add the number of elements which couldn't be paired to it.

Code: https://cses.fi/paste/56c2246f697c07422656cd/

Based on Greedy + Sorting
Put the price of each ticket in a multiset. Then for each customer, find the lower bound i.e., the ticket price which is greater than or equal to price customer is willing to pay. After that remove that ticket price from multiset.

Code: https://cses.fi/paste/8ae8898f755b7c73269cfc/

Based on Greedy + Sorting
Maximum number of customers means the most number of overlapping sequences. Every arrival time increments the overlap and every departure time decrements the overlap. We are required to sort the arrival and departure times together and find max(sum of +1 & -1 by arrivals & departures).

Code: https://cses.fi/paste/f8a04ea7c15eb2b6269ce9/

Based on Greedy + Sorting
Sort periods by order of ending time. Then, if ending time of one movie is greater than or equal to that of previous movie, then increment your ans.

Code: https://cses.fi/paste/67853cbe6ac0a0cf269d22/

Based on Two Pointer Approach. However, restriction on sorting array.
We can by-pass the restriction on sorting if we can remember the indices in unsorted array. We can either store it somewhere or we can make vector<pair<ll, ll>> for sorting number along with its previous index.

Code: https://cses.fi/paste/eea715c7a1a4c5a026d9e4/

Based on Prefix Sums.
Prefix Sum can be used to find sum of a certain subarray a[i,j] by p[j] - p[i] in O(1) time. For maximum subarray sum, we need to subtract min prefix sum from max prefix sum.

Code: https://cses.fi/paste/d1d475dd655719be2659d0/

Classic Greedy Question.
Find the median of sorted array and get the summation of absolute differences of median and array element.

Code: https://cses.fi/paste/e332a763ca3ce071269d86/

Classic Greedy Question + Prefix Sums
Sort the array first, then find prefix sum, while pf[i] >= coins[i].

Code:

int n; cin >> n;
vector<int> coins;
for (auto &i: coins) cin >> i;
sort(coins.begin(), coins.end());
int sum = 1;
for (int i=0;i<n && sum>=coins[i];i++) sum += coins[i];
cout << sum << endl;

Observation based question.


Code: https://cses.fi/paste/e332a763ca3ce071269d86/

Observation based question.
Continuation of Collecting Numbers I, just that right now we have to perform the same calculation at each of the m swaps.

Code: https://cses.fi/paste/cf5b854d677858a526a507/

Classic Sliding Window Question
Place i & j at same position and increase j until a duplicate is found. At every iteration, jth element is inserted & ith element is erased. Therefore, maintaining O(n) complexity.

Code: https://cses.fi/paste/d65fa65e76c228ed26a32d/

Similar to Maximum Subarray Sum I, we need to find the largest subarray sum provided the length of the subarray is between a and b. Let's revisit Maximum Subarray Sum I, where we used prefix sum array and then subtracted the largest prefix sum from smallest prefix sum to get the maximum subarray sum. We shall do something similar in this case, while considering the length constraint given. Also, note that we have to consider the negative elements given in input too.
Since the number of elements is large, we will use INF (1e18) instead of INT_MIN.

Code: https://cses.fi/paste/9f2e28ce959484e426d2e2/

Similar to Stepping Stones Problem. We can select numbers between 1-6 (duplicates allowed) until the sum is N. We require the count of such selections. Therefore, the state should constitute the count at given N (dp[x]). The base case is that dp[0] = 1. Therefore,
dp[x] = dp[x-1]+dp[x-2]+dp[x-3]+dp[x-4]+dp[x-5]+dp[x-6].

Code:

This is a classical Knapsack problem. The state dp[x], should be the number of coins, that are required to produce target sum. The base case dp[0] would be 0, since we cannot have a sum if we don't have coins. Then for the transitions, if we include the last coin, then state would be incremented by 1. We require to take the optimal solution of the previous state.

Code: https://cses.fi/paste/52086d95520ac9c2286115/

This is a direct application of Unbounded Knapsack problem. The state dp[x] is the number of distinct ways to produce sum, x. For the base case, dp[0] = 1 because empty set is only way to make the sum = 0. To choose a coin to get sum x, we need to choose any combination of coin y (where y = x - coin[i]) such that it matches x - y. Therefore, we need to sum over all the combinations.

Code: https://cses.fi/paste/92936dba4c962a4a286183/

This is a tricky question. The state would be denoted by dp[idx][val], which is the number of ways to fill array till position i, denoted by v. For idx = 0, dp[0][val] = 1, since val could be any value. But for idx > 0, we can fill a 0 with any value val provided previous number is either of { val - 1, val, val + 1 }. Therefore, transition would be:
dp[idx][val] = dp[idx-1][val-1] + dp[idx-1][val] + dp[idx-1][val+1].

Code: https://cses.fi/paste/52bd3ac7d4f28363286a4a/

The edit distance is a spin off of LCS. Basically, we are given two strings "LOVE" & "MOVIE", and we have operations ADD, REMOVE & REPLACE to make the strings equal. If we find the LCS("LOVE", "MOVIE"), we get "OVE". Therefore, we delete(L) from "LOVE" giving "OVE" & then add "M" & "I", to make "MOVIE". Therefore, the number of operations are 3. Now, if the problem had only ADD or REMOVE operations. Then, this would be the approach. However, we find that we have a REPLACE operation too.

Therefore, let's think about the subproblems & try to apply pull dp on the state dp[i][j]. The subproblem would be to perform the operations on part of string a till ith index & part of string b till jth index.
- Delete: dp[i][j] = 1 + dp[i-1][j] (from a)
- Add: dp[i][j] = 1 + dp[i][j-1] (add from b to a -> delete something from b)
- Replace: dp[i][j] = 1 + dp[i-1][j-1]
- Equal terms: dp[i][j] = 0 + dp[i-1][j-1] (replace didn't happen so the 0)


Code: https://cses.fi/paste/74d9aae48a77d94a2869c0/

Let us first guess the state of this problem, obviously dp[w][h] which is the minimum cost of cuts required to make a rectangle of dimensions w*h a square, i.e, w == h. Let's consider the base case, dp[0][0] = 0, also, dp[1][1] = 0, since they are all squares. So, if i == j, dp[i][j] = 0 otherwise dp[i][j] = INT_MAX (since we are minimizing). Now, lets move ahead with the tramnsition, if we cut the rectangle dp[i][j] then, we are left with two parts dp[i-k][j] & dp[k][j]. We must consider both in the transition state. Also, we have two cuts - horizontal and vertical.

Therefore, dp[i][j] = min(1 + dp[i-k][j] + dp[k][j], dp[i][j]) and dp[i][j] = min(1 + dp[i][j-k] + dp[i][k], dp[i][j])

Code: https://cses.fi/paste/875e9cccd088e7242a6589/