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

aNotHeRNo0b

Senior Member

• 24/8/25

• #761

Q3 segment tree cay lỏ thiệc. Tìm vị trí xa nhất có giá trị nhỏ hơn nums

 

freedom.9

Senior Member

• 24/8/25

• #762

Thôi bỏ cuộc, ko có ý tưởng gì Q4 cả

 

aNotHeRNo0b

Senior Member

• 24/8/25

• #763

Em thất bát rồi các bác ạ, rank 16k, đang 2k về lại 1k8 ngồi rồi

 

M

Manmapi

Senior Member

• 24/8/25

• #764

aNotHeRNo0b đã nói:

Q3 segment tree cay lỏ thiệc. Tìm vị trí xa nhất có giá trị nhỏ hơn nums

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

Q3 dùng binary seach + prefix sum nè bác

 

aNotHeRNo0b

Senior Member

• 24/8/25

• #765

Manmapi đã nói:

Q3 dùng binary seach + prefix sum nè bác

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

Ảo vậy fen, cho mình xin í tưởng được không, bí quá @@

 

M

Manmapi

Senior Member

• 24/8/25

• #766

Khả năng là cách giải của em sẽ bị rejudge nếu đề bài yêu cầu nhảy quá nhiều

Spoiler: Q3 | Binary search, prefix and hope

Python:

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        # Determine how far in can jump forward
        prefix_max = [nums[0]]
        curr = nums[0]
        n = len(nums)
        for num in nums[1:]:
            if num > curr:
                curr = num
            prefix_max.append(curr)
            
        prefix_min = [(n - 1, nums[-1])]
        curr = nums[-1]
        for i in range(n - 2, -1, -1):
            if curr > nums[i]:
                curr = nums[i]
                prefix_min.append((i, curr))
        prefix_min = prefix_min[::-1]
        res = []
        l_pm = len(prefix_min)
        def find_jump(index, num):
            result = index
            l, r = 0, l_pm - 1
            while l <= r:
                mid = (l + r) // 2
                if num > prefix_min[mid][1]:
                    result = prefix_min[mid][0]
                    
                    l = mid + 1
                else:
                    r = mid - 1
            return result

        # Do update res until no more update
        # Hope this will end before TLE
        res = [0] * n
        changed = True
        iteration = 0
        
        while changed:
            changed = False
            updated_max = -1
            new_res = [0] * n
            new_prefix_max = []
            for i, num in enumerate(nums):
                jump_index = max(find_jump(i, num), i)
                current_max = prefix_max[jump_index]
                if i > 0:
                    current_max = max(current_max, res[i-1])
                
                updated_max = max(current_max, updated_max)
                new_prefix_max.append(updated_max)
                new_res[i] = updated_max
                if res[i] != new_res[i]:
                    changed = True
            res = new_res[:]
            prefix_max = new_prefix_max
        return res©leetcode

 

freedom.9

Senior Member

• 24/8/25

• #767

Q3 của mình đây ae

Python:

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        largestFromTheLeft = [-inf]*n
        indx = -1
        for i in range(n):
            if indx == -1:
                indx = i
            else:
                if nums[i] > nums[indx]:
                    indx = i

            largestFromTheLeft[i] = indx

        stack = []
        sl = SortedList()
        ans = [-1]*n
        for i in range(n - 1, -1, -1):
            while stack and nums[largestFromTheLeft[i]] <= nums[stack[-1]]:
                indx = stack.pop()
                sl.remove(nums[largestFromTheLeft[indx]])

            if sl:
                ans[i] = max(nums[largestFromTheLeft[i]], sl[-1])
            else:
                ans[i] = nums[largestFromTheLeft[i]]
                
            sl.add(nums[largestFromTheLeft[i]])
            stack.append(i)
            
        return ans
        
        ©leetcode

Ý tưởng là ở mỗi index thì có thể nhảy về max phía trái, sau đó thì có thể nhảy về các index nhỏ hơn max phía trái để tìm ra số max.
Mình đi ngược lại từ n - 1, dùng 1 monotonic stack để keep track tất cả các số nhỏ hơn max phía trái, và maintain thêm 1 cái sortedlist để lưu giá trị lớn nhất ở mỗi index về phía trái. Kết quả sẽ là max value trong cái sorted list cho mỗi index.

 

aNotHeRNo0b

Senior Member

• 24/8/25

• #768

freedom.9 đã nói:

Q3 của mình đây ae

Python:

