2
$\begingroup$

You are given a number $k$ which specifies the number of consecutive balls you can paint in a go. You are given a string $S$ of length $l$. $l$ is the number of balls and each character in the string specifies the color of the $i^{th}$ ball. I want to know whether it is possible to color all the balls in the given pattern.

e.g.,
$S=rrggg$,
$l=5$,
$k=3$

We can color this pattern in two operations. As a first step we paint first three balls in red color and in the second step last three balls in green. Hence the answer should be $2$.

I conjecture that we can always generate a pattern provided that there's at least one consecutive sequence that has same color and $l \ge k$. I've formed this conjecture using various sample tests but there's no concrete proof that I could produce. Is the conjecture true? Can you prove it?

If this can be proved logically, it's easier to code the solution of the above problem. I'd like to see the proof of the conjecture that it's always possible to produce the pattern if there's at least one consecutive sequence that has same color and $l \ge k$.

$\endgroup$
1
$\begingroup$

Every pattern with a run of length $\ell$ is feasible. Indeed, consider first that the last run has length at least $\ell$. We go over the string from left to right, and for each $i$, we paint balls $i,i+1,\ldots,i+\ell-1$ with the required color for position $i$. After going over all possible indices (i.e., all but the last $\ell-1$), we have painted the pattern.

Now suppose that there is such a run in the middle, say $r,\ldots,s$. We run the algorithm above up to position $r-1$, and the we run a similar algorithm going from left to right, until ball $r$ is painted. We have painted the pattern.

As for the optimal number of moves, one natural algorithm to consider is the algorithm described above, with a simple optimization: when attempting to paint the $i$th ball, if it is already of the correct color, then don't bother. I conjecture that this algorithm, or some simple variant of it, is indeed optimal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.