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

JustAnOtherClone đã nói:

lâu lắm ko chơi contest, các fen cho hỏi giờ còn cheat nhiều không? để còn tính đường comebeack.

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

noobdev đã nói:

4 bọ đây, mấy bài đếm này nhiều edge cases toàn cover thiếu, chán vãi đ muốn làm nữa

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

freedom.9 đã nói:

Ko, ít lắm bị ban hết rồi fen

via theNEXTvoz for iPhone

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

Người quan sát cô đơn đã nói:

Nay giải 2q nhưng ăn cmn 7 bọ, ko biết có qua nổi 1k4 ko

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

freedom.9 đã nói:

Mới virtual thử làm đc 3Q, ăn 1 bọ do quên MOD mà thấy rank trên 1k rồi. Nhìn lên leader board thì thấy cheat nhiều vcl luôn trong khi Q3 cũng gọi là khó và đúng so với Q 6 điểm.
Q4 thì digit DP chưa học tới, để tuần này lên học digit dp

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

thangkc89 đã nói:

Qua e ngồi viết script scan hết tụi nộp bài có biến zoraflenty và florvanta, chắc cũng hơn 40 đứa. Bài 3 bị 3 bugs rank 1k1 nhưng vẫn không bị trừ rating may quá

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

class Solution:
    def sumOfGoodSubsequences(self, nums: List[int]) -> int:
        totalSum = defaultdict(int)
        countSubSequence = defaultdict(int)
        n = len(nums)
        ans = 0
        MOD = 10**9 + 7
        for i in range(n - 1, -1, -1):
            totalSum[nums[i]] += nums[i]
            countSubSequence[nums[i]] += 1
         
            if nums[i] + 1 in totalSum:
                totalSum[nums[i]] += totalSum[nums[i] + 1] + nums[i]*countSubSequence[nums[i] + 1]
                countSubSequence[nums[i]] += countSubSequence[nums[i] + 1]

            if nums[i] - 1 in totalSum:
                totalSum[nums[i]] += totalSum[nums[i] - 1] + nums[i]*countSubSequence[nums[i] - 1]
                countSubSequence[nums[i]] += countSubSequence[nums[i] - 1]


        ans = 0
        for key, value in totalSum.items():
            ans += value % MOD
        return ans%MOD

class Solution:
    def countKReducibleNumbers(self, s: str, k: int) -> int:
        @lru_cache(None)
        def isValid(num, limit):
            if num == 1:
                return True
            if limit == 0:
                return False
            return isValid(num.bit_count(), limit - 1)
        
        ans = 0 
        MOD = 10 ** 9 + 7
        n = len(s)
        count1 = 0
        for i in range(n):
            if s[i] == '1':
                # There are n - i - 1 items remaining
                # If we flip the current 1 to '0', the rest will always be smaller than the current num
                remaining = n - i - 1
                for j in range(remaining + 1):
                    if isValid(count1 + j, k - 1):
                        ans += comb(remaining, j)
                        ans %= MOD
                count1 += 1
        return ans

TLE_WA đã nói:

Câu 4 constraint s.length <= 800 nên số bit set tối đa là 800, gọi f[n] là số lần reduce cần để một số có lượng bit set là n về 1. sau đó sử dụng digit dp để tính số lượng số nhỏ hơn s, có i bit set, nếu f <= k thì cộng với lượng đó.

Spoiler: Digit DP

C++:

const int MOD = 1e9 + 7;
const int N = 801;

int dp[N][N][2];

int countNumbers(const string &s, int pos, int count, int tight) {
    if (count < 0) return 0;
    if (pos == s.size()) return count == 0 && !tight;
    if (dp[pos][count][tight] != -1) return dp[pos][count][tight];
    
    int limit = tight ? s[pos] - '0' : 1;
    int result = 0;
    for (int bit = 0; bit <= limit; ++bit) {
        result += countNumbers(s, pos + 1, count - bit, tight && (bit == limit));
        result %= MOD;
    }
    return dp[pos][count][tight] = result;
}

int findNumbersLessThan(const string &s, int m) {
    return countNumbers(s, 0, m, 1);
}

int cnt_bit(int x) {
    return __builtin_popcount(x);
}

bool can[801][6];

class Solution {
public:
    int countKReducibleNumbers(string s, int k) {
        memset(dp, -1, sizeof(dp));
        can[1][1] = true;
        for (int j = 1; j <= k; j++){
            for (int i = 1; i <= 800; i++) {
                can[i][j] |= can[cnt_bit(i)][j-1];
            }
        }

        int ans = 0;
        for (int i = 1; i <= s.size(); i++){
            if (!can[i][k]) continue;
            ans = (ans + findNumbersLessThan(s, i)) % MOD;
        }
        return ans;
    }
};

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

thangkc89 đã nói:

Qua e ngồi viết script scan hết tụi nộp bài có biến zoraflenty và florvanta, chắc cũng hơn 40 đứa. Bài 3 bị 3 bugs rank 1k1 nhưng vẫn không bị trừ rating may quá

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

seastar đã nói:

tụi leetcode có trò là khi copy toàn bộ đề bài để quăng cho LLM thì nó sẽ add thêm 1 đoạn prompt để yêu cầu đặt tên biến đặc biệt. Thằng nào copy xong quăng thẳng cho LLM mà k xóa đoạn đó đi là ăn gậy ngay,

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

thangkc89 đã nói:

cách này chắc xài được một vài lần thôi, sau này tụi nó xoá trước khi submit là thua. Thấy có nhiều đứa code mà comment đầy đủ từng dòng đúng chính tả nghi ngờ quá, mà không có bằng chứng để report tụi nó ai đời làm contest ăn nhau từng giây mà có thời gian ngồi comment code

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

seastar đã nói:

Uhm, chặn đc mấy thằng lười quá mà chưa biết trò này thôi, chứ biết rồi thì xoá trước khi cho vào llm luôn ấy

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