Author: Tomohito Hoshii

Introduction

In this review, we only explain solutions which lead to full score solutions. However, there are other solutions which give good results but do not lead to full score solutions.

In the following, the indices of elements of arrays are zero-based (i.e. they start from ~0~), and "the value set in the memory area of the machine" is called "the state" of the machine.

~M = 1002~ (10 points)

We can determine the ~i~-th character by ~m = i+3~. Concretely, we construct the sequences as follows.

$$\displaystyle (a_j, b_j) = \begin{cases} (j+1, j+1) & 0 \le j \le i-1 \\ (i+1, i+2) & j = i \\ (j, j) & j = i+1, i+2 \end{cases}$$

The ~i~-th character is 0 if the final state is ~i+1~, and it is 1 if the final state is ~i+2~.

Since ~N = 1000~, we determine each character one-by-one from the first one, and get a solution with ~M = 1002~.

~M = 1001~ (10 points)

For the ~|T|~ characters from the last one, it is possible to determine whether the string ~S~ coincides with the string ~T~ or not by ~m = |T|+1~.

For example, if ~T =~ 101, we construct as follows.

• ~a = [0, 2, 0, 2]~
• ~b = [1, 1, 3, 1]~

The current state is ~i~ if the characters are the same until the ~(i-1)~-th character of ~T~.

If the final state is ~|T|~, the last characters coincide with ~T~; otherwise, the last characters do not coincide with ~T~.

By this method, we determine the characters from the last one, and get a solution with ~M = 1001~.

~M = 502~ (37 points)

We use an ~M = 1002~ solution as above for the first half of characters (~500~ characters), and use an ~M = 1001~ solution as above for the last half of characters (~500~ characters). Combining them, we get a solution with ~M = 502~.

~M = 114~ (97 points)

We can achieve ~M = 114~ using linear algebra.

There are ~1000~ unknown quantities. We would like to have ~1000~ independent linear equations in ~1000~ variables. Since we know each quantity is either ~0~ or ~1~, we can consider equations mod ~2~.

Concretely, we proceed as follows.

We get the sum of ~S_i~'s (mod ~2~) for every ~i~ with ~i \equiv q~ (mod ~p~) by ~m = 2p~. Here we choose the values of ~p~ and ~q~ by row reduction (or Gaussian elimination) so that the vectors for chosen ~p~ and ~q~ (for example, ~[0, 1, 0, 0, 1, 0, 0, 1, 0, \dots]~ if ~p = 3~ and ~q = 1~) are linearly independent.

We can find ~1000~ linearly independent vectors in the range ~p \le 57~. Hence we get a solution with ~M = 114~.

~M = 102~ (100 points)

Combining an ~M = 114~ solution and an ~M = 502~ solution, we achieve ~M = 102~ as follows.

To get information on a particular character amounts to choose the vector ~[0, 0, \dots, 0, 1, 0, \dots, 0]~.

Up to ~102~, we determine the first ~100~ characters and the last ~101~ characters; hence we get ~201~ vectors. Additionally, in the range ~p \le 51~, we get ~799~ vectors such that the ~201+799 = 1000~ vectors are linearly independent. Hence we get a solution with ~M = 102~.