## LC weekly contest 170

[sauce to contest page](https://leetcode.com/contest/weekly-contest-170) rank: 1867 / 6834 (oops) [1309. Decrypt String from Alphabet to Integer Mapping](https://leetcode.com/contest/weekly-contest-170/problems/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](https://leetcode.com/contest/weekly-contest-170/problems/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](https://leetcode.com/contest/weekly-contest-170/problems/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](https://leetcode.com/contest/weekly-contest-170/problems/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!