thảo luận Leetcode mỗi ngày

Violet_7

Senior Member
8/7/2022:
  • 1 Câu hard khó, nhưng khó ở chỗ code khá dài vì nhiều dữ liệu
  • Nhìn vào đề bài: yêu cầu min cost cho target group, 1 group là gồm các nhà có màu liên tiếp
-> dẽ thấy có thể dùng backtracking, mỗi nhà có thể tô n màu -> time O(n^m) -> tle
  • như vậy phải tối ưu
  • nhận thấy 1 key khá quan trọng, số group sẽ tăng nếu houses[i.] != houses[i - 1]
-> dùng qhđ
  • tạo mảng 2 chiều dp, trong đó dp[i.][j.] là min cost có i group và kết thúc tại màu j
  • tạo hàm add để xét màu nhà thứ i vào cái dp
Xét lần lượt các ngôi nhà:
nếu houses[i.] == 0 -> nhà này có thể có nhiều màu, add lần lượt các màu và cost của có vào dp
nếu houses[i,] != 0 -> chỉ add màu nhà đó và cost lúc đó bằng 0
  • Về hàm add thì nhìn vào code :), làm câu này 1 tiếng nên h mệt, lúc nào khỏe thì viết tiếp
  • Nói chung là câu này ý tưởng cx khá dễ đoán mất 10p để nghĩ ra, không quá khó để nghĩ ra mà lúc code loạn vl vì nhiều dữ kiện quá dẫn đến code mất 50 phút:beat_brick::beat_brick:
  • Code : https://leetcode.com/submissions/detail/741509252/ (đã cố gắng viết gọn nhất có thể)
 
Last edited:

_Gia_Cat_Luong_

Senior Member
8/7/2022:
  • 1 Câu hard khó, nhưng khó ở chỗ code khá dài vì nhiều dữ liệu
  • Nhìn vào đề bài: yêu cầu min cost cho target group, 1 group là gồm các nhà có màu liên tiếp
-> dẽ thấy có thể dùng backtracking, mỗi nhà có thể tô n màu -> time O(n^m) -> tle
  • như vậy phải tối ưu
  • nhận thấy 1 key khá quan trọng, số group sẽ tăng nếu houses[i.] != houses[i - 1]
-> dùng qhđ
  • tạo mảng 2 chiều dp, trong đó dp[i.][j.] là min cost có i group và kết thúc tại màu j
  • tạo hàm add để xét màu nhà thứ i vào cái dp
Xét lần lượt các ngôi nhà:
nếu houses[i.] == 0 -> nhà này có thể có nhiều màu, add lần lượt các màu và cost của có vào dp
nếu houses[i,] != 0 -> chỉ add màu nhà đó và cost lúc đó bằng 0
  • Về hàm add thì nhìn vào code :), làm câu này 1 tiếng nên h mệt, lúc nào khỏe thì viết tiếp
  • Nói chung là câu này ý tưởng cx khá dễ đoán mất 10p để nghĩ ra, không quá khó để nghĩ ra mà lúc code loạn vl vì nhiều dữ kiện quá dẫn đến code mất 50 phút:beat_brick::beat_brick:
  • Code :https://leetcode.com/submissions/detail/741406332/ (đã cố gắng viết gọn nhất có thể)
Bài nàm làm bottom-up dài vậy nhỉ. Top down có chút:
https://leetcode.com/submissions/detail/741438343/
 

bribnt

