A simple but slow (around O(n)) approach would be to generate the whole string and then find the nth character. Tough O(n) seems good, but this problem could be solved in much better time (with worst case around O(log(n)) and best being O(1), and the probability (on random input) of being near to the best case is many times greater that being near worst).

If you start generating the string manually, you will notice that patterns are recurring. Let us take two sub-strings, str1 as “001” (first 3 characters of the string), str2 as “011” (last 3 characters of a string of length 7, which is “001 0 011”). Now let’s generate the string in terms of str1 and str2:

str1 (0) str2 (0) str1 (1) str2 (0) str1 (0) str2 (1) str1 (1) str2 and so on…

Now we can easily correctly guess the characters at positions 0, 1, 2, 4, 5, 6, 8, 9, 10 and so on (they either belong to str1 or str2).

Now to notice how strings are reccurring, this whole string can be seen in terms of substrings str1 and str2. Apart from str1 and str2 reccuring directly in the example string, if we only write the new terms written as digits in brackets in the above example) and omit the sub-strings str1 and str2, another recurring of pattern can be seen. The new string after omitting the said characters looks same as the original string.

001 0 011, that is, str1 (0) str2 and so on…

Now in terms of programming, we can break down the problem. Notice that at any step (or iteration), we know characters at all the positions apart from positions 3, 6, 9 and so on (with base 0). In other terms, we know all the positions where modulo 4 of the character to be found is 0, 1 or 2. If the modulo is 3, we have to further recurse one more level (note that it has 1/4 chance that at any level we have to goto the next level as well, 3/4 being that we will find the result at the same level).

Also note that, getting modulo 0, 1 or 2 means we have the character either from str1 or str2. To differentiate, we will have to find out which sub-string we actually have to refer to. This can be done by noticing that the string is divided into patternse each of 4 character (as str1 or str2 has a character next to it which is not used in current iteration, making groups of 4 characters each). So we can now find out which sub-string it particularly is, by finding whether modulo 2 of the position of the character to be found divided by 4 is 0 or 1.

Here is the code:

#include <string> #include <fstream> long long int a, b; std::string str1 = "001", str2 = "011"; char res() { if(a < 3) { if((b % 2) == 0) return str1[a]; return str2[a]; } a = b % 4; b = b / 4; return res(); } int main() { std::ifstream in("/home/nishantbhardwaj2002/Downloads/A-large-practice.in"); std::ofstream out("/home/nishantbhardwaj2002/Downloads/codejam_sol2.txt"); int t; in >> t; for(int i = 1; i <= t; i++) { in >> b; b--; a = b % 4; b = b / 4; out << "Case #" << i << ": " << res() << std::endl; } in.close(); out.close(); return 0; }