why not use dp??? just it will have 64 * 2 * 2 states
The solution from the editorial actually uses DP for smaller testcases (see Hint 1). The number of reachable DP states is only around 2 * log_2 N, but they are all scattered in the [1, 10^{18}] interval and having such a big array is non-practical. It’s also possible to easily use STL unordered_map for storing DP states instead of a simple array. And the execution time is definitely not outlandish, but it’s still a little bit longer than the allowed time limit (maybe the problem author specifically wanted to ensure that such solutions are not accepted?).
But it’s possible to transform the problem statement a little bit, so that all DP states of this modified problem easily fit into a small array and don’t need expensive lookups: ALBOFACE - Editorial - #2 by ssvb
1 Like
Hey, I think the observation you made when in case the ith character is an ‘E’, you either consume the entire streak of 'E’s or you leave 1 for the other player. Is it necessary? I mean I wrote a solution where I consumed any number of Es. Obviously It got passed as it explores more number of choices, but I just wanted to ask whether this approach of consuming any number of Es can give TLE or not in some test case which may not be there in the test cases of codechef. BTW, very nice approach of solving a problem. Can I ask you how do you come up with such an innovative solution? Have you solved any similar problem before? If so then can you provide links to some of those. It would be really helpful. Thanks again