Đã tốn tiền
Có ý tưởng dùng đồ thị như này chưa có thời gian code, bác nào thử xem có vấn đề gì không:

  • Vertex là |V| = {s, (i, j,k) } với s là một vertex ảo đánh dấu điểm bắt đầu, (i, j,k) là đại diện cho việc house i được tô bởi color j và đã có k neighborhood,
  • Edge nối từ s -> (0, j, 1) hoặc (i, j,k) -> (i + 1, j,k) hoặc (i,j,k) -> (i+1,j', k+1) với weight là cost[i+1][j],
  • Dùng Dijkstra để tìm đường đi ngắn nhất từ s tới n điểm có dạng (m-1, j, target).
  • Trick tối ưu:
    • Loại bỏ những vertex bất khả thi ngay từ đầu. VD có dạng (i, j, k) với k < i, hoặc (m-1, j, k) với k < target.
    • Trong quá trình tìm kiếm nếu gặp (i, j, target) thì chỉ lấy những vertex kề có cùng color j
 
Last edited:
Bài nàm làm bottom-up dài vậy nhỉ. Top down có chút:
https://leetcode.com/submissions/detail/741438343/
Sao em implement y hệt code java của nó phần TOP-DOWN nhưng bị TLE. Xoá hết mảng memo, dùng decorator @cache thì lại chạy được. Ảo diệu quá, bác biết tại sao lại thế k :(

Python:
class Solution:

    def minCost(self, houses, cost, m, n, target):

        memo = [[[None for _ in range(21)] for _ in range(100)] for _ in range(100)]
        MAX_COST = 1000001

        def find_min_cost(curr_index: int, neighbors_cnt: int, prev_color: int ):

            if curr_index == len(houses):
                return 0 if neighbors_cnt == target else MAX_COST

            if neighbors_cnt > target:
                return MAX_COST
           
            print(curr_index, neighbors_cnt, prev_color)
            if memo[curr_index][neighbors_cnt][prev_color] is not None:
                return memo[curr_index][neighbors_cnt][prev_color]

            min_cost = MAX_COST

            # Nếu nhà tại index này đã tô màu -> update neighbors_cnt và prev_color
            if houses[curr_index] != 0:
                new_neighbors_cnt = neighbors_cnt + (0, 1)[houses[curr_index] != prev_color]
                min_cost = find_min_cost(curr_index + 1, new_neighbors_cnt, houses[curr_index])

            # Nếu nhà tại index này chưa tô màu -> tô từ màu 1 đến màu cuối
            else:
                for color in range(1, len(cost[0])+1):
                    print(curr_index, color)
                    new_neighbors_cnt = neighbors_cnt + (0, 1)[color != prev_color]
                    curr_cost = cost[curr_index][color-1] + find_min_cost(curr_index+1, new_neighbors_cnt, color)
                    min_cost = min(min_cost, curr_cost)

            memo[curr_index][neighbors_cnt][prev_color] = min_cost
            return min_cost

        answer = find_min_cost(0, 0, 0)
        return (answer, -1)[answer == MAX_COST]
 

_Gia_Cat_Luong_

Senior Member
Sao em implement y hệt code java của nó phần TOP-DOWN nhưng bị TLE. Xoá hết mảng memo, dùng decorator @cache thì lại chạy được. Ảo diệu quá, bác biết tại sao lại thế k :(

Python:
class Solution:

    def minCost(self, houses, cost, m, n, target):

        memo = [[[None for _ in range(21)] for _ in range(100)] for _ in range(100)]
        MAX_COST = 1000001

        def find_min_cost(curr_index: int, neighbors_cnt: int, prev_color: int ):

            if curr_index == len(houses):
                return 0 if neighbors_cnt == target else MAX_COST

            if neighbors_cnt > target:
                return MAX_COST
          
            print(curr_index, neighbors_cnt, prev_color)
            if memo[curr_index][neighbors_cnt][prev_color] is not None:
                return memo[curr_index][neighbors_cnt][prev_color]

            min_cost = MAX_COST

            # Nếu nhà tại index này đã tô màu -> update neighbors_cnt và prev_color
            if houses[curr_index] != 0:
                new_neighbors_cnt = neighbors_cnt + (0, 1)[houses[curr_index] != prev_color]
                min_cost = find_min_cost(curr_index + 1, new_neighbors_cnt, houses[curr_index])

            # Nếu nhà tại index này chưa tô màu -> tô từ màu 1 đến màu cuối
            else:
                for color in range(1, len(cost[0])+1):
                    print(curr_index, color)
                    new_neighbors_cnt = neighbors_cnt + (0, 1)[color != prev_color]
                    curr_cost = cost[curr_index][color-1] + find_min_cost(curr_index+1, new_neighbors_cnt, color)
                    min_cost = min(min_cost, curr_cost)

            memo[curr_index][neighbors_cnt][prev_color] = min_cost
            return min_cost

        answer = find_min_cost(0, 0, 0)
        return (answer, -1)[answer == MAX_COST]
Submit được mà, có TLE đâu bác ?
https://leetcode.com/submissions/detail/741670142/
 

bribnt

Đã tốn tiền
https://voz.vn/t/leetcode-moi-ngay.568742/post-18821562

Cách làm OK.
Lâu không code đồ thị tốn thời gian quá.

1657289374649.png


https://leetcode.com/submissions/detail/741812376/

Để giảm không gian tìm kiếm thì ban đầu vào đưa những vertex (i, j, t) dạng sau vào danh sách invalid:
  • i < t: vì sau i house chắc chắn sẽ có ít nhất i neighborhood,
  • Tương tự: m - i < target - t: trường hợp này sẽ không đạt được neighborhood bằng target.

Những trường hợp sau chắc chắn là invalid để đảm bảo tính đúng đắn:
  • house[i] > 0 && house[i] != j + 1
 

_Gia_Cat_Luong_

Senior Member
https://voz.vn/t/leetcode-moi-ngay.568742/post-18821562

Cách làm OK.
Lâu không code đồ thị tốn thời gian quá.

View attachment 1254429

https://leetcode.com/submissions/detail/741812376/

Để giảm không gian tìm kiếm thì ban đầu vào đưa những vertex (i, j, t) dạng sau vào danh sách invalid:
  • i < t: vì sau i house chắc chắn sẽ có ít nhất i neighborhood,
  • Tương tự: m - i < target - t: trường hợp này sẽ không đạt được neighborhood bằng target.

Những trường hợp sau chắc chắn là invalid để đảm bảo tính đúng đắn:
  • house[i] > 0 && house[i] != j + 1
Quá đỉnh mai fen
 

Violet_7

Senior Member
7/9/2022:
  • 1 câu medium khá quen
  • Ý tưởng là 1 câu biến tấu câu max window: https://leetcode.com/problems/sliding-window-maximum/
  • lời giải câu trên https://vnoi.info/wiki/algo/data-structures/deque-min-max.md
  • tạo mảng dp với dp[i.] là max score khi con ếch đến ô thứ i
  • vì con ếch chỉ nhảy đc từ 1 đến k bước nên để đến đc ô thứ i thì trước đó con ếch có thể đứng ở 1 trong k ô trước đó
  • vậy nếu biết dp của k ô trước đó thì dp[i.] = max(dp[i - k] -> dp[i - 1]) + nums[i.]
  • như vậy áp dụng công thức qhđ trên và ý tưởng câu tìm max trên 1 đoạn tịnh tiến k sẽ ra đáp án
  • Lúc đầu cx áp dụng cái câu max window kia mà phức tạp xét âm dương nên code hơi dài, đọc solution thì chả cần phải tách âm dương làm j nên đã tối ưu code lại:
https://leetcode.com/submissions/detail/742162855/
 
Last edited:
7/9/2022:
  • 1 câu medium khá quen
  • Ý tưởng là 1 câu biến tấu câu max window: https://leetcode.com/problems/sliding-window-maximum/
  • lời giải câu trên https://vnoi.info/wiki/algo/data-structures/deque-min-max.md
  • tạo mảng dp với dp[i.] là max score khi con ếch đến ô thứ i
  • vì con ếch chỉ nhảy đc từ 1 đến k bước nên để đến đc ô thứ i thì trước đó con ếch có thể đứng ở 1 trong k ô trước đó
  • vậy nếu biết dp của k ô trước đó thì dp[i.] = max(dp[i - k] -> dp[i - 1]) + nums[i.]
  • như vậy áp dụng công thức qhđ trên và ý tưởng câu tìm max trên 1 đoạn tịnh tiến k sẽ ra đáp án
  • Lúc đầu cx áp dụng cái câu max window kia mà phức tạp xét âm dương nên code hơi dài, đọc solution thì chả cần phải tách âm dương làm j nên đã tối ưu code lại:
https://leetcode.com/submissions/detail/742162855/
Ý tưởng dùng deque hay đó.
Tuy nhiên phần đề cập đến độ phức tạp của deque trong bài viết của vnoi là không đúng.
1657337142900.png

https://en.cppreference.com/w/cpp/container/deque/operator_at
 
cay, giải giống hôm qua rồi mà bị
View attachment 1255197
t submit lần đầu cũng bị ntn. Do k chịu đọc kỹ chỗ đề bài
1657338230835.png

Cách làm này độ phức tạp là O(nums.length*k) nên với constraints như trên thì TLE là đúng rồi.

Coi cách làm bên trên chỗ xử lý cái max để giảm độ phức tạp thì sẽ pass đc. :p
 
t submit lần đầu cũng bị ntn. Do k chịu đọc kỹ chỗ đề bài
View attachment 1255199
Cách làm này độ phức tạp là O(nums.length*k) nên với constraints như trên thì TLE là đúng rồi.

Coi cách làm bên trên chỗ xử lý cái max để giảm độ phức tạp thì sẽ pass đc. :p
chứng minh kiểu gì để ra độ phức tạp là O(NK) với top-down memo vậy bác
 
Top