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.
EXPLANATION:
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.
“As the answer could be very large, print answers modulo 1^09 + 7.” So, it turns out the answer to all the testcases doesn’t even reach 10^9+7? I didn’t expect it to be this easy, I was overthinking. Anyway, I made an observation that when length(s) >= 27 and a = 3, the answer is always 0. I made a backtracking solution which only got 60 pts. Anyway, great problem!!
Please fix the solution link. I computed the answer using backtracking. It was passing 60 pts, then i just memoized solution for all the cases having k = string length and for each A value and it passed for 100 points too
one of the best problems i have ever seen in codechef. 10^9+7 modulo was not required. and it seemed to me a very tough dp, whereas one could easily understand the answer would be 0 after a certain stage.
I had expected a much better logic(and implementation)
5th or 6th question in the contest should not be only a coding question like this one,it should be a “programming” question.
The purpose of a long challenge is that people can learn an algorithm over the days and then apply it in the question so that they learn something from the question, but just processing all the strings makes no sense and does not help in “learning” anything.
You can solve it using dynammic programming and recursion (similar to digit dp). You each state that the moment you chose a given position as “a”, “b” or “c” mark the future positions are per condition. here i, j, k to be in AP as false. To save some amount of recursion, you can check that any any moment of adding leads to any future position not being able to accommodate any of “a”, “b” or “c”, return from the function. You can check the hamming distance in the code itself.
I didn’t expect it to be this easy, I was overthinking. Anyway, I made an observation that when length(s) >= 27 and a = 3, the answer is always 0. I made a backtracking solution which only got 60 pts. Anyway, great problem!!