thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

freedom.9

Senior Member

• 21/9/25

• #921

Đm q4 sao mà khó thế ko biết mẹ đang nhiều thời gian mà gặp ngay câu 7 điểm ngọng quá

 

freedom.9

Senior Member

• 21/9/25

• #922

Bỏ cuộc, dùng sparse table so close

 

aNotHeRNo0b

Senior Member

• 21/9/25

• #923

Q4 không biết làm sao mà sinh được số đẩy vào PriorityQueue các bác nhỉ, maintain 1 cái PriorityQueue size = k nma không biết làm sao sinh cho ra. Nested-for thì TLE

 

Husqvarna701SM

Senior Member

• 21/9/25

• #924

tiếp cận nhầm hướng +3 bug, mãi mới xong

 

Husqvarna701SM

Senior Member

• 21/9/25

• #925

aNotHeRNo0b đã nói:

Q4 không biết làm sao mà sinh được số đẩy vào PriorityQueue các bác nhỉ, maintain 1 cái PriorityQueue size = k nma không biết làm sao sinh cho ra. Nested-for thì TLE

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

bắt đầu từ toàn mang xong thụt 2 bên dạng như tree ấy thím

 

aNotHeRNo0b

Senior Member

• 21/9/25

• #926

DNA issue hiến máu nhân đạo rồi

 

freedom.9

Senior Member

• 21/9/25

• #927

Cho thêm tí thời gian chắc làm xong Q4 có ý tưởng rồi mà

 

aNotHeRNo0b

Senior Member

• 21/9/25

• #928

bài này cần trả lời câu hỏi:
- với 1 phần tử max và 1 phần tử min được chỉ định, có bao nhiêu subarray có thể tạo ra. Và query này phải trả lời trong O(1) hoặc O(log) :v

 

aNotHeRNo0b

Senior Member

• 21/9/25

• #929

ra rồi, ăn rồi vào upsolve thôi

 

Husqvarna701SM

Senior Member

• 21/9/25

• #930

aNotHeRNo0b đã nói:

bài này cần trả lời câu hỏi:
- với 1 phần tử max và 1 phần tử min được chỉ định, có bao nhiêu subarray có thể tạo ra. Và query này phải trả lời trong O(1) hoặc O(log) :v

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

Mình theo hướng đó nên gãy
Đầu tiên nhận xét là full array cho values lớn nhất và giảm hai đầu sẽ cho hai cái nhỏ hơn -> dùng heap, pop đủ k lần là đủ giá trị
Bài chuyển thành tìm value trong O(1) -> sparse table cho max và min

 

freedom.9

Senior Member

• 21/9/25

• #931

Husqvarna701SM đã nói:

Mình theo hướng đó nên gãy
Đầu tiên nhận xét là full array cho values lớn nhất và giảm hai đầu sẽ cho hai cái nhỏ hơn -> dùng heap, pop đủ k lần là đủ giá trị
Bài chuyển thành tìm value trong O(1) -> sparse table cho max và min

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

Còn mấy test case ko pass cay thật, ý tưởng là đi từ ngoài vào trong, đếm freq và xài sparse table + heap mà ko ăn đen
Đi từ ngoài vào trong dùng ý tưởng này thì sẽ bị trùng

 

freedom.9

Senior Member

• 21/9/25

• #932

Hí hí, dù ko ăn q4 vẫn rank 5 loét nhưng vẫn tự phạt tuần sau làm 10 bài hard
Bài nay hơi đen tí nhưng rút kinh nghiệm vậy
Xem tệp đính kèm 3249008

 

Windows 2001

Member

• 21/9/25

• #933

2Q
Tuần nay rớt rank rồi, hôm qua Codeforce tạch, hôm nay cũng tạch nốt

 

freedom.9

Senior Member

• 21/9/25

• #934

Đếm freq đúng phức tạp mà bị trùng hơi ngu code đúng phải là đi từng index kẹp thêm cái visited queue cho trường hợp left == right. Má nó

Spoiler: O(nlogn)

Python:

