DEVGOSTR - editorial

PROBLEM LINK:

[Practice][1]
[Contest][2]

Author: [Praveen Dhinwa][3]
Tester: [Sergey Kulik][4]
Editorialist: [Mugurel Ionut Andreica][5]

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

[Arithmetic progression][8], [Hamming distance][9]

PROBLEM:

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.
[1]: http://www.codechef.com/problems/DEVGOSTR
[2]: http://www.codechef.com/APRIL16/problems/DEVGOSTR
[3]: http://www.codechef.com/users/admin2
[4]: http://www.codechef.com/users/xcwgf666
[5]: http://www.codechef.com/users/mugurelionut
[6]: X
[7]: Y
[8]: https://en.wikipedia.org/wiki/Arithmetic_progression
[9]: https://en.wikipedia.org/wiki/Hamming_distance

1 Like

Is there any Online processing algorithm for this question?

If anyone knows it then please do comment your logic (not the link to the solution)… I would really appreciate it.

“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? :smiley: 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!!

Same here.

I didn’t compute all the strings in beggining, but got 60 pts as I was constructing for every testcase.

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

1 Like

This question disappointed me.
Why we should get 100 points for checking every possible string (discarding bad strings at early stage)?

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.

1 Like

You may refer to my solution for implementation details.

one of the best problems i have ever seen in codechef. :smiley: 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.

In fact, for A = 3 the length of good string cannot exceed 26 by Van der Waerden’s Theorem.

3 Likes

Thnx @likecs…

I had expected a much better logic(and implementation) :frowning:

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.

Hope to see a better question next time…

@admin the tester and author solution is not opening.Please look into the matter.

Does anyone has dp solution for it without generating all possible solutions and checking. ?

Here is a link to dp solution https://www.codechef.com/viewsolution/9833923 .

For details refer to my comment above on “@sharad07” question.