How to solve "cancer" from Day 2? :D

Day2 Problem1. Cancer. I wrote alien's trick(since dp[n][k]-dp[n][k-1] >= dp[n][k+1] — dp[n][k] where dp[n][k] is the answer for separating first n elements into k groups) with dp check for some lambda being O(n^2) which scored 55 points, but didn't know how to improve the check to complexity of O(n) or O(nlogn). I think it has to do with the fact that the left border of the last range in some optimal solution for first i elements and j groups always shifts to the right when we increase i. Also problem is very similar to the problems where we need to use Divide and Conquer Optimization but again i didn't found how to connect these concepts.

Porblem2. Rectpoints. The idea is to use sweep algorithm: for every point (x,y) you create two events: at time x point (x,y) becomes active, and at point x+w+1 it becomes inactive. Remaining part is to check for given set of y's which range of length covers most points. This could be done using segment tree with interval updates where when point (x, y) becomes active u need to update the range [y-h, y] by +1, or -1 when it becomes inactive.

Problem3. Alpha. I used backtracking. Let's call a letter good if it's not added to the set. Then we go trough strings from first to the last and we try to add some good letter from the string into the set. During the process we keep track of the number of good letters in other strings that we haven't processed yet. If there is a string which is not processed and without any good letter we terminate the process since we won't find any valid solution afterwards. The set is being stored using a bitmask, it's easy to see that we don't need to use additional variable for position for the current string since position is the number of elements in the set + 1. Since in the backtracking we revisit states multiple time we can use memoization with unordered map(i couldn't use array because of the memory problems). I personally dislike this problem since i thought there is a "smarter" solution not only tuning the code to avoid memory and time limit problem.