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

seastar đã nói:

code ông này nhìn giống code t phết.

Python:

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        @cache
        def dfs(idx, num_diff):
            if num_diff > k or idx == len(nums):
                return 0
            ret = 1
            for i in range(idx + 1, len(nums)):
                ret = max(ret, 1 + dfs(i, num_diff + int(nums[idx] != nums[i])))
            return ret
        return max(dfs(i, 0) for i in range(len(nums)))

Mà bài 4 làm ntn bị TLE. tối ưu ntn thế?

Nhấp để mở rộng...

class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[0] * n for _ in range(k + 1)]
       
        for diff in range(k + 1):
            posMap = {}
            prefixMax = 0
            for end in range(n):
                dp[diff][end] = 1 + max(
                    prefixMax if k - 1 >= 0 and end - 1 >= 0 else 0,
                    dp[diff][posMap[nums[end]]] if nums[end] in posMap else 0
                )
                prefixMax = max(prefixMax, dp[diff - 1][end] if diff > 0 else 0)
                posMap[nums[end]] = end
       
        return max(dp[k])

maskup đã nói:

Python:

Q4
class Solution:
    def maximumLength(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[0] * n for _ in range(k + 1)]
       
        for diff in range(k + 1):
            posMap = {}
            prefixMax = 0
            for end in range(n):
                dp[diff][end] = 1 + max(
                    prefixMax if k - 1 >= 0 and end - 1 >= 0 else 0,
                    dp[diff][posMap[nums[end]]] if nums[end] in posMap else 0
                )
                prefixMax = max(prefixMax, dp[diff - 1][end] if diff > 0 else 0)
                posMap[nums[end]] = end
       
        return max(dp[k])

Dùng prefix-max của dp và tham lam thôi bác

Nhấp để mở rộng...

freedom.9 đã nói:

Nhưng mà mấy thằng C++ vẫn pass đó fence, nhìn đây

C++:

#define ll long long
int dp[503][503][26];


int find(int pos, int prev, int cnt, vector<int> &nums)
{
    if(pos == nums.size())
        return 0;
   
    int ans = -1;

    if(dp[pos][prev+1][cnt] != -1)
        return dp[pos][prev+1][cnt];
   
    if(prev == -1) // prev = -1 implies the the subsequence has not started
    {
        ans = max(ans, find(pos+1, -1, cnt, nums)); // not starting
        ans = max(ans, 1 + find(pos+1, pos, cnt, nums)); //starting
    }
   
    else
    {
        if(nums[pos] == nums[prev]) // if prev == curr no need to reduce the cnt when adding to subsequence
        {
            ans = max(ans, find(pos+1, prev, cnt, nums));
            ans = max(ans, 1 + find(pos+1, pos, cnt, nums));
        }
       
        else
        {
            ans = max(ans, find(pos+1, prev, cnt, nums));
           
            if(cnt > 0) // make sure cnt > 0 before adding a number not equal to the previous.
                ans = max(ans, 1 + find(pos+1, pos, cnt-1, nums));
        }
   
    }
       
    return dp[pos][prev+1][cnt] = ans;
}


class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
       
        memset(dp, -1, sizeof(dp));
       
        int ans = find(0, -1, k, nums);
        return ans;
    }
};

Nhấp để mở rộng...

seastar đã nói:

C++ nó ăn gian, chơi allocate hết trên stack,

Nhấp để mở rộng...

freedom.9 đã nói:

Toy bị mấy lần bị cái vụ này rồi fence, thôi từ sau cứ theo template mà táng chứ ko chơi kiểu prev, current nữa.

Nhấp để mở rộng...

seastar đã nói:

T cũng từng bị TLE kiểu đó rồi. Xét về độ phức tạp thì nó ổn.
Code hiện tại của fen t chưa xem kỹ lắm. Nhưng theo t nghĩ thì vấn đề nó nằm ở cái cache. Cache như vậy sẽ k hiệu quả. K tin thì fen thử viết thêm 1 đoạn code để tính số lần write, read, hit, miss của cache. So sánh 2 cách là sẽ thấy

Nhấp để mở rộng...

vicejuniordev đã nói:

Thôi mình Brute Force rồi

Nhấp để mở rộng...

vicejuniordev đã nói:

Thôi nghỉ, hóng ae cho ít hint mà có vẻ như cũng bí .

Nhấp để mở rộng...

freedom.9 đã nói:

Q3 sort đã fence, rồi xài DP take not take thôi nhưng mà sẽ bị TLE nên fence ngồi suy nghĩ tiếp

Nhấp để mở rộng...

vicejuniordev đã nói:

À Q3 mình đớp lâu rồi, định lên gài ae xem có ai hint tiện làm Q4 luôn, mà bị ăn gạch luôn

Nhấp để mở rộng...

NudeDuck đã nói:

giải không ra câu 4 dù rất cố gắng

Nhấp để mở rộng...

freedom.9 đã nói:

Ko có ý tưởng gì cả, hay là có cách xài binary search nhỉ

Nhấp để mở rộng...

class Solution:
    def maxTotalReward(self, nums: List[int]) -> int:
        nums.sort()
        dp = 1
        for v in nums:
            x = dp & ((1 << v) - 1)
            dp |= x << v
        return dp.bit_length() - 1

seastar đã nói:

Code của thanh niên Yawn_Sean đây, ảo diệu vkl,

Python:

class Solution:
    def maxTotalReward(self, nums: List[int]) -> int:
        nums.sort()
        dp = 1
        for v in nums:
            x = dp & ((1 << v) - 1)
            dp |= x << v
        return dp.bit_length() - 1

Nhấp để mở rộng...

seastar đã nói:

Code của thanh niên Yawn_Sean đây, ảo diệu vkl,

Python:

class Solution:
    def maxTotalReward(self, nums: List[int]) -> int:
        nums.sort()
        dp = 1
        for v in nums:
            x = dp & ((1 << v) - 1)
            dp |= x << v
        return dp.bit_length() - 1

Nhấp để mở rộng...