pre-read-problems.txt (1259B)
1 2. Given an M × N integer matrix Q (1 ≤ M, N ≤ 30), determine if there exists a 2 sub-matrix of Q of size A × B (1 ≤ A ≤ M, 1 ≤ B ≤ N) where mean(Q) = 7. 3 (a) Try all possible sub-matrices and check if the mean of each sub-matrix is 7. 4 This algorithm runs in O(M 3 × N 3 ). 5 6 this would use 2 for loops to iterate over all possible upper left locations 7 8 we would then have two more for loops, iterating from A -> M and B -> N, taking the mean at each step to check each possible submatrix of correct sizes from the given position. 9 10 (b) Try all possible sub-matrices, but in O(M 2 × N 2 ) with this technique: 11 12 memoize solution for sub-matrices that will be fully enclosed, reusing such computations? uncertain 13 14 (this is a see what you know before starting type question) 15 16 --- 17 18 7. You want to test if the factorial of n, i.e. n! is divisible by an integer m. 1 ≤ n ≤ 10000. 19 What should you do? 20 (a) Test if n! % m == 0. 21 (b) The naı̈ve approach above will not work, use: 22 (Section 5.5.1). 23 24 better approach: 25 26 if m <= n -> true 27 else compute prime factorization of n, iff any of the numbers <= n then true else false? 28 29 (this seems wrong in the case of factorial matching, but not totally confident; seems like there's some sort of trick like that)