em đái ra máu luôn bác :vCũng tại cơm áo gạo tiền, thấy mấy thằng khác giải nhanh quá mà nhìn ra cái trick kia nên chạy đi search solution, đoán kiểu gì cũng có sẵn trên google
Gặp bài 3 constructive programming nhìn là thấy đái ra quần rồighét mấy bài phong cách codeforces này quá
:v ai cho em xin Q3 với, gap quá, làm không, không nhìn ra được cách chọn
class Solution:
def generateSchedule(self, n: int) -> List[List[int]]:
if n <= 4:
return []
schedule = []
for phase in range (1,n):
played_home_matches = [False] * n
remaining_matches = n
home_team = 0
while (remaining_matches > 0):
if played_home_matches[home_team] == False:
away_team = (home_team + phase) % n
if len(schedule) == 0 or (home_team not in schedule[-1] and away_team not in schedule[-1]):
schedule.append([home_team, away_team])
played_home_matches[home_team] = True
remaining_matches -= 1
home_team = (home_team + 1) % n
return schedule
3Q còn lại solved!
Chưa update kịp thôi bác
Q3 e thử DP mà fail từ test 200Q3 quá dễ đi mà làm ẩu thật, đọc lộn đề nữa chứ cay quá
class Solution:
def subsequenceSumAfterCapping(self, nums: List[int], k: int) -> List[bool]:
n = len(nums)
c = Counter(nums)
res = [False] * n
a = [False] * (k + 1)
a[0] = True
s = n
for x in range(1, n + 1):
t = s
temp = False
for s in range(k + 1):
if a[s] and k - s >= 0 and (k - s) % x == 0 and (k - s) // x <= t:
temp = True
break
res[x - 1] = temp
s -= c.get(x, 0)
if c.get(x, 0) > 0:
for _ in range(c.get(x, 0)):
for s in range(k, x - 1, -1):
a[s] = a[s] or a[s - x]
return res
Bài này dễ thôi fen, brute force từ 0 đến n-1 cho mỗi answer, với mỗi số x thì sẽ phải capitalize tất cả số lớn hơn hoặc bằng x, dùng bisect để tìm tổng số num lớn hơn và bằng x.Q3 e thử DP mà fail từ test 200
cao nhân đây có hướng giải khác ko ạ?Python:class Solution: def subsequenceSumAfterCapping(self, nums: List[int], k: int) -> List[bool]: n = len(nums) c = Counter(nums) res = [False] * n a = [False] * (k + 1) a[0] = True s = n for x in range(1, n + 1): t = s temp = False for s in range(k + 1): if a[s] and k - s >= 0 and (k - s) % x == 0 and (k - s) // x <= t: temp = True break res[x - 1] = temp s -= c.get(x, 0) if c.get(x, 0) > 0: for _ in range(c.get(x, 0)): for s in range(k, x - 1, -1): a[s] = a[s] or a[s - x] return res
Ồ nhưng mà solution của mình hình như n^2k mà sao vẫn pass nhỉ?Bài này dễ thôi fen, brute force từ 0 đến n-1 cho mỗi answer, với mỗi số x thì sẽ phải capitalize tất cả số lớn hơn hoặc bằng x, dùng bisect để tìm tổng số num lớn hơn và bằng x.
Vì tổng của element phải bằng K, nên nếu mình có 1 possible sum thì phần còn lại remaining là k - possible sum, thì cái phần thừa này nó phải chia hết cho x và nhỏ hơn hoặc bằng số elements >= x thì mình sẽ chọn 1 cái sum thỏa mãn.
Fen xem solution của mình ở đây, làm ko ra trong contest mà bài thì quá dễ, trong contest tâm lí hơi yếu
Subsequence Sum After Capping Elements - LeetCode
Can you solve this real interview question? Subsequence Sum After Capping Elements - You are given an integer array nums of size n and a positive integer k. An array capped by value x is obtained by replacing every element nums[i] with min(nums[i], x). For each integer x from 1 to n, determine...leetcode.com
Q3 nay khó mà bác, accepted ít hơn cả Q4Bài này dễ thôi fen, brute force từ 0 đến n-1 cho mỗi answer, với mỗi số x thì sẽ phải capitalize tất cả số lớn hơn hoặc bằng x, dùng bisect để tìm tổng số num lớn hơn và bằng x.
Vì tổng của element phải bằng K, nên nếu mình có 1 possible sum thì phần còn lại remaining là k - possible sum, thì cái phần thừa này nó phải chia hết cho x và nhỏ hơn hoặc bằng số elements >= x thì mình sẽ chọn 1 cái sum thỏa mãn.
Fen xem solution của mình ở đây, làm ko ra trong contest mà bài thì quá dễ, trong contest tâm lí hơi yếu
Subsequence Sum After Capping Elements - LeetCode
Can you solve this real interview question? Subsequence Sum After Capping Elements - You are given an integer array nums of size n and a positive integer k. An array capped by value x is obtained by replacing every element nums[i] with min(nums[i], x). For each integer x from 1 to n, determine...leetcode.com
tôi cũng dùng DP.Q3 e thử DP mà fail từ test 200
cao nhân đây có hướng giải khác ko ạ?Python:class Solution: def subsequenceSumAfterCapping(self, nums: List[int], k: int) -> List[bool]: n = len(nums) c = Counter(nums) res = [False] * n a = [False] * (k + 1) a[0] = True s = n for x in range(1, n + 1): t = s temp = False for s in range(k + 1): if a[s] and k - s >= 0 and (k - s) % x == 0 and (k - s) // x <= t: temp = True break res[x - 1] = temp s -= c.get(x, 0) if c.get(x, 0) > 0: for _ in range(c.get(x, 0)): for s in range(k, x - 1, -1): a[s] = a[s] or a[s - x] return res
class Solution
{
public:
vector<bool> subsequenceSumAfterCapping(vector<int> &a, int k)
{
sort(a.begin(), a.end());
int n = a.size();
vector<bool> dp(k + 1, false);
dp[0] = true;
vector<bool> ans(n, false);
int j = 0;
for (int i = 1; i <= n; ++i)
{
while (j < n && a[j] <= i)
{
for (int t = k; t - a[j] >= 0; t--)
{
if (dp[t - a[j]])
{
dp[t] = true;
}
}
j++;
}
if (dp[k])
{
ans[i - 1] = true;
continue;
}
for (int t = 0; j + t <= n && k - t * i >= 0; t++)
{
if (dp[k - t * i])
{
ans[i - 1] = true;
break;
}
}
}
return ans;
}
};Mình dùng DP + Bit + Early Exist may là vẫn qua :v
class Solution:
def subsequenceSumAfterCapping(self, nums: List[int], k: int) -> List[bool]:
n = len(nums)
nums.sort()
res = []
for i in range(n):
x = i + 1
curr = 1
flag = False
if min(nums[0], x) > k:
break
for num in nums:
if num > x:
num = x
curr |= curr << num
curr |= 1
if curr & (1 << k):
res.append(True)
flag = True
break
if not flag:
res.append(False)
if len(res) < n:
res = res + [False] * (n - len(res))
return res
