The last two columns of matrix S represent one class. The combination of zeroes and ones in these columns is called a combination of a class. Some combinations of zeroes and ones might not be achieved by any configuration, i.e. they are combinations of non-existing classes and we say that they are not possible. Knowing the solution for a combination means that we know minimal number of mistakes that can be achieved for that combination (among all the configurations of the class). Finally, we can formulate new induction hypothesis: Hypothesis: We know the solutions for all possible combinations of T(N, K). Base case can be solved by trying all configurations (combinations) for T(N, 2). We can also solve that in the following way. If we imagine an additional column before the first one (column zero where it is not allowed to cover any square), then the only possible combination for T(N, 1) is the one where no plate is put on the pavement. The minimal number of mistakes for that combination is equal to the number of zeros in the first column of the pavement. We can deal induction step easily, too. By having the solutions for all combinations for T(N, K) we have to find solutions for all combinations for T(N, K+1). The solution for some combination for T(N, K+1) is equal to the minimum number of mistakes that can be achieved by trying all possible extensions (additions) to all possible combinations for T(N, K) that produce exactly that combination for T(N, K+1). We don�need to prove this explicitly. t All configurations are implicitly tested through their classes (combinations). The execution of this step could look like this: For each combination for T(N, K) we try to extend it in all possible ways by adding new plates. For each extended combination for T(N, K+1) we notify if it was the first time it appeared and check if we got better result than the current one.ImplementationImplementation should follow induction, i.e. it should execute dynamic steps until the solution for T(N, M) is reached. From the solution for one set of combinations ( for T(N, K) ) we make the solution for another set of combinations ( for T(N, K+1) ). That means that we must have enough space to store minimal number of mistakes for two sets of combinations at a time. Since constraints in the task are N � and M �00, minimum number of mistakes certainly cannot exceed 700, so 2 bytes are sufficient for its storage. One combination is completely defined by the last two columns of matrix S that contain 2N elements of only two distinct values �0 or 1. That implies that maximal number of combinations for T(N, K) is at most 22N = 4N ( N � implies 4N �6384). Now we see how the fact that N � is used in the solution. It enables usage of partial backtracking and information storage inside a general
