Let's see how can we use less memory.
We solve the problem once and save every kth row from the best matrix and from the parent matrix.

!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image02.png 80%!

!<{margin-right: 20px; auto;display:block;}blog/square-root-trick?image02.png 90%!

We can start from the last saved row to n to compute the solution path from the n - 1 line to [n/k] * k line. And then go lower and lower to compute the part of the solution between the ik (i+1)k. Computing part of the path between row ik and row (i+1)k takes k * m space and k * m time. Computing the whole path takes n/k * (k * m) = nm time and km space, keeping every kth row in memory takes [n/k]m. again we minimize memory by using k = sqrt n
Caveats

2. (Level ancestor) You are given an tree of size n. ancestor(node, levelsUp) finds the node’s ancestor that is levelsUp steps up. For example, ancestor(node, 1) returns the father and ancestor(node, 2) returns the grandfather. Implement ancestor(node, levelsUp) efficiently. (O(sqrt(n)) per query)
3. (Range median) You are given an array of size n. Implement a data structure to perform update operations a[i] = k and range median operations efficiently. The range median query, median(l, r)  returns the median element of the sorted subsequence a[l..r]. ($O(\log n)$ per update and O(sqrt n log n) per query)

You can discuss the problems in the comments section.
 
4. Compute the number of digits of n!.
5. 2 balls

You can discuss the problems in the comments section.