[
dfs
math
backtracking
]
Leetcode 1807. Evaluate the Bracket Pairs of a String
Problem statement
https://leetcode.com/problems/maximum-number-of-groups-getting-fresh-donuts/
Solution
Quite difficult problem, we need to read problem restriction carefully to suceed. We can notice, that B <= 9
and this is the main point we will use.
- Let us first understand, what our problem is about. We have bunch of nubmers and we need to make them in special order, such that as much groups are divisible by
B
. Notice, that what matters, is not elementg in groups
, but in factg % B
. - Now, we have elements in groups be numbers from
0
toB-1
. Notice, that if we have element0
, than this group is always happy, so no need to consider it: remove it and add1
to final answer. Also, notice, that if we have two elements, which giveB
in total, if we put them one after another, we will make happy group as well. - Let us call
position
how many of each reminders we have, for example for case[1, 2, 3, 3, 4, 5, 5, 5]
andB = 4
, we have[4,1,2]
, because we have4
numbers with reminder1
,1
number with reminder2
and2
numbers with reminder3
. - It is time now to use
dfs(position, last)
, whereposition
is what we discussed earlier andlast
is last number in our sequence. Where we can go from this position: we try to decrease one of the elements ofposition
by one and run function recursively: we add1
(usingU == 0
), if we make one more group happy. - In the end we just run our
dfs
from positions we created.
Complexity
We have at most O(K)
, where K = B//2
non-zero elements in group and sum of all elements in groups is restricted by n
. So we have no more than (n/K)^K
possible positions here, which given problem restriction is quite small, so total time complexity is O((n/K)^K*K)
, because we can have upto K
transitions from one state to others. Space complexity is the same.
Code
class Solution:
def maxHappyGroups(self, B, groups):
ans = sum(g%B == 0 for g in groups)
groups = [g for g in groups if g%B != 0]
pos = [0]*(B-1)
for g in groups: pos[g%B - 1] += 1
for i in range(B-1):
t = min(pos[i], pos[B-i-2]) if 2*i != B - 2 else pos[i]//2
ans += t
pos[i] -= t
pos[B-i-2] -= t
if sum(pos) == 0: return ans
@lru_cache(None)
def dfs(position, last):
if sum(position) == 0: return 0
ans = float("-inf")
for i in range(B - 1):
if position[i] > 0:
t = [j for j in position]
t[i] -= 1
U = (last - (i + 1)) % B
ans = max(ans, dfs(tuple(t), U) + (U == 0))
return ans
return max(dfs(tuple(pos), i) for i in range(1, B)) + ans
If you like the solution, you can upvote it on leetcode discussion section: Problem 1815