Worked a bit on the system design of a new micro service.
New month, new me.
I didn't have an environment to work on competitive programming and others when I was a student, and though it's embarrassing, I sometimes feel jealous of people who could have done this thing in their early days.
Anyway, I better keep going.
Tabulation
def min_removal(s: str) -> int:
dp = [0] * (
n + 1
) # dp[i] will hold the minimum deletions needed to make s[:i] beautiful
for i in range(3, n + 1):
if s[i - 3 : i] in ("pie", "map"):
dp[i] = dp[i - 3] + 1
else:
dp[i] = dp[i - 1] # same as s[:i-1] because s[i] does not increase the number of removals
return dp[n]
for _ in range(int(input())):
n = int(input())
s = input()
print(min_removal(s))I can't fully explain how to replicate this solution. I'll come back later.
The only thing I'm sure is that, dynamic programming is all about finding recurrence relations.
Memoization is intuitive for my brain, but it seems not to be practical, at least in the competitive programming context.
TODO: Consider the tabulation approach
Also, I should remember that the total number of iterations should be below 10 ** 10, perhaps?
20240602: On second thought, the memo is reused for each test case, and the total number of (a, b, c) combinations is 10 ** 6, which should be independent of the total number of test cases 10 ** 5.
"""
(a, b, c) => 100 * 100 * 100 = 10 ** 6
num of testcases => 10 ** 5
10 ** 11 > 10 ** 10 TLE
"""
memo = {}
def possible_results(a: int, b: int, c: int) -> tuple[int, int, int]:
key = f"{a},{b},{c}"
if key in memo:
return memo[key]
if a < 0 or b < 0 or c < 0:
return 0, 0, 0
if a != 0 and b == c == 0:
memo[key] = (1, 0, 0)
return 1, 0, 0
if b != 0 and a == c == 0:
memo[key] = (0, 1, 0)
return 0, 1, 0
if c != 0 and a == b == 0:
memo[key] = (0, 0, 1)
return 0, 0, 1
res = (0, 0, 0)
subres = possible_results(a + 1, b - 1, c - 1)
res = tuple(x | y for x, y in zip(res, subres))
subres = possible_results(a - 1, b + 1, c - 1)
res = tuple(x | y for x, y in zip(res, subres))
subres = possible_results(a - 1, b - 1, c + 1)
res = tuple(x | y for x, y in zip(res, subres))
memo[key] = res
return res
for _ in range(int(input())):
a, b, c = map(int, input().split())Sushi bowl 1000 Teriyaki bowl 1500
Total 2500 kcal
As I get older, it’s getting harder to stop eating, or maybe I'm just stressted out.
TODO: