SQUIRREL - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

View solution here first.
But for a given t, we don’t really need O(m * n) dp to calculate maximum nuts the squirrels can get. For each tree, we simply calculate the number of nuts that will drop in time t. After that, we sort those numbers, and pick the first n highest numbers. So complexity becomes O( m + m*log(m) + n ).

2 Likes

In the solution, it says the complexity of the solution is O( m * n * log(t) ). For arguments sake, lets assume log(t) is negligible. So complexity is O ( m * n ). But there are 20 test cases. So overall, it becomes, 20 * m * n = 20 * 10000 * 10000 = 2*10^9. That’s approximately 20 seconds. Time limit given is 1 seconds. So the solution will definitely time out.

For a given t, we don’t really need O(m * n) dp to calculate maximum nuts the squirrels can get. For each tree, we simply calculate the number of nuts that will drop in time t. After that, we sort those numbers, and pick the first n highest numbers. So complexity becomes O( m + m*log(m) + n ). I saw everyone using this one in their code.

2 Likes