CF - An impassioned circulation of affection

Official Editorial

Solution (Two Pointers)

Time Complexity: $\mathcal{O}(nq)$

For each query we can keep a sliding window where no more than $m$ letters in the window are not $c$.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	int garland_len, query_num;
	string garland;
	cin >> garland_len >> garland >> query_num;

	for (int i = 0; i < query_num; i++) {
		int max_repaint;

Alternative Solution (Two Pointers with Prefix Sums)

Time Complexity: $\mathcal{O}(n(k+q))$

For each query we can use prefix sums to check the number of occurrences of a given letter $c$ and use two pointers to find the maximum Koyomity ending at a given pointer $p2$ from $0 \dots n$.

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1500;

int dp[26][MAX_N + 1];

int main() {
	int garland_len;
	string garland;

Alternative Solution (Dynamic Programming)

Time Complexity: $\mathcal{O}(n^2k + q)$

We are performing up to $200\,000$ queries, so it may be optimal to have some way to quickly precompute our answer in constant time.

We can use dynamic programming to cache such answers.

Define $\texttt{dp}[i][j][k]$ to be the best possible score of the first $i$ characters, with $j$ amount painted of character $k$. Either two things can happen when we add an additional character.

1. We append the character and paint an additional square.

   $$\texttt{dp}[i+1][j+1][k] = \max(\texttt{dp}[i+1][j+1][k], \texttt{dp}[i][j][k] + 1)$$

2. We append the character, but since it is the same as our previous character we get to "save" a paint.

   $$\texttt{dp}[i+1][j][k] = \max(\texttt{dp}[i+1][j][k], \texttt{dp}[i][j][k] + 1)$$

Since this only gives us the best possible score that ends with length $i$, we can just take the current best and translate it using $\texttt{dp}[i+1][j][k] = \max(\texttt{dp}[i+1][j][k], \texttt{dp}[i][j][k])$.

Now, we can query the max painting score for any substring containing the first character. However, this is not required; we only have to query the optimal paintings with size $n$ (the full string) with $\texttt{dp}[n][m_i][c_i]$.

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1500;

int dp[MAX_N + 1][MAX_N + 1][26];
int garland[MAX_N + 1];

int main() {
	int garland_len;