Painting Squares

Time limit4sMemory limit1024 MB

Summary

Paint squares black or white and choose the smallest k so that the color pattern in any window of length k, together with whether it runs off the row, always identifies the window's start.

Level: Hard8 of 10
Topics: String, Combinatorics, Greedy, Implementation
Solved: No attempts yet

Problem

Mike is playing a game with Peter. There are $n$ squares drawn on the ground in a single row, numbered $0$ to $n-1$ from left to right. At the start of the game, Peter is allowed to paint each of these squares either black or white. He will then give Mike a single positive integer $k$ ( $1 \leq k \leq n$ ).

This game lasts a total of $q$ rounds. In each round, Mike will randomly pick a square $x$ ( $0 \leq x \lt n$ ), and tell Peter the colours of the squares from positions $x$ to $x+k-1$ inclusive. If any of these positions are out of range, Mike will inform Peter accordingly as well. Peter will then need to correctly deduce $x$ based purely on this information alone.

Peter wishes to impress Mike, and thus wants to pick a value of $k$ that is as low as possible. Help Peter devise a strategy to win this game with the minimum possible value of $k$ .

Constraints

$1 \leq r \leq 10$
$2 \leq n, q \leq 1000$
$-1 \leq c[i] \leq 1$ ( $0 \leq i \lt k$ )

Examples1

Example 1
Input
```
2 2
```
Expected output
```
1
```