@salil03 thanks for reminding me about the template.
If I understood your solution well, then the ineffcecient part is summing f(i+1,curtot+x) for every x. Rather than doing this we can store prefix sums of in another called pref. Pre[i, j] is sum of f(i, 0) + f(i, 1) + f(i, 2)ā¦ f(i, x). This will reduce the complexity by a factor of M
@lokesh2002 yes your solution is also valid. In fact that was close o the intended solution. I had to reduce the time limits, to reduce the load on Codechef servers however I donāt think it affected anyone in any way. If you know of any instance where someone got TLE just cause of the lower time limit pls tell me.
this solution is wrong. I had put a specific test case just to fail this solution. Idk how it still passed.
The case was 25 6 6. 11001, 110, 110. The correct answer is 6
Thanks, Iāll try it.
@adhyyan1252 Iāve tried it for a long time and I donāt know why Iām getting wrong answers by using prefix sums. Maybe I havenāt correctly understood how to make a prefix sum array here. Can you please explain?