thảo luận Leetcode contest, đường tới Guardian

Haizz, câu 3 làm hơn 1h mà không ra. Em thấy cũng là flip các bit 0 của X với (n-1) lần thì được nhưng vấn đề là có xen kẽ bit 1 ở giữa nhưng lại không hanlde được
class Solution { public: long long minEnd(int n, int x) { if (n == 1) return x; bool bitZero[32]; int bit[32]; for (int i = 0; i < 32; i++) { if (((1 << i) & x) == 0) { bitZero[i] = true; } } int t = 0; for (int i = 1; i <= n-1; i++) { int numbit = (t > 0) ? static_cast<int>(ceil(log2(t))) : 0; if (bitZero[numbit]) { t = t + 1; } else { t = t + x + (1 << numbit); } } return t + x; } };
 
Câu 4 có tầm 500 người làm được, trong đó không có tôi :D
Câu 3 thì t làm theo ý tưởng thế này:
nums[0] = x
nums[k]: giữ nguyên các bit 1 của x, thay các bit 0 của x thành biểu diễn nhị phân của k

Ví dụ mà Leetcode cho:
Input: n = 3, x = 4
Output: 6
Explanation: nums can be [4,5,6] and its last element is 6.

x biểu diễn theo bit là 0100
0 = 0b000 => nums[0] biểu diễn theo bit: 0100
1 = 0b001 => nums[1] biểu diễn theo bit: 0101
2 = 0b010 => nums[2] biểu diễn theo bit: 0110
Em cũng nhận thấy tính chất như này, nhưng lúc cài đặt không handle được do có bit 1 xen kẽ
 
Em cũng nhận thấy tính chất như này, nhưng lúc cài đặt không handle được do có bit 1 xen kẽ
em đặt y = n - 1
duyệt các bit từ bit 0 trở đi
nếu có bit i nào của x bằng 1, thì gán bit i của y cũng bằng 1, tất cả các bit ở trước (i + 1 đến ...) thì dịch sang trái
 
Em cũng nhận thấy tính chất như này, nhưng lúc cài đặt không handle được do có bit 1 xen kẽ
Đổ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
 
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)
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 ans
 
Đổ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
Dạ 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ả
 
Last edited:
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.
Đâ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.
 
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á ae =((
Đm đường lên Knight sao lại ngày càng xa thế này =((
Contest tuần này khó ý, em thấy Q1 Q2 cũng lắt léo hơn thường :LOL: 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
 
Câu daily hôm nay cũng bit manipulation, nhưng làm bài hôm qua rồi thì bài hôm nay cài đặt theo hướng dùng mảng để đếm bit như bài hôm qua thì nó cũng dễ, mặc dù các idol khác thì chỉ cần vài line vớ phép xor là ra
 
Câu daily hôm nay cũng bit manipulation, nhưng làm bài hôm qua rồi thì bài hôm nay cài đặt theo hướng dùng mảng để đếm bit như bài hôm qua thì nó cũng dễ, mặc dù các idol khác thì chỉ cần vài line vớ phép xor là ra
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 :cautious:
 
Bài 3 biweekly dynamic programming bữa trước nay mới đọc lại thấy hay vãi :ah: nhìn ra việc ko đc đặt quá mấy thằng trùng nhau vượt limit là ngon cmnr :ah:
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 :too_sad:
via theNEXTvoz for iPhone
 
Back
Top