Unofficial editorial for this problem

Length of beach is L, # of pre-placed umbrellas is N, # of spare umbrellas is K, length of spare umbrella is X.

# Subtask 1

Classic LeetCode type problem. The answer has to be formed by some contiguous block of touching, pre-placed umbrellas. Merge touching intervals and output largest (merged) interval.

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int maxn = 1e5+5;
int L, N, K, X;
pii ar[maxn];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("beachin.txt", "r", stdin);
	freopen("beachout.txt", "w", stdout);
	cin >> L >> N >> K >> X;
	for(int i = 1; i <= N; i++) {
		int x, y; cin >> x >> y;
		ar[i] = {x, y};
	}
	sort(ar+1, ar+1+N);
	vector<pii> mer;
	for(int i = 1; i <= N; i++) {
		#define mb mer.back()
		if(mer.size() and ar[i].first-1 <= mb.second) {
			mb = {min(mb.first, ar[i].first), max(mb.second, ar[i].second)};
		} else mer.push_back(ar[i]);
	}
	N = mer.size();
	int res = 0;
	for(auto it : mer) {
		res = max(res, it.second-it.first+1);
	}
	cout << res << "\n";
}

# Subtask 2

empty spots = cells not covered by a pre-placed umbrella

We can use prefix sums to calculate # of empty spots in a contiguous range. If a range is valid (a candidate solution), the empty spots within that range must be <= K. Also notice that if the maximum valid range (MVR) starting at cell i is [i, j) then the MVR starting at cell i+1 is at least [i+1, j) because the # of empty spots in [i+1, j) is <= # of empty spots in [i, j). Knowing this, we can use a two pointer technique, advancing j further as we iterate all possible i from 1 to L and calculate the MVR starting from each cell.

Remember to merge touching intervals first (see code comments)

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
const int maxn = 1e5+5;
int L, N, K, X;
bool occ[maxn];
int pref[maxn];
pii rg[maxn];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("beachin.txt", "r", stdin);
	freopen("beachout.txt", "w", stdout);
	cin >> L >> N >> K >> X;
	assert(X == 1);
	for(int i = 1; i <= N; i++) {
		int x, y; cin >> x >> y;
		rg[i] = {x, y};
	}
	//must merge touching intervals before
	//populating occ otherwise TLE
	//because N,L <= 100,000 and jury can just dump
	//[1, 100,000] 100,000 times
	sort(rg+1, rg+N+1);
	vector<pii> mer;
	for(int i = 1; i <= N; i++) {
		#define mb mer.back()
		if(mer.size() and rg[i].first-1 <= mb.second) {
			mb = {min(mb.first, rg[i].first), max(mb.second, rg[i].second)};
		} else mer.push_back(rg[i]);
	}
	N = mer.size();

	//safe to populate occ array now
	for(auto it : mer) {
		for(int i = it.first; i <= it.second; i++) {
			occ[i] = true;
		}
	}
	for(int i = 1; i <= L; i++) pref[i] = pref[i-1] + !occ[i]; 
	//if occ[i] false then is empty spot
	int res = 0, j = 1;
	for(int i = 1; i <= L; i++) {
		while(j <= L and pref[j] - pref[i-1] <= K) j++;
		//[i, j) is maximum valid range starting at i
		res = max(res, j-i); 
	}
	cout << res << '\n';
}

# Subtask 3 and 4

From now on we assume WLOG intervals are disjoint (not touching). And sorted by left endpoint. If this is not the case just sort them and merge touching intervals - solution is not affected.

Let [i, dp[i][j]) be the MVR (maximum vaild range) starting at i, using j spare umbrellas. So dp[i][j] is the exclusive right endpoint of this MVR. Our answer is the maximum of dp[i][K]-i across all i from 1 to L. If i is occupied (by a pre-placed umbrella) then dp[i][j] = dp[i+1][j], we don’t place a spare umbrella here because clearly we don’t need to. However, if i is not occupied we need to use a spare umbrella which will take X spots, so dp[i][j] = dp[i+X][j-1]. Notice if j = 0 (and i is not occupied) we can’t use a spare, so we can’t make a valid range, so dp[i][0] = i. Also, i+X could overflow out of the beach, to fix this, we change our relation dp[i+X][j-1] to dp[min(L+1, i+X)][j-1], where dp[L+1][j] is always set to L+1. Basically if we access dp[L+1][j] our MVR has taken us all the way to the end of the beach and we can’t go any further and so the MVR is always [i, L+1) from this point onwards.

