New Year and Handle Change
Contest: Educational Codeforces Round 79 (Rated for Div. 2)
Difficulty rating: 2800
Tags: binary search, dp

New Year is getting near. So it's time to change handles on codeforces. Mishka wants to change his handle but in such a way that people would not forget who he is.

To make it work, he only allowed to change letters case. More formally, during one handle change he can choose any segment of his handle $$$[i; i + l - 1]$$$ and apply tolower or toupper to all letters of his handle on this segment (more fomally, replace all uppercase letters with corresponding lowercase or vice versa). The length $$$l$$$ is fixed for all changes.

Because it is not allowed to change codeforces handle too often, Mishka can perform at most $$$k$$$ such operations. What is the minimum value of $$$min(lower, upper)$$$ (where $$$lower$$$ is the number of lowercase letters, and $$$upper$$$ is the number of uppercase letters) can be obtained after optimal sequence of changes?

Input format:
The first line of the input contains three integers $$$n, k$$$ and $$$l$$$ ($$$1 \le n, k, l \le 10^6, l \le n)$$$ — the length of Mishka's handle, the number of changes and the length of the segment.

The second line of the input contains one string $$$s$$$, consisting of $$$n$$$ lowercase and uppercase Latin letters — Mishka's handle.

Output format:
Print one integer — the minimum value of $$$min(lower, upper)$$$ after that Mishka change his handle at most $$$k$$$ times in a way described in the problem statement.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
7 1 4
PikMike

Example output:
0

Example input:
15 2 2
AaAaAAaaAAAAaaA

Example output:
2

Editorial:
Let's simplify the problem a bit: we need either to minimize the number of lowercase letters or to minimize the number of uppercase letters. Both variants can be described by the following model: we have a binary array $$$a$$$ where $$$a[i] = 0$$$ if $$$s[i]$$$ is in the correct case and $$$a[i] = 1$$$ otherwise. We can do at most $$$k$$$ operations "set $$$0$$$ on the segment $$$[i, i + l - 1]$$$" and we'd like to minimize the total sum of $$$a$$$.
At first, let's start with a solution which is pretty slow but correct. Let $$$dp[len][c]$$$ be the minimum sum of the prefix $$$a[0] \dots a[len - 1]$$$ such that $$$c$$$ operations was already applied on it.
In order to calculate this $$$dp$$$ somehow efficiently, we need to understand that it's optimal to avoid intersections of segments of applied operations so we can further specify the state of $$$dp$$$ with the following: all $$$c$$$ applied operations have their right borders $$$\le len - 1$$$. It's easy to specify the transitions: we either apply set operation on $$$[len, len + l - 1]$$$ and relax $$$dp[len + l][c + 1]$$$ with $$$dp[len][c]$$$ or not and relax $$$d[len + 1][c]$$$ with $$$dp[len][c] + a[len]$$$.
It still $$$O(nk)$$$ so we'd like to optimize it more — and we can do it using the "lambda-optimization" i. e. "aliens trick". Here we will try to describe what "aliens trick" is and the "features" of its application on the discrete calculations.
In general, "aliens trick" allows you to get rid of the restriction on the total number of operations applied to the array (sometimes it's the number of segments in the partition of the array) by replacing it with the binary search of the value $$$\lambda$$$ connected to it. The $$$\lambda$$$ is the cost of using the operation (or the cost to use one more segment in the partition). In other words, we can use as many operations as we want but we need to pay for each of them. Often, we can calculate the answer without the restriction faster.
The main restriction of the using this dp-optimization is the following (in case of the discrete model): consider the answer $$$ans(c)$$$ for the fixed $$$c$$$, or $$$dp[n][c]$$$. If we look at the function $$$ans(c)$$$ it should be "somewhat convex", i.e $$$ans(c - 1) - ans(c) \ge ans(c) - ans(c + 1)$$$ (or, sometimes, $$$ans(c) - ans(c - 1) \ge ans(c + 1) - ans(c)$$$) for all possible $$$c$$$.
Let's look at the answers of the modified version of the problem (with cost $$$\lambda$$$ for each used operation) as function $$$res(\lambda, c)$$$. It's easy to prove that $$$res(\lambda, c) = ans(c) + \lambda c$$$ and it's also "somewhat convex" for a fixed $$$\lambda$$$ (as a sum of convex functions). But, more important, it has the following property: let $$$c_\lambda$$$ be the position where the $$$res(\lambda, c)$$$ is the minimum possible. It can be proven (from the convex property) that $$$c_{\lambda} \ge c_{\lambda + 1}$$$.
This property leads to the solution: binary search $$$\lambda$$$ while keeping track of the $$$c_\lambda$$$, i. e. find the minimum $$$\lambda$$$ that $$$c_\lambda \le k$$$. But there are several problems related to the discrete origin of the problem:
• The $$$c_\lambda$$$ is not unique. In general case, there is a segment $$$[cl_\lambda, cr_\lambda]$$$ where the minimum $$$res(\lambda, c)$$$ can be achieved. But there is still a property that $$$cl_\lambda \ge cl_{\lambda + 1}$$$ and $$$cr_\lambda \ge cr_{\lambda + 1}$$$. So we need to ensure that we will always find either minimum such $$$c_\lambda$$$ or maximum such $$$c_\lambda$$$.
• The second problem comes from the first one. There are situations when $$$c_\lambda - c_{\lambda + eps} > 1$$$. It creates a problem in the next situation: suppose the binary search finished with $$$\lambda_{opt}$$$; the $$$c_{\lambda_{opt} - 1} > k$$$ and $$$c_{\lambda_{opt}} < k$$$. But we need to use exactly $$$k$$$ operations, what to do? Using float values will not help, so we don't need them (so we'll use usual integer bs). Suppose we minimized the $$$c_{\lambda_{opt}}$$$ then we can show that $$$k \in [cl_{\lambda_{opt}}, cr_{\lambda_{opt}}]$$$ or, in other words, $$$res(\lambda_{opt}, k) = res(\lambda_{opt}, c_{\lambda_{opt}})$$$. So we can claim that we calculated the value not only for $$$c_{\lambda_{opt}}$$$ but also for $$$k$$$.
In the end, if we can efficiently calculate $$$c_\lambda$$$ and $$$res(\lambda, c_\lambda)$$$ for the fixed $$$\lambda$$$, then we can binary search $$$\lambda_{opt}$$$, extract $$$res(\lambda_{opt}, c_{\lambda_{opt}})$$$ and claim that the $$$dp[n][k] = res(\lambda_{opt}, c_{\lambda_{opt}}) - \lambda_{opt} k$$$.
Finally, let's discuss, how to calculate $$$c_\lambda$$$ and $$$res(\lambda, c_\lambda)$$$ for a fixed $$$\lambda$$$. Since $$$res(\lambda, c_\lambda)$$$ is just a minimum cost and the $$$c_\lambda$$$ is the minimum number of operations with such cost. We can calculate it by simplifying our starting $$$dp$$$. (Remember, the cost is calculated in a next way: for each remaining $$$1$$$ in $$$a$$$ we pay $$$1$$$ and for each used operation we pay $$$\lambda$$$).
Let $$$d[len] = \{cost_{len}, cnt_{len}\}$$$, where $$$cost_{len}$$$ is minimum cost on the prefix of length $$$len$$$ and $$$cnt_{len}$$$ is minimum number of operations $$$cost_{len}$$$ can be achieved. Then the transitions are almost the same: we either let $$$a[len]$$$ be and relax $$$d[pos + 1]$$$ with $$$\{cost_{len} + a[len], cnt_{len}\}$$$ or start new operation and relax $$$d[pos + len]$$$ with $$$\{cost_{len} + \lambda, cnt_{len} + 1\}$$$. The result is pair $$$d[n]$$$.
Some additional information: we should carefully choose the borders of the binary search: we should choose the left border so it's optimal to use operation whenever we can (usually, $$$0$$$ or $$$-1$$$). And we should choose the right border so it's never optimal to use even one operation (usually more than the maximum possible answer).
The total complexity is $$$O(n \log{n})$$$.
P. S.: We don't have the strict proof that the $$$ans(c)$$$ is convex, but we have faith and stress. We'd appreciate it if someone would share the proof in the comment section.