humanversion9x
Senior Member
Mình thấy bạn làm 2 contest đã lên gần 2k rating và lấy được badge Knight. Không hiểu sao mà đã lo chôn chân ở Knight dài dài.chắc còn phải chôn chân ở knight dài dàicòn lâu mới lên được guardian
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
lovelyly
Senior Member
Đổi x ra một mảng bit, n - 1 ra một mảng bit khác rồi duyệt trên 2 mảng để chèn các bit của mảng bit n-1 vào những bit 0 trên mảng x
TLE_WA
Junior Member
mình nghĩ giải thích như này sẽ dễ hiểu hơn chút
đầu tiên constraint của bài toán là n = 1e8 => ta không thể brute force shift số hiện tại tới khi đạt tới vị trí n được
=> nghĩ theo hướng khác, cụ thể là suy nghĩ xem để đạt tới trạng thái n cần đi qua bao nhiêu phần tử => đi qua n - 1 phần tử
=> phân tích n - 1 để tìm được các vị trí cần add
tìm các vị trí có bit = 0 trong x, vì đây là các ứng viên ta có thể sử dụng, sau đó dựa trên phân tích n - 1 mà ta add với (1 << vị trí tương ứng)
=> nghĩ theo hướng khác, cụ thể là suy nghĩ xem để đạt tới trạng thái n cần đi qua bao nhiêu phần tử => đi qua n - 1 phần tử
=> phân tích n - 1 để tìm được các vị trí cần add
tìm các vị trí có bit = 0 trong x, vì đây là các ứng viên ta có thể sử dụng, sau đó dựa trên phân tích n - 1 mà ta add với (1 << vị trí tương ứng)
Python:
class Solution:
def minEnd(self, n: int, x: int) -> int:
def get_zero_pos(y):
res = []
for i in range(62):
if (1 << i) & x:
continue
res.append(i)
return res
zero_pos = get_zero_pos(x)
def analysis(y):
res = [False] * 62
for i in range(62):
if (1 << i) & y:
res[i] = True
return res
ones = analysis(n-1)
ans = x
for i in range(62):
if ones[i]:
equi = zero_pos[i]
ans += 1 << equi
return ansDạ em cảm ơn ạ, bởi vì nếu mình chỉ thao tác trên mảng toàn bit 0 như này thì chỉ việc cộng 1 với (n-1) lần thôi. Và sau đó thì chèn vị trí bit vừa rồi vào bit 0 của X thì ra kết quả
Sửa lần cuối:
honda stone
Junior Member
Đâu bác, mấy contest gần đây em thọt vl
Em leo lên 1976 qua 4 contest, giờ chắc còn ở đây lâu nữa Đợt này em luyện code bằng js, mà nhiều cái nó ngu/bất tiện quá, chắc phải quay về c++ cho lành.
lovelyly
Senior Member
Ý fen là bài 3 à? Bài đó O(log n) thôi chứ nhỉ, mà t code cứng độ dài mảng bit là 64 nên nó thành O(1)n <= 10^8 giải được bằng O(n) à, ăn cức rồi ae
O(n) thì chắc C/C++ vẫn chạy được
hieunm3538
Senior Member
log(n) mà anh, do mình chuyển x qua binary màn <= 10^8 giải được bằng O(n) à, ăn cức rồi ae
freedom.9
Senior Member
Thấy tụi nó giải O(n) cũng được luôn, mấy nay mải đọc truyện tiên hiệp quá ko học hành gì làm contest toang quá aelog(n) mà anh, do mình chuyển x qua binary mà
Đm đường lên Knight sao lại ngày càng xa thế này
hieunm3538
Senior Member
Contest tuần này khó ý, em thấy Q1 Q2 cũng lắt léo hơn thườngThấy tụi nó giải O(n) cũng được luôn, mấy nay mải đọc truyện tiên hiệp quá ko học hành gì làm contest toang quá ae
Đm đường lên Knight sao lại ngày càng xa thế này
Qua em làm bài 1 bài 2 hết 15 phút + 3 submit fail mà vẫn rank 2k9 ảo thật
honda stone
Junior Member
bài daily hôm nay cũng lại là dùng bit với xor, có điềm gì cho contest cuối tuần này chăng
freedom.9
Senior Member
Bài 3 biweekly dynamic programming bữa trước nay mới đọc lại thấy hay vãi 
nhìn ra việc ko đc đặt quá mấy thằng trùng nhau vượt limit là ngon cmnr
Mấy bài này mà nhìn ra cái trick của nó thì làm lại đơn giản, giờ mới biết lỗi sai ở đâu
via theNEXTvoz for iPhone
nhìn ra việc ko đc đặt quá mấy thằng trùng nhau vượt limit là ngon cmnr Mấy bài này mà nhìn ra cái trick của nó thì làm lại đơn giản, giờ mới biết lỗi sai ở đâu
via theNEXTvoz for iPhone
Đúng r ạ.Đặc biệt đọc solution giải bằng recursion + memo thì càng dễ hiểu, sau đó tự convert lại thành mấy vòng for loop.Bài 3 biweekly dynamic programming bữa trước nay mới đọc lại thấy hay vãi
Mấy bài này mà nhìn ra cái trick của nó thì làm lại đơn giản, giờ mới biết lỗi sai ở đâu
via theNEXTvoz for iPhone
Câu 4 của weekly tuần trước cũng hay, em mới giải lại và giải 1 số bài tương tự
seastar
Member
Phải tối ưu về mem nữa, memo k cẩn thận sẽ bị dính mem limit error.
Dạ, nhưng khi giải đc bằng memo vs recursion thì convert qua dp cũng nhanh ạ.
Mà ở voz làm sao để thả biểu cảm vậy ạ. Em mới xài voz ạ
Hai_hihi
Junior Member
Lên senior member nhé fen
seastar
Member
t nhìn ra cái trick đó mà cũng trầy trật mới pass đc, k dễ ăn đâu.Bài 3 biweekly dynamic programming bữa trước nay mới đọc lại thấy hay vãi
Mấy bài này mà nhìn ra cái trick của nó thì làm lại đơn giản, giờ mới biết lỗi sai ở đâu
via theNEXTvoz for iPhone
.Bài 4 khó phết, dp + prefix sum. Dạng này gặp nhiều nhưng chưa lần nào tự nhìn ra được. Toàn phải vào thảo luận thấy keyword xong mới biết mà giải được,
- Trạng thái
Chủ đề tương tự