class Solution:
    def maxTotalValue(self, nums: List[int], k: int) -> int:
        n = len(nums)
        log_table = [0] * (n + 1)
        for i in range(2, n + 1):
            log_table[i] = log_table[i // 2] + 1
       
        max_st = [[0] * (log_table[n] + 1) for _ in range(n)]
        min_st = [[0] * (log_table[n] + 1) for _ in range(n)]
       
        for i in range(n):
            max_st[i][0] = nums[i]
            min_st[i][0] = nums[i]
           
        for j in range(1, log_table[n] + 1):
            for i in range(n - (1 << j) + 1):
                max_st[i][j] = max(max_st[i][j-1], max_st[i + (1 << (j-1))][j-1])
                min_st[i][j] = min(min_st[i][j-1], min_st[i + (1 << (j-1))][j-1])

        def query_max(l, r):
            j = log_table[r - l + 1]
            return max(max_st[l][j], max_st[r - (1 << j) + 1][j])

        def query_min(l, r):
            j = log_table[r - l + 1]
            return min(min_st[l][j], min_st[r - (1 << j) + 1][j])
       
        heap = [[query_min(0, n - 1) - query_max(0, n - 1), 0, n - 1]]
        ans = 0
        visited = set()
        visited.add((0, n - 1))
        while k:
            val, left, right = heapq.heappop(heap)
            val*= -1
            ans += val
            if left + 1 <= right and (left + 1, right) not in visited:
                visited.add((left + 1, right))
                newVal = query_min(left + 1, right) - query_max(left + 1, right)
                heapq.heappush(heap, [newVal, left + 1, right])

            if right - 1 >= left and (left, right - 1) not in visited:
                visited.add((left, right - 1))
                newVal = query_min(left, right - 1) - query_max(left, right - 1)
                heapq.heappush(heap, [newVal, left, right - 1])

            k -= 1

        return ans

Mà bài này nếu để hard 7 điểm thì constrain đúng ra phải k<= n*(n+1)//2.
Để 10^5 cũng ko khó lắm nhỉ, hơi lậm vô cái đếm frequency

 

Sửa lần cuối: 21/9/25

LKDT0357

Senior Member

• 21/9/25

• #935

tuần này đc 3/4
mong là giữ đc ổn định phong độ
chứ tuần 2/4 tuần 3/4 nhìn rating như chứng khoán mà chán

 

athxzz

Senior Member

• 21/9/25

• #936

cheater nhiều như lá mùa thu, sáng rank 2k1 giờ lên 1k7 r

 

LKDT0357

Senior Member

• 21/9/25

• #937

athxzz đã nói:

cheater nhiều như lá mùa thu, sáng rank 2k1 giờ lên 1k7 r

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

mà leetcode hình như diệt cheater ngay trong contest hay sao ấy
e thấy trong lúc thi đang 800 thấy tụt còn 600

 

hungmessi2

Senior Member

• 21/9/25

• #938

Leetcode nó có 1 cái promt ẩn lúc copy đề, ai mà copy paste thẳng từ ai ra là dễ bị dính lắm, promt kiểu như đặt tên biến là aksjdkalsdjlka, kiểu vậy...

 

LmaoSuVuong

Senior Member

• 21/9/25

• #939

hungmessi2 đã nói:

Leetcode nó có 1 cái promt ẩn lúc copy đề, ai mà copy paste thẳng từ ai ra là dễ bị dính lắm, promt kiểu như đặt tên biến là aksjdkalsdjlka, kiểu vậy...

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

kết quá trả lại trong code cũng phải ẩn biến đó thì mới bắt triệt để dc chứ mấy a ấn cũng có mắt, có não mà. cop xong ko thèm đọc lại xứng đáng ban IP vĩnh viễn

 

hungmessi2

Senior Member

• 21/9/25

• #940

LmaoSuVuong đã nói:

kết quá trả lại trong code cũng phải ẩn biến đó thì mới bắt triệt để dc chứ mấy a ấn cũng có mắt, có não mà. cop xong ko thèm đọc lại xứng đáng ban IP vĩnh viễn

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

Cách này chắc giảm được một ít thôi, kệ có còn hơn ko