Please help me in MARRAYS

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.
My solution link-

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

CodeChef: Practical coding for everyone (this one uses unordered map. Got through 1 more TC but last 2 still TLE) :frowning:

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 :(.

Can you explain your solution pleaseeee :slight_smile:

You mean the correct solution? You can see the editorial, it’s out now. It relies on the fact that you can separate the |a-b| terms because |a-b| = max(a-b, -a+b).

Yeah, its out now. Thanks! :slight_smile: