Posts in 2020 feb

lc 60 - permutation sequence

the trick is to use the condition "The set [1,2,3,...,n] contains a total of n! unique permutations." ```python import math class Solution: def getPermutation(self, n: int, k: int) -> str: k-=1 l=list(range(1,n+1)) o='' for p in range(n): f=int(math.factorial(n-p-1)) x, k = k//f, k%f o+=str(l[x]) l.remove(l[x]) return o ```

LC weekly contest 174

[sauce to contest]( rank: 525 / 6997 (first time using a pixelbook on contests. the keyboard is great but i still need to get used to it. Accidentally submitted twice, lol. Also I'm pretty tired today from security class's homework, so my code is kinda trashy. All code below are rewritten after I've completed the contests. Oh well.) [5328. The K Weakest Rows in a Matrix]( This problem asks you to rank rows of a matrix by frequency of 1's. well, you sort the rows by that frequency and create a tuple (frequency, row number) and sort the tuple. Lastly, you report the row number of the first k entries. Easy. [5329. Reduce Array Size to The Half]( This problem is kinda an easy problem. You create a frequency table and greedily select the most frequent elements until you have at least half of the elements. Then you report the amount selected. [5330. Maximum Product of Splitted Binary Tree]( Given a fixed sum, the product of a and b is largest when a=b. Also, splitting by removing one edge of a tree always means to take a subtree. So keep a list of subtree sums and find the one closest to half of the total sum. [5331. Jump Game V]( Again a DP problem. Use L and R to keep track of the left and right bound of the jumping range of the indices. Then ```dp[i] = max(dp[L[i]]...dp[r[i]]) or 1 if L[i]==R[i]```.