Hey guys, Can someone point out why my approach gets TLE in this problem?

My intuition was that mapping (storing old answers) is the way to go. I tried this by creating a 2-D map and storing it like-

mp[dish_no][ingredient at last in the dish]


This stores the answer for the sub-problem.

https://www.codechef.com/viewsolution/15868589

https://www.codechef.com/viewsolution/15872361 (this one uses unordered map. Got through 1 more TC but last 2 still TLE)

The worst case for this problem is when two adjacent dishes each have near x/2 dishes where x is the total number of dishes, which has a limit of 10^6. Since in the worst case for each [dish][ingredient] you have to check all [dish+1][ingredient] the complexity is \mathcal{O}(x^2).
However this problem does not have good test cases and I got AC using this approach initially. The difference in our solutions is that you have used map instead of arrays, which are slower. And I think that is probably the reason for TLE.

1 Like

I tried using vector instead of map. I got 1 more TC correct, but last one didnt budge :(.