thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
athxzz
Senior Member
34 thì chắc cũng rank 1k mà bác cũng bị trừ rating à :v q4 nay khoai chắc ít all killed lắm
thangkc89
Senior Member
e guardian rồi bác, 1k là giữ hạng thôi, chứ hơn 1k là bị trừ rating
Bài này nếu mà chỉ cần chọn 1 số x thôi thì dễ vl, thêm cái (x,y) nữa khó quá. E có ý tưởng trong đầu là BS số k rồi những số -1 sẽ tìm được cái acceptance_interval từ 2 số khác -1 gần nhất bên trái và phải -> bài toán lúc này là làm sao chọn đc 2 số x, y và assign vào mỗi đoạn. Khó vl chưa nghĩ ra
P/s: e cảm giác như chỉ cần sort lại rồi tham lam thôi không biết đúng không
Sửa lần cuối:
Husqvarna701SM
Senior Member
hehe sau 1 tháng bắt đầu biết tới contest lần đầu dc 3 bài
seichan502
Member
Hôm nay lần đầu làm được 2 bài, bài 1 ăn 3 bọ 
, mong tháng sau lên được 3 bài.
, mong tháng sau lên được 3 bài.
freedom.9
Senior Member
Q1 đúng khắm lọ, Q2 thì mình cắm đầu xài segment tree ngu thật
athxzz
Senior Member
hiểu biết sâu rộng dễ nghĩ ra mấy cách làm phức tạp đấy bácQ1 đúng khắm lọ, Q2 thì mình cắm đầu xài segment tree ngu thật
seichan502
Member
Q2 lúc đầu e cũng định dùng segment tree mà quên cách implement nên dùng đại line sweep, không biết có cách nào O(n) không.Q1 đúng khắm lọ, Q2 thì mình cắm đầu xài segment tree ngu thật
freedom.9
Senior Member
Mình thì nghĩ sẽ tính nếu như nums i == -1 thì nó sẽ contribute vô 2 đoạn, 1 là phía trái thì diff sẽ là x - nums[i - 1], phải thì sẽ là nums[i + 1] - xe guardian rồi bác, 1k là giữ hạng thôi, chứ hơn 1k là bị trừ rating
Bài này nếu mà chỉ cần chọn 1 số x thôi thì dễ vl, thêm cái (x,y) nữa khó quá. E có ý tưởng trong đầu là BS số k rồi những số -1 sẽ tìm được cái acceptance_interval từ 2 số khác -1 gần nhất bên trái và phải -> bài toán lúc này là làm sao chọn đc 2 số x, y và assign vào mỗi đoạn. Khó vl chưa nghĩ ra
P/s: e cảm giác như chỉ cần sort lại rồi tham lam thôi không biết đúng không
Nếu có 1 số x và y để thoả mãn target thì sẽ phải là min(nums[i - 1]) + target và max(nums[i + 1) - target rồi sau đó double check lại bằng cách chọn 1 trong 2 số bất kì đi từ trái qua phải.
Mà éo biết cái logic này nó sai ở đâu đang debug lại, hên là đang dùng clone thi nên ko áp lực lắm
đang train đầu năm sau đem acc chính đấm nhauTinh Hoa Đông Lào
Junior Member
Q3 có cách giải segment tree k bác, e giải Q3 segment tree bị TLEQ1 đúng khắm lọ, Q2 thì mình cắm đầu xài segment tree ngu thật
athxzz
Senior Member
Q3 có cách giải segment tree k bác, e giải Q3 segment tree bị TLE
q3 bác chơi line sweep với BS cho đơn giản
Q4 chắc xài Binary search để tìm điểm minimum trong đoạn A, B. sao cho f(C - 1) >= f(C) và f(C) <= f(C + 1)
Không có time để implement do bận con mọn
- Tìm hết các đoạn a -1 b, a -1 -1 b, -1 a, b - 1 gọi ==> x, y phải nằm trong min(a), max(b)
- Tìm với x chạy từ min(a), tới max(b), rồi lại với mỗi x tìm y từ x đến max(b), nếu có cặp a -1 ... -1 b thì add thêm |y - x| cũng là một giá trị.
Không có time để implement do bận con mọn
Husqvarna701SM
Senior Member
Tạo 1 arrays n+1, Với mỗi cặp điểm trong queries thím + giá trị val tại điểm bắt đầu queries và - val tại điểm kết thúc queries +1 rồi dùng prefixSum là tính dc số lần bớt tối đa tại 1 điểm á. Q3 thì thêm binary search là dc
freedom.9
Senior Member
Ko bác, ko giải segment tree được vì là range update xong rồi phải tính sum toàn bộ bằng range query và loại bỏ thằng nào < -1 nên chắc chắn TLE. Q2 mình đâm đầu vô segment tree mà quên mẹ mất là cái giá trị dưới 0 thì tính sum chết mẹ nó mất ko loại trừ đượcQ3 có cách giải segment tree k bác, e giải Q3 segment tree bị TLE
Q2 thực ra là giải đc segment tree nhưng mà mình quên mẹ mất ko loop từng thằng mà tính sum đúng ngu mất mẹ 20ph cuộc đời
do mình xài clone nên múa múa tí cũng thoải mái.
Python:
class SegmentTree:
def __init__(self, nums):
n = len(nums)
self.n = n
self.tree = [0]*n + nums
for i in range(n - 1, -1, -1):
self.tree[i] = self.tree[i*2] + self.tree[i*2 + 1]
def update(self, index, val):
index += self.n
if index >= len(self.tree):
return
self.tree[index] += val
while index > 1:
index //= 2
self.tree[index] = self.tree[index*2] + self.tree[index*2 + 1]
def query(self, index):
left = self.n
right = index + self.n + 1
ans = 0
while left < right:
if left & 1:
ans += self.tree[left]
left += 1
if right & 1:
right -= 1
ans += self.tree[right]
left//=2
right//=2
return ans
class Solution:
def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
n = len(nums)
diff = [0]*n
diff[0] = nums[0]
for i in range(1, n):
diff[i] = nums[i] - nums[i - 1]
seg = SegmentTree(diff)
for left, right in queries:
seg.update(left, -1)
seg.update(right + 1, +1)
sumSofar = 0
for i in range(n):
if seg.query(i) > 0:
return False
return TrueTinh Hoa Đông Lào
Junior Member
Q3 giải được bằng line sweep á, tại mình nghĩ cái thuật toán này cần sort range, mà đề yêu cầu queries in sequence nên ko theo hướng này
freedom.9
Senior Member
Ko cần chạy từ min a tới max b mà chỉ cần dùng 2 cận đó thôi bác, em code gần ra rồi mà thời gian rush quáQ4 chắc xài Binary search để tìm điểm minimum trong đoạn A, B. sao cho f(C - 1) >= f(C) và f(C) <= f(C + 1)
==> TC = N * log(max(b) - max(a)) * log(max(b) - max(a))
- Tìm hết các đoạn a -1 b, a -1 -1 b, -1 a, b - 1 gọi ==> x, y phải nằm trong min(a), max(b)
- Tìm với x chạy từ min(a), tới max(b), rồi lại với mỗi x tìm y từ x đến max(b), nếu có cặp a -1 ... -1 b thì add thêm |y - x| cũng là một giá trị.
Không có time để implement do bận con mọn
Nice, xong còn xử lý edge cases nữa. bài 8 điểm thường là Hard Algo + Hard implementation.
freedom.9
Senior Member
Line sweep thì thường ko cần phải sort mà nếu constrain thấp thì bác có thể brute force từ 0 -> 10**5 được mà, nếu 10**9 là max number ở trong lines thì mới cần sortQ3 giải được bằng line sweep á, tại mình nghĩ cái thuật toán này cần sort range, mà đề yêu cầu queries in sequence nên ko theo hướng này
Có ý tưởng mà code ko ra nó thốn, thấy bài 8 điểm là té đái cmnr. Mấy thằng top code cũng gần giống ý tưởng của mình
- Trạng thái
Chủ đề tương tự