class Solution:
    def maxValue(self, nums: List[int]) -> List[int]:
        n = len(nums)
        largestFromTheLeft = [-inf]*n
        indx = -1
        for i in range(n):
            if indx == -1:
                indx = i
            else:
                if nums[i] > nums[indx]:
                    indx = i

            largestFromTheLeft[i] = indx

        stack = []
        sl = SortedList()
        ans = [-1]*n
        for i in range(n - 1, -1, -1):
            while stack and nums[largestFromTheLeft[i]] <= nums[stack[-1]]:
                indx = stack.pop()
                sl.remove(nums[largestFromTheLeft[indx]])

            if sl:
                ans[i] = max(nums[largestFromTheLeft[i]], sl[-1])
            else:
                ans[i] = nums[largestFromTheLeft[i]]
               
            sl.add(nums[largestFromTheLeft[i]])
            stack.append(i)
           
        return ans
       
        ©leetcode

Ý tưởng là ở mỗi index thì có thể nhảy về max phía trái, sau đó thì có thể nhảy về các index nhỏ hơn max phía trái để tìm ra số max.
Mình đi ngược lại từ n - 1, dùng 1 monotonic stack để keep track tất cả các số nhỏ hơn max phía trái, và maintain thêm 1 cái sortedlist để lưu giá trị lớn nhất ở mỗi index về phía trái. Kết quả sẽ là max value trong cái sorted list cho mỗi index.

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

Em cũng có ý tưởng dùng monotoic nhưng mà lại chọn nhảy về min xa nhất rồi mới về max.

DNA issue nên không xử được

 

aNotHeRNo0b

Senior Member

• 24/8/25

• #769

bầm dập hết người

 

freedom.9

Senior Member

• 24/8/25

• #770

Q3 khó vl ấy chứ, giải ra là đã thấy thỏa mãn rồi, Q4 6 điểm còn khó hơn nhiều. Ko thể nhìn ra đó là DP được

 

freedom.9

Senior Member

• 24/8/25

• #771

Q3 cũng tương tự như 1 câu Div2 D, khó vãi.
Nếu mà cho mình ít thời gian nữa thì chắc là nghĩ theo hướng DP Q4 được mà giải Q3 quá tốn thời gian

 

dhl001

Đã tốn tiền

• 24/8/25

• #772

giải được Q1 là mình hạnh phúc rồi

 

aNotHeRNo0b

Senior Member

• 24/8/25

• #773

Thằng clist.by crawl bảng rank lâu nhỉ, chắc infra không đủ mạnh nên kéo khá lâu 30 phút mà mới hơn 3500 record

 

troioidaucatmoi

Member

• 24/8/25

• #774

aNotHeRNo0b đã nói:

Thằng clist.by crawl bảng rank lâu nhỉ, chắc infra không đủ mạnh nên kéo khá lâu 30 phút mà mới hơn 3500 record

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

Bác tự host cái riêng cho ae vozer đi e cũng đợi nãy h

 

freedom.9

Senior Member

• 24/8/25

• #775

Q4 quên mẹ mất cái case 2 con robot ném bị conflict, ko là nghĩ qua hướng dp rồi đi greedy sai quá sai.
Q3 làm mình hơi bị panic q4 chứ q4 còn dễ hơn cả q3

via theNEXTvoz for iPhone

 

aNotHeRNo0b

Senior Member

• 24/8/25

• #776

:v vào đọc thấy nó là 1 con mono, riêng phần crawl thì thấy spawn 8 thread rồi kéo từng page :> bảo sao lâu, code bằng python nữa thì ._. cứ từ từ chờ thôi bác ạ
clist/src/ranking/management/modules /leetcode.py

troioidaucatmoi đã nói:

Bác tự host cái riêng cho ae vozer đi e cũng đợi nãy h

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

 

freedom.9

Senior Member

• 24/8/25

• #777

Để ý gần đây Leetcode toàn cho ra mấy câu Dp mà ko nhìn ra là Dp nhé, khá khoai nhưng hay đỡ ngán

via theNEXTvoz for iPhone

 

LmaoSuVuong

Senior Member

• 24/8/25

• #778

freedom.9 đã nói:

Để ý gần đây Leetcode toàn cho ra mấy câu Dp mà ko nhìn ra là Dp nhé, khá khoai nhưng hay đỡ ngán

via theNEXTvoz for iPhone

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

nhìn không ra tức là học gạo. pattern solver r

 

aNotHeRNo0b

Senior Member

• 24/8/25

• #779

Đề hôm nay chết chóc thật :v bắt đầu quỷ quỷ giống như bên Codeforce rồi

 

Husqvarna701SM

Senior Member

• 24/8/25

• #780

Sáng đi trà đá nói xấu port k kịp làm, ngó thử trông đề cũng khả thi
Tối thím nào phang div 2 k