Author: [Praveen Dhinwa]
Tester: [Sergey Kulik]
Editorialist: [Mugurel Ionut Andreica]
[Arithmetic progression], [Hamming distance]
Given a string s, the alphabet size A and a number K, find out how many good strings w of the same length as s exist, such that the Hamming distance between s and w is at most K. A string w is good if for every 3 positions i<j<k such that j-i=k-j the condition w(i)=w(j)=w(k) is false.
A is at most 3 and the maximum length of s is 50. If you try to generate all the good strings for every alphabet size up to 3 and every length up to 50 you will notice that there aren’t too many of them.
Thus, you can generate all these strings in the beginning. Then, for every test case, just iterate through all the good strings of the same length as s and for the given alphabet size. For each good string w you just need to compute its Hamming distance to s. If this distance is at most equal to K, then you increment a counter. The answer for each test case is the value of the counter.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.