## leetcode weekly contest 134 question 3: 1035. Uncrossed Lines

source
(Gosh I still remembered the happiness when I figured out this DP problem after I stopped doing coding contests for a long, long time.)
At first glance, I correctly guessed that this is a dynamic programming problem. Some thirty seconds later, I sketched a scheme (in my mind in a KFC) for a solution that builds on top of earlier solutions:

`dp[i, j]` means the answer i.e. maximum number of lines we can draw from the first i characters of A (`A[:i]`) and first j characters of B (`B[:j]`)
if there's a line from `A[i]` to `B[j]` i.e. if `A[i] == B[j]`, then `dp[i, j] = dp[i-1, j-1] + 1`
otherwise, `dp[i, j] = max(dp[i-1,j],dp[i,j-1])`.

This is also explained in the code below (which comes straight from contest).

```class Solution:
def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
'''
dp[a,b]=max(dp[a-1][b],dp[a][b-1]) if A[a]!=B[b] else:
#connect the line
1+dp[a-1][b-1]
dp[0,0]=0 if A[a]!=B[b] else 1
return dp[len(A)-1,len(B)-1]
'''
dp=[[0 for _ in range(len(B))] for _ in range(len(A))]
for a in range(len(A)):
for b in range(len(B)):
#print(a,b)
if a==0 and b==0:
dp[a][b] = 0 if A[a] != B[b] else 1
elif a==0:

dp[a][b] = dp[a][b-1]
if dp[a][b]==0 and A[a] == B[b]:
dp[a][b] = 1
elif b==0:
dp[a][b] = dp[a-1][b]
if dp[a][b]==0 and A[a] == B[b]:
dp[a][b] = 1
else:
dp[a][b] = max(dp[a-1][b],dp[a][b-1])
if A[a] == B[b]:
dp[a][b] = max(dp[a][b],1+dp[a-1][b-1])
#print(dp)
return dp[len(A)-1][len(B)-1]
```

## leetcode weekly contest 134 question 2: 1034. Coloring A Border

source
This is a simple breadth-first search problem.
Also, this is when lambda functions comes in handy.
Also, this code seems to beat 95% of accepted Python solutions during the contest XD

```class Solution:
def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
#trial 1: modify dfs to add border
R = len(grid)
C = len(grid)
isborder = lambda r, c: r == 0 or c == 0 or r + 1 == R or c + 1 == C
border = []
st = [(r0, c0)]
vis = set()
colorbefore = grid[r0][c0]
while len(st) > 0:
r, c = st.pop()
isb = isborder(r, c)
nbr = [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]
for n in nbr:
if R > n >= 0 and C > n >= 0:
if (n, n) not in vis and colorbefore == grid[n][n]:
st += (n, n),
if grid[n][n] != colorbefore:
isb = True
if isb:
border += (r, c),
for b in border:
grid[b][b] = color
return grid
```

## leetcode weekly contest 134 question 1: Moving Stones Until Consecutive

source
This problem needs to be broken down into two problems. Firstly, the minimum number of moves is equal to the number of gaps (so two moves are required if there are no adjacent stones). There's a catch though, if you have [1, 3, 5], you can move 1 to 4 and that would give you one moves instead of two (the number of gaps). The maximum number of moves is the length of the gaps, if any.
Note that this problem got harder in a following contest.

```class Solution:
def numMovesStones(self, a: int, b: int, c: int) -> List[int]:
x,y,z=sorted([a,b,c])
if y-x==1 and z-y==1:
return [0,0]
mi = 0
if y-x==1 or z-y==1 or y-x==2 or z-y==2:
mi=1
else:
mi=2
ma = z-y-1+y-x-1
return [mi,ma]
```

## leetcode 338. Counting Bits

sauce
There are concise bit manipulation solutions that uses school of thoughts mentioned in the opening chapter of Knuth's famous Concrete Math book (iirc) covering the baby case of Josephus problem. Recurrence relations is indeed a very interesting math topic. See also toys.
But...strangely this rather straightforward solution beats 100%.

```class Solution {
void helper(int[] ans, int n, int i, int b){
if(i<=n){
ans[i] = b;
helper(ans,n,i*2,b);
helper(ans,n,i*2+1,b+1);
}
}

public int[] countBits(int n) {
int[] ans = new int[n+1];
helper(ans,n,1,1);
return ans;
}
}
```

## leetcode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

A dynamic programming solution would be more intuitive and faster (logarithmic advantage) than the binary search shown below. Note also that some dp is still needed here in the preprocessing phase.

```class Solution:
def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:

#print(threshold)
if min(min(row) for row in mat) > threshold:
return 0
m,n=len(mat),len(mat)
for i in range(m):
for j in range(n):
if i==0 and j==0:
continue
elif i==0:
mat[i][j]+=mat[i][j-1]
elif j==0:
mat[i][j]+=mat[i-1][j]
else:
mat[i][j]=mat[i][j]+mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]

def verifysl(sl):
for i in range(-1,m-sl):
for j in range(-1,n-sl):
b,c,d=0,0,0
if i>=0:
if j>=0:
d=mat[i][j]
c=mat[i+sl][j]
b=mat[i][j+sl]
if mat[i+sl][j+sl]-b-c+d<=threshold:
return True
return False

lo, hi = 1, min(m,n)+1
while lo < hi-1:
mid = (lo + hi) // 2
if verifysl(mid):
lo = mid
else:
hi = mid
return lo
```

• 2020
• 2019

### Daily Quote

Good artists copy. Great artists steal. -- Pablo Picasso