Tamagotchi got popular among Japanese software developers because the Tamagotchi team released a blog about how they use AWS to build the complex system.
I browsed the Tamagotchi website today and found that there is a web page to list OSS they use. It's rare that a project for children discloses such technical details.
I'm considering ordering one for myself. It's not that expensive ($59 before tax).
I cannot simply use memoization because it involves string manipulations.
For example,
memo = {}
def min_removal(s: str) -> int:
if s in memo:
return memo[s]
if "pie" not in s and "map" not in s:
memo[s] = 0
return 0
res = 10 ** 7
for i in range(len(s)):
res = min(res, min_removal(s[:i] + s[i+1:]) + 1)
memo[s] = res
return res
for _ in range(int(input())):
n = int(input())
s = input()
print(min_removal(s))if the length of the input string s is n, the creation of a substring s[:i] + s[i+1:] costs O(n), making the total time complexity ~= O(n^2)? which is not suitable for the constraints of this problem.
I'll try to come up with a tabulation solution tomorrow.
Cheat day
Total ???? kcal
TODO: