If you are going from right most bit to left then, let k be the number of bits left:
max=fib[k+1]*max(ct1+1,ct2)
min=min(kct1+ct2,kct2+ct1)
also answer will always be less than n/2+1 so you can prune if number of differences so far exceeds that value.
I didn’t know C1(n) beforehand. In my actual solution I considered prefixes of length 19 and got C1 = 4597. That means that for a string of length 32 I would need to consider 2^12 different suffixes and for each suffix I would need to consider at most 4597 different pairs (p1,p2). In total there are 2^18=262,144 possible prefixes.
XYHUMOQ is almost same as this problem :
Let the number of subsequences of the form 1010…10 in a string be ‘a’ and the number of subsequences of the form 1010…101 be ‘b’. So, you can represent any given binary string as a pair (a,b). By appending a 1 or 0 to such a string, you get either of these two strings (a+b,b), (a,a+b). This is because adding a ‘1’ gives ‘a’ more sequences of type 1010…1 by extending each of the previously present sequences of type 1010…10, similarly for the other character, you get ‘b’ more sequences of type 101010…10.
Now, consider the reverse process. Given a string (a,b), you can go to either (a-b,b) or (a,b-a), by removing the last bit present in it. And, furthermore, there is only one way of going back this way, depending on whether a>b or b>a. This process is the same as the GCD algorithm. And, since the string must always begin with ‘1’, we must always reach (0,1). In the given problem, its mentioned that we need to have exactly ‘X’ subsequences of the form 101010…10. So, any candidate string will be represented by a pair of the form (X,Y).
Also, since we must reach (0,1), that means that the gcd of X and Y must be 1. This still leaves us with a lot of candidates for ‘Y’. But, since all strings must end with 0, Y will always be less than X. So, we just need to loop through 1,2,3,…X-1 as the candidates for ‘Y’, and for each of them, find the number of bits the string will have, and in case its equal to ‘n’, we will see in how many places this string is different from the input string. Finally, we will print the one with the minimum number of differences as the answer. Overall, the complexity of this solution is O(XlogX).
Generate all the strings of length 20, for each string store two values X, Y where X denotes the number of good subsequences ending at last 0 and X denotes the number of good subsequences ending at last 1. This can be done simply in 202^20. Now the fun part is the observation that the number of distinct values of X is very less (order of 10^4) let these be K. For each distinct X, let’s build the next 2^12 strings and take min over the strings where X == Given ways. Time Complexity: K2^12.
The link isn’t accessible.
Also, could you explain how you found the correct suffix?
We can build a list of the cumulative number of letters from all previous suffixes. We then use a binary search to find the first letter. The binary search will bring us to a specific suffix but is only accurate for the first letter. That is because although the suffixes are in alphabetic order, their prefixes are not. We then search in both directions to find the range of suffixes that start with that particular letter. Looking for the second letter is similar, but first we need to account for all subsequences that are just that particular letter.
Got it, thanks! Could you update your answer to include this part as well?