Solutions to ICOP 3

general
, , , ,
21

check this: https://ide.geeksforgeeks.org/fp6cPLMZro

22

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

23

@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.

24

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

25

Thanks, Iā€™ll try it.

26

In JOKRBOMB, how can be calculate number of shortest path using the mentioned BFS+DFS trick?

1 Like
27

@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?