Subtask 1 is as simple as it gets: just generate and intersect all possible locations of the clue.

Subtask 2: if you really have to, you can brute force the ~2^{20}~ configurations and check whether they match the clues. Your loss (of time), directly solving subtask 3 is much simpler.

Subtask 3 has a special case, helpfully shown in Example 2.

Except for that special case, we can only deduce black cells. This can be done greedily: for each clue, find the leftmost and the rightmost valid position of the corresponding block. If their intersection is non-empty, those cells are guaranteed to be black. (Proof of a more general statement is given below.)

The same approach works for subtask 4 as well. Additionally, we are able to deduce some white cells. One case is shown in Example 3. The same logic has to be applied at the beginning and at the end of a row. (In fact, the easiest solution is to prepend and append a white cell as a sentinel.)

Here's a tricky test case for subtask 4: ~n = 13~, ~k = 4~, ~c = (3, 1, 1, 3)~, ~s =~ ...._..._..... Correct output: ?XX?_X_X_?XX?. The tricky part here is that we can deduce the white cell at index ~6~. (Whenever two consecutive blocks have a fixed position, all cells between those positions have to be white.)

Subtask 4 was as far as we could get with an easy greedy approach. In order to solve the general version, we will use dynamic programming.

One possible solution looks as follows:

• Step 1: Compute prefix sums of given white cells and given black cells (each separately).
• Step 2: For each ~i~ and ~j~, compute the answer ~P(i, j)~ to the following question: "Is there a valid solution if we only consider the first ~i~ clues and the first ~j~ cells of the given puzzle (as if cutting away and discarding the rest)?"
• Base case of the recurrence: If ~i = 0~, this is possible iff there is no given black cell among the first ~j~ cells.
• Recursive case: If cell ~j-1~ is forced white, ~P(i, j) = P(i, j-1)~. If cell ~j-1~ is forced black, we verify that it is possible to place the last block there (the number of forced white cells it overlaps must be zero, the next cell to the left must be able to be white) and if that is the case, we make a recursive call ~P(i-1, j-c-1)~ where ~c~ was the corresponding clue. Finally, if cell ~j-1~ isn't forced, the answer is the logical or of both above cases.
• Step 3: The same in reverse, i.e., with suffixes of the puzzle and the list of clues.
• Step 4: For each cell, we verify whether it can be white. A cell cannot be white if it is forced to be black. If that is not the case, we try all possibilities for the number of black blocks to the left of the cell, and verify each possibility using the data we precomputed in steps 2+3.
• Step 5: For each clue, we mark all the cells where it can be located as cells that can be black. Suppose we are processing clue ~t~ and that its value is ~c_t~. For each ~i~, we verify whether the clued block can be placed starting from cell ~i~. This requires a few checks that can all be done in constant time:
  • cells ~i-1~ and ~i+c_t~ must not be forced black
  • cells ~i~ through ~i+c_t-1~ must not be forced white
  • there must be a valid solution for the first ~t~ clues and the first ~i-1~ cells
  • there must be a valid solution for the last ~k-t-1~ clues and the last ~n-i-c_t-1~ cells

The above solution can conveniently be implemented in ~\mathcal O(nk)~, where ~k~ is the number of clues. Less efficient implementations may run in ~\mathcal O(n^2)~, but these should not solve subtask 7. Other implementations may run in something like ~\mathcal O(n^2 |C|)~ or in ~\mathcal O(n |C|^2)~. These should solve subtask 5, but not subtasks 6 and 7.

Proof of the greedy solution (subtasks 1-4)

Theorem 1. Consider the version of our puzzle where initially each cell is either unknown or forced white.

Suppose that there is a cell ~x~ such that there are two valid solutions in which this cell belongs to different black blocks. Then there is also a valid solution in which this cell is white.

Proof. Suppose that we have ~i < j~ such that in the first solution, the block that covers cell ~x~ corresponds to clue ~i~, and in the second solution, it corresponds to clue ~j~.

We will now construct a new solution as follows: take the first ~j-1~ black blocks from the second solution and the remaining blocks from the first solution.

This is a valid solution because in the second solution, the first ~j-1~ black blocks are all strictly to the left of cell ~x~, and in the first solution, all the remaining blocks are strictly to the right of cell ~x~. It is also obvious that for this reason, cell ~x~ is white in the new solution. ■