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

SchindlerRoman · 12/10/24

lilleboybk đã nói:
Q4 thuần về toán nhỉ các bác, ngồi nghĩ mà lú quá.

Đọc nhớ mấy bài đếm đếm thời cấp 3 =))

nahnahinin · 12/10/24

q4 thuần toán, nháp 40ph mới xong. sợ thật, đi làm ko động toán bố ai nhớ được///

C++:

#define i64 long long
class Solution {
   
public:
    long long p(long long a, long long b, long long c) {
        long long result = 1;
        a = a % c;
        while (b > 0) {
            if (b % 2 == 1) {
                result = (result * a) % c;
            }
            b = b >> 1;
            a = (a * a) % c;
        }
        return result;
    }
    int numberOfWays(int n, int x, int y) {
        i64 mod=1e9+7;
        vector<vector<i64>> dp(x + 1, vector<i64>(x + 1, 0));
        for (int i = 0; i <= x; i++) {
            dp[i][0] = 1;
            if (i <= x) { dp[i][i] = 1; }
        }
        for (int i = 0; i <= x; i++) {
            for (int j = 1; j <= min(i, x); j++) {
                if (i != j) {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
                }
            }
        }
        vector<vector<i64>> S(n+1, vector<i64>(n+1, 0));
        S[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(i, n); ++j) {
                S[i][j] = ((j * S[i - 1][j])%mod + S[i - 1][j - 1]) %mod;
            }
        }
        int res=0;
        vector<i64>gt(x+1,1);
        for(int i=1;i<=x;i++) gt[i]=(gt[i-1]*i)%mod;
        for(int i=0;i<x;i++){
            if(x-i>n) continue;
            i64 k=dp[x][x-i];
            k=(k*gt[x-i])%mod;
            k=(k*S[n][x-i])%mod;
            k=k*p(y,x-i,mod);
            k%=mod;
            res+=k;
            res%=mod;
        }
        return res;
    }
};

nahnahinin · 12/10/24

nahnahinin đã nói:

q4 thuần toán, nháp 40ph mới xong. sợ thật, đi làm ko động toán bố ai nhớ được///

C++:

#define i64 long long
class Solution {
  
public:
    long long p(long long a, long long b, long long c) {
        long long result = 1;
        a = a % c;
        while (b > 0) {
            if (b % 2 == 1) {
                result = (result * a) % c;
            }
            b = b >> 1;
            a = (a * a) % c;
        }
        return result;
    }
    int numberOfWays(int n, int x, int y) {
        i64 mod=1e9+7;
        vector<vector<i64>> dp(x + 1, vector<i64>(x + 1, 0));
        for (int i = 0; i <= x; i++) {
            dp[i][0] = 1;
            if (i <= x) { dp[i][i] = 1; }
        }
        for (int i = 0; i <= x; i++) {
            for (int j = 1; j <= min(i, x); j++) {
                if (i != j) {
                    dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % mod;
                }
            }
        }
        vector<vector<i64>> S(n+1, vector<i64>(n+1, 0));
        S[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= min(i, n); ++j) {
                S[i][j] = ((j * S[i - 1][j])%mod + S[i - 1][j - 1]) %mod;
            }
        }
        int res=0;
        vector<i64>gt(x+1,1);
        for(int i=1;i<=x;i++) gt[i]=(gt[i-1]*i)%mod;
        for(int i=0;i<x;i++){
            if(x-i>n) continue;
            i64 k=dp[x][x-i];
            k=(k*gt[x-i])%mod;
            k=(k*S[n][x-i])%mod;
            k=k*p(y,x-i,mod);
            k%=mod;
            res+=k;
            res%=mod;
        }
        return res;
    }
};

số cách lấy n người đưa vào b group * b giai thừa * tổ hợp (b,x) * y^b
bác nào có công thức gọn hơn ko

lilleboybk · 12/10/24

nahnahinin đã nói:
số cách lấy n người đưa vào b group * b giai thừa * tổ hợp (b,x) * y^b
bác nào có công thức gọn hơn ko

Khéo mấy bác kia giải được 1Q đi ngủ hết rồi bác.

freedom.9 · 12/10/24

Dạo gần đây đọc tiên hiệp dữ quá làm Medium trầy trật thật, thôi luyện tập 1 tháng nữa trở lại contests :ah:

via theNEXTvoz for iPhone

lilleboybk · 12/10/24

Sợ gì bác, em giải 3Q vẫn bị trừ rank mà mai vẫn thi contest này.

lilleboybk · 13/10/24

lilleboybk đã nói:
Chúc mừng bác nhé, bác đứng trước cửa danh hiệu Guardian rồi ấy. Bác mà làm 2 contest tới cũng "bay" như này là lên Guardian thôi.

Em chúc "thiêng" thật, 2 contest vừa rồi bác chủ thớt thấy làm cũng "bay", mà là bay mấy chục điểm

nahnahinin · 13/10/24

de hon hom qua nhi, hom qua q4 khoai vc

freedom.9 · 13/10/24

lilleboybk đã nói:
Em chúc "thiêng" thật, 2 contest vừa rồi bác chủ thớt thấy làm cũng "bay", mà là bay mấy chục điểm

Bay thật chứ, mà trình chưa tới nên phục thù sau :ah:

