Posts in 2020 jan

LC weekly contest 170

[sauce to contest page]( rank: 1867 / 6834 (oops) [1309. Decrypt String from Alphabet to Integer Mapping]( This one can be a bit time-consuming. You need to look two steps ahead. ```python class Solution: def freqAlphabets(self, s: str) -> str: n=len(s) a=[] i=0 while i<n: if i+2<n and s[i+2]=='#': d=int(s[i:i+2]) i+=3 else: d=int(s[i]) i+=1 c=chr(ord('a')-1+d) a+=c, return ''.join(a) ``` [1310. XOR Queries of a Subarray]( I stared at this for a while, then came the moment of realization that you can precompute a "running total" of XORs for the array and "subtract" the front end from the rear end of that array. ```python class Solution: def xorQueries(self, A: List[int], Q: List[List[int]]) -> List[int]: X=[A[0]] for a in A[1:]: X.append(X[-1]^a) res=[] for a,b in Q: if a==0: res.append(X[b]) else: res.append(X[b]^X[a-1]) return res ``` [1311. Get Watched Videos by Your Friends]( This one's solution is kinda long and buggy, I only got it at the last 30 minute. Still need to practice those graphics problems! ```python class Solution: def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]: gp=set([id]) vis=set() vis|=gp while level>0: vis|=gp ngp=set() for f in gp: for ff in friends[f]: ngp.add(ff) gp=ngp level-=1 v=[] for f in gp: if f not in vis: v.extend(watchedVideos[f]) c=list(collections.Counter(v).items()) c.sort(key=lambda x:(x[1],x[0])) return [d[0] for d in c] ``` [1312. Minimum Insertion Steps to Make a String Palindrome]( I used a longest common subsequence algorithm from the contest and got time limit error. Turns out one can use lru_cache decorator for a dp function on an interval (i, j). From this contest on, I started practicing various DP problems and got a lru_cache implementation working for a hard problem 40 minutes into contest 173. Hooray!

LC weekly contest 172

[sauce to contest]( rank: 130 / 6605 Overall this is an easy contest. The second problem can be time consuming if you don't think really clearly, though. [1323. Maximum 69 Number]( Greedy: Change the first 9 to 6. ```python class Solution: def maximum69Number (self, num: int) -> int: s=str(num) return max([num]+[int(s[:i]+'9'+s[i+1:]) for i in range(len(s))]) ``` [1324. Print Words Vertically]( Ugly implementation during contest: ```python class Solution: def printVertically(self, s: str) -> List[str]: w=s.split() R, C=len(max(w, key=len)), len(w) res=[[' '] * C for _ in range(R)] for r in range(R): for c in range(C): res[r][c] = w[c][r] if len(w[c]) > r else ' ' ans=[] for row in res: ans.append(''.join(row).rstrip()) return ans ``` Although in Python there are many solutions using zip_longest. [1325. Delete Leaves With a Given Value]( Another easy tree problem, just recurse. ```python # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode: if root: root.left = self.removeLeafNodes(root.left, target) root.right = self.removeLeafNodes(root.right, target) if root.val == target and not root.left and not root.right: root = None return root ``` [1326. Minimum Number of Taps to Open to Water a Garden]( This problem has a O(n) solution, but I noticed how small the range is compared to the garden's length, so I just used a O(nm) solution. Worked like a charm. ```python class Solution: def minTaps(self, n: int, ranges: List[int]) -> int: dp=[1<<30]*(n+1) dp[0]=0 for i, r in enumerate(ranges): for j in range(max(i-r, 0)+1, min(i+r,n)+1): dp[j] = min(dp[j],dp[max(i-r,0)]+1) return dp[-1] if dp[-1] < 1<<30 else -1 ```

LC weekly contest 173

[sauce]( rank:529/6103 btw, thoughts and prayers to [WuHan](, my birth place and my hometown. Check it out, great city, great people. (Of course don't go there after the infection dies down.) 我会用一千个夜晚,陪伴着湖北的江。 ——尧十三,北方的女王 Okay, get to the contest. [1332. Remove Palindromic Subsequences (Easy)]( The trick is to realize that the answer is either 0 or 1 or 2. (If one studies mathematics, lots of structures are "degenerate" in this sense.) If the string is empty, return 0. If the string is not a palindrome, one can first remove all 'a's and then all 'b's, if any. ```python class Solution: def removePalindromeSub(self, s: str) -> int: if not s: return 0 return 1 if s==s[::-1] else 2 ``` [1333. Filter Restaurants by Vegan-Friendly, Price and Distance]( This is a typical elementary database query like: ```mysql select, restaurant.rating from restaurants where veganFriendly like if(@veganFriendly, "1", "%") and maxPrice<@maxPrice and maxDistance<@ maxDistance order by rating desc id desc ``` The following solution uses namedtuple, though there is a faster and intuitive solution due to awice that uses names in the for loop. ```python class Solution: def filterRestaurants(self, restaurants: List[List[int]], veganFriendly: int, maxPrice: int, maxDistance: int) -> List[int]: ans=[] Restaurant = collections.namedtuple('Restaurant', ['id','rating','veganFriendly','maxPrice','maxDistance']) restaurants = [Restaurant(*r) for r in restaurants] for i,r in enumerate(restaurants): if veganFriendly: if r.veganFriendly==1 and maxPrice>=r.maxPrice and maxDistance>=r.maxDistance: ans.append(i) else: if maxPrice>=r.maxPrice and maxDistance>=r.maxDistance: ans.append(i) ans=sorted(ans,key=lambda x:(-restaurants[x].rating, -restaurants[x].id)) return [restaurants[a][0] for a in ans] ``` Easy, right? Then there's this one that tripped me off: [1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance]( I used bfs first, but found that it's not correct. Only at the last minute did I realize to use Djikstra's. Then there's this solution (due again to awice) using [Floyd–Warshall]( (I rewrote it but it's largely the same.) ```python class Solution: def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int: dist=[[1<<30]*n for _ in range(n)] for u in range(n): dist[u][u]=0 for u,v,w, in edges: dist[u][v]=dist[v][u]=w for w,u,v in itertools.permutations(range(n),3): dist[u][v]=min(dist[u][v],dist[u][w]+dist[w][v]) ans,c=-1,1<<30 for u in range(n): count=sum(dist[u][v] <= distanceThreshold for v in range(n)) if count<=c: ans,c=u,count return ans ``` Finally: [1335. Minimum Difficulty of a Job Schedule]( The last problem has been consistently easy, though. This is another DP problem. One way to think about the DP state is (time, today's jobs). That leads to the following DP solution that considers all viable jobs handled today, and queries the solution for the rest of the jobs handled up to yesterday. The dp function takes t as time (start at day 0, ends at one before original d), i as index of the last job handled. M is used to cache the maximal difficulty given an interval of jobs. ```python from functools import lru_cache class Solution: def minDifficulty(self, A: List[int], d: int) -> int: if len(A)<d: return -1 d-=1 M=dict() for i,j in itertools.combinations(range(len(A)),2): M[(i,j)]=max(A[i:j+1]) for i in range(len(A)): M[(i,i)]=A[i] @lru_cache(None) def dp(t, i): if t==0: return M[(0,i)] return min(dp(t-1,j-1)+M[(j,i)] for j in range(t,i+1)) return dp(d,len(A)-1) ``` I've walked away from competitive programming, so all pairs shortest path is kinda forgotten to me. But missing the third problem is still a pity, since its time bound probably allows N Dijkstra's to pass. Oh well, practice more and wait for the next time.