The code probably makes more sense. Try out a few things by hand to convince yourself that the DP relation is correct.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
using pii = pair<int,int>;
int L, N, K, X;
int dp[maxn][6];
bool occ[maxn];
pii rg[maxn];
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("beachin.txt", "r", stdin);
	freopen("beachout.txt", "w", stdout);
	cin >> L >> N >> K >> X;
	for(int i = 1; i <= N; i++) {
		int x, y; cin >> x >> y; rg[i] = {x, y};
	}
	//Merging intervals
	sort(rg+1, rg+N+1);
	vector<pii> mer;
	for(int i = 1; i <= N; i++) {
		#define mb mer.back()
		if(mer.size() and rg[i].first <= mb.second+1) {
			mb.second = max(mb.second, rg[i].second);
		}
		else mer.push_back(rg[i]);
	}
	for(auto it : mer) {
		for(int j = it.first; j <= it.second; j++) {
			occ[j] = true;
		}
	}

	//DP
	//occ[i] = is i occupied by pre-placed umbrella? 
	for(int j = 0; j <= K; j++) dp[L+1][j] = L+1;
	int res = 0;
	for(int i = L; i >= 1; i--) {
		dp[i][0] = occ[i] ? dp[i+1][0] : i;
		for(int j = 1; j <= K; j++) {
			dp[i][j] = occ[i] ? dp[i+1][j] : dp[min(i+X,L+1)][j-1];
		}
		res = max(res, dp[i][K]-i);
	}
	cout << res << '\n';
}

# Subtask 5, Full Solution

Let’s analyze our Subtask 4 recurrence. In essence, the DP places umbrellas side-by-side until it’s supposed to place an umbrella that starts within a preplaced umbrella. Then, realizing we are just wasting space by doing so, it “skips” to the end of the umbrella and resumes placing side-by-side until there are no more spare umbrellas. See image below:

Note that if we completely cross over a pre placed umbrella we should just keep placing umbrellas side-by-side.

We can simulate this process for each spot on the beach. But that’s Omega(LK). To speed it up, we should calculate how many umbrellas we need to place before we can “skip”. This can be done via finding, from each possible starting point the first skipped umbrella (FSU). After we skip, then we can just “move” our starting point to the right of the skipped umbrella and repeat the same process. Much like recursion. Notice that in our recursive step we only use the points right after a pre-placed umbrella. So we’ll calculate the FSU for N points (it should become clear later why this is sufficient to find the solution).

But, how to find FSU?

Let i be our starting position. Our future position after placing S spare umbrellas will be i + SX. We “skip” when i + SX = c where a <= c <= b, and [a, b] corresponds to a pre-placed umbrella. Our FSU is the first c that satisfies those constraints. From the above equation we have:

Notice that because [a, b] corresponds to a range, [a % X, b % X] will correspond to a circular range. Our FSU will be the first umbrella after our starting point that contains i % X in its circular range. Iterating from the last umbrella, we can use a lazy create (X <= 1,000,000,000) lazy update (set all elements in a range to a particular value) segment tree to find the FSU of N points in O(N log X).

Note that if a % X > b % X, the modulo range will “wrap around”, we express this as [a % X, X-1] \({\displaystyle \cup}\) [0, b % X]. For example, in the image above [5, 2] is [5, 5] \({\displaystyle \cup}\) [0, 2]. Also note that if b-a+1 >= X then the modulo range will occupy all possible elements, we express this as [0, X-1].

If we draw an edge between i->fsu[i] we see that the corresponding graph is a bunch of trees. The cost of each edge i->fsu[i] is the number of spare umbrellas we need to place before reaching fsu[i] which can be determined using simple math division.

Optimally we want to keep going i->fsu[i] as far as possible, as each “skip” gives as some extra space. We want to ascend the child->ancestor path as far as possible without exceeding the cost limit of K spare umbrellas. To do this, we binary search on the path from i to the root of the tree. The sum of edges along a path from i to an ancestor j is sumFromRoot(i)-sumFromRoot(j). sumFromRoot can be preprocessed for all nodes using prefix sums approach in O(n) time.

Remember that the nodes in the forest are our starting points right after pre-placed umbrellas.

Define the furthest node we can reach from i to be ans[i]. It is possible that there are leftover umbrellas which should to place (it never hurts to place more umbrellas). We don’t need to apply the skipping process to these umbrellas - we can’t skip any more forward and skipping backward is the same as skipping forward from a previous umbrella.

Let the # of spaces before umbrella i be l, the # of spaces after ans[i] be r. Greedily assign umbrellas (placing them side-by-side) to l and r. (Be careful, placing an umbrella does not necessarily mean you get X extra spots).

One final edge case: the skipping process might be useless in which case the answer is min(L, K * X).

Proof and implementation is left as an exercise to the reader. (Hint: it’s painful). In my opinion, far too much effort for 12 extra points.