I am stuck at a mixture of a combinatorial and maximization problem and don't know how to proceed. Hopefully someone has an idea that can bring me further.
Imagine that we have a sequence of $n$ coins. (order is important) Most of the coins have two different sides denoted with $C$ and $D$, respectively. There are a few coins that are special: they have $C$ on both sides and are in positions $k, k+1,\ldots,k+p$ and $r, r+1,\ldots,r+q$. We are not allowed to move the coins around, but we can flip them as many times as we want. For concreteness, let's say that $n=1000$, $k=20$, $p=7$, $r=200$, and $q=35$.
We start with the configuration in which all coins have their $C$ side facing up.
"Easy" version of the problem:
Flip the coins such as to get the configuration with the highest number of coins having their $D$ side facing up. However, there are the following rules:
Rule 1: There can be no more than $14$ consecutive coins with their $D$ side facing up.
Rule 2: Between any two non-consecutive coins that have their $D$ side facing up, there must be at least $30$ coins with their $C$ side facing up.
I think that there are potentially multiple solutions (i.e., configurations of coins) that maximize the number of coins with their $D$ side up.
What would be a good strategy to arrive at or close to such a configuration?
I am thinking of using something like a greedy approach: to start at the beginning of the sequence and flip as many coins as possible (in this case $14$). Then counting $30$ "$C$ coins". After this step I will have essentially a smaller version of the same problem as before, i.e., it's a recursive solution that is applied until I reach the end of the sequence. However, I am not sure if that's a good way to approach the problem. Perhaps I'm missing something obvious. In addition, the blocks of "special" coins can vary in size, position and number.
"Hard" version of the problem:
Same objective and rules as before, however, now we have a second kind of special coins that have $D$ on both sides. Those coins come in small sequences and are positioned in accordance with the above rules. The starting configuration this time is such that all coins except of that second special kind have their $C$ side facing up.
There is actually nothing that makes the beginning of the sequence special. One could also start from the end. But I am not sure if that freedom is helpful.
Instead of $C$ and $D$ sides of coins one can also think of $0$s and $1$s, i.e. bits, and then assume that some ("special") bits are broken and cannot be changed from $0$ to $1$ or vice versa.
Edit 1: $n$, $k$, $p$, $r$ and $q$ are given, i.e., their values are known.
Edit 2: I don't know what the optimal configuration is for above numerical values. I gave them just for concreteness, so that one can more easily visualize the problem.