mấy nay mình random làm medium còn trầy trật thì sao lên nổi, nay làm ổn ko fence.
Mà đề gần đây phân loại dữ quá, tụi nó cheat có vẻ cũng nhiều top toàn thấy AI ko =((

callmemark · 13/10/24

Q4 nghĩ ra đc idea sài sortedlist nhưng lại kg đủ time :/

NguyenQUy1801 · 13/10/24

Mấy bác cho em hỏi câu 3 như này sao lại TLE nhỉ :

lilleboybk · 13/10/24

freedom.9 đã nói:
Bay thật chứ, mà trình chưa tới nên phục thù sau mấy nay mình random làm medium còn trầy trật thì sao lên nổi, nay làm ổn ko fence.
Mà đề gần đây phân loại dữ quá, tụi nó cheat có vẻ cũng nhiều top toàn thấy AI ko

Nay em cũng 3Q như hôm qua thôi bác, được cái rank cao hơn hôm qua do Q4 ít người làm được.

lilleboybk · 13/10/24

NguyenQUy1801 đã nói:
Mấy bác cho em hỏi câu 3 như này sao lại TLE nhỉ :
Xem tệp đính kèm 2731138

Em cũng TLE Q3, xong thêm cái điều kiện giống bác là chỉ xét các score mà đảm bảo đến cuối Bob vẫn win thôi là Accepted. Nhưng em ko dùng đệ quy mà dùng for-loop.

NguyenQUy1801 · 13/10/24

lilleboybk đã nói:
Em cũng TLE Q3, xong thêm cái điều kiện giống bác là chỉ xét các score mà đảm bảo đến cuối Bob vẫn win thôi là Accepted.

lúc đầu e cũng thêm đk như v mà k ra đúng nên mới đổi lại là thấy Bob thua thì nghỉ k chạy nữa =))

nhưng mà k hiểu sao có ông làm chả cần đk gì vẫn accept :V

clonemasteruwu · 13/10/24

NguyenQUy1801 đã nói:
Mấy bác cho em hỏi câu 3 như này sao lại TLE nhỉ :
Xem tệp đính kèm 2731138

pass string = copy

NguyenQUy1801 · 13/10/24

clonemasteruwu đã nói:
pass string = copy

ặc bảo sao, thanks bác giờ mới nhớ cái này =((

Tinh Hoa Đông Lào · 13/10/24

Python:

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        result = []
        freq = defaultdict(int)

        for i in range(k):
            freq[nums[i]] += 1
      
        def compute_top_x_sum(freq, x):
            heap = [(count, num) for num, count in freq.items()]
            top_x = nlargest(x, heap)
            return sum(freq * value for freq, value in top_x)

        result.append(compute_top_x_sum(freq, x))

        for i in range(k,n):
            freq[nums[i]] += 1
            freq[nums[i-k]] -= 1

            if freq[nums[i-k]] == 0:
                del freq[nums[i-k]]

            result.append(compute_top_x_sum(freq, x))
        return result

mn cho hỏi sao tính thấy độ phức tạp là N^2LOGN vẫn bị LTE nhỉ ở Q4

freedom.9 · 14/10/24

Tính ra contest weekly bữa trước dễ nhỉ, làm chưa tới 40 phút đc 3Q cmnr :ah:

Cái contest biweekly cũng dễ nữa mà bữa trước trigger bài 2 quá, bay mẹ mất mấy chục điểm :ah:

Python:

class Solution:
    def maxRemovals(self, source: str, pattern: str, targetIndices: List[int]) -> int:
        n = len(source)
        m = len(pattern)
        indicies = set(targetIndices)
        cache = [0]*n
        toBeRemoved = 0
        for i in range(n - 1, -1 ,-1):
            toBeRemoved += int(i in indicies)
            cache[i] += toBeRemoved

        #source, pattern
        @lru_cache(None)
        def dp(i, j):
            if i == n:
                if j == m:
                    return 0
                else:
                    return -inf
            if j == m:
                return cache[i]

            ans = -inf

            if i in indicies:
                ans = max(ans, 1 + dp(i + 1, j))
    
            if source[i] == pattern[j]:
                ans = max(ans, dp(i + 1, j + 1))
            else:
                ans = max(ans, dp(i + 1, j))

            return ans

        return dp(0, 0)

Python:

class Solution:
    def countWinningSequences(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        sArray = [0]*n
        for i, val in enumerate(s):
            if val == 'W':
                sArray[i] = 1
            elif val == 'E':
                sArray[i] = 2
        
        @lru_cache(None, False)
        def dfs(i, last, diff):
            if diff < 0 and n - i <= abs(diff):
                return 0

            if i == n:
                if diff > 0:
                    return 1
                else:
                    return 0
            
            # F, W, E
            moves = [0, 1, 2]
            ans = 0
            for move in moves:
                if move == last:
                    continue

                if move == sArray[i]:
                    ans += dfs(i + 1, move, diff)

                elif move == 0 and sArray[i] == 2:
                    ans += dfs(i + 1, move, diff + 1)
                
                elif move == 1 and sArray[i] == 0:
                    ans += dfs(i + 1, move, diff + 1)

                elif move == 2 and sArray[i] == 1:
                    ans += dfs(i + 1, move, diff + 1)
                else:
                    ans += dfs(i + 1, move, diff - 1)

            return ans%mod
        
        return dfs(0, -1, 0)

freedom.9 · 14/10/24

Tinh Hoa Đông Lào đã nói:
return sum(freq * value for freq, value in top_x)

Cái này fence tính như này là On^2 rồi mà, TLE là đúng. Phải có cách tính O(nlogn) ấy
Mình nghĩ phải có cách tính O n log n

Violet_7 · 20/10/24

box này trôi lạc thế. Nay đọc sai đề câu 3, mất mẹ 20 phút xàm lờ :sweat:

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

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này