Solutions to ICOP 3

@salil03 thanks for reminding me about the template.

check this: Online Compiler and IDE - GeeksforGeeks

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?