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

humanversion9x đã nói:

Thuật toán này có Time complexity là 1 + 2 + 4 + 8 + .. + 2^k = 2^(k+1) - 1 = O(2^k) rồi bạn.

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

freedom.9 đã nói:

Sao lại 2^K đc nhỉ, 2^K thì k = 16 là chết à, cũng như bfs thông thường thôi mà chỉ là O(n) thôi chứ


via theNEXTvoz for iPhone

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

humanversion9x đã nói:

BFS O(n) thì n là số đỉnh trong đồ thị. Trong thuật toán của bạn thì những giá trị total (2,...,k-1) sẽ được thăm nhiều lần.
Edit: Mình không lập trình trên python. Có đoạn code "if (total, lastNum) in visited" thì mình hiểu là nếu một cặp (total, lastNum) đã gặp rồi thì bỏ qua, nhưng (total, lastNum nào đó) thì sẽ được xét các lân cận.

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

freedom.9 đã nói:

Ừ cũng đúng nhỉ, để mình tính toán lại xem sao. Thanks fence. Do mình nghĩ tối đa thì mình chỉ có K đỉnh trong đồ thị thôi, nhưng mà ko phải rồi vì cache kiểu này nó sẽ là O(k*lastNum) nên worst case sẽ là O(n^2) chứ ko phải O(n)

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

freedom.9 đã nói:

À mấy fence cho mình hỏi thử sao bài 2 giải bằng DFS thì nó throws TLE nhỉ
Time complexity với space complexity chỉ là O(n) thôi mà, vì worst case ở mỗi trường hợp nó tăng lên từ 1 -> 10^5 thôi chứ nhỉ

Python:

from collections import deque

class Solution:
    def minOperations(self, k: int) -> int:
        visited = set()
        queue = deque()
        queue.append((0, 1, 1))
      
        while queue:
            operations, total, lastNum = queue.popleft()
          
            if total >= k:
                return operations
          
            if (total, lastNum) in visited:
                continue
          
            visited.add((total, lastNum))
          
            queue.append((operations + 1, total + lastNum, lastNum))
            queue.append((operations + 1, total + 1, lastNum + 1))
          
        return -1

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

hieunm3538 đã nói:

Em chạy thử thấy k = 3819 là đã TLE rồi, chắc test case bài này khá chặt, phải giải dưới O(n^2) thì mới qua

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

freedom.9 đã nói:

Xem tệp đính kèm 2408064
Cày sml ăn quả rank 13k4 mất toi 30 điểm huhu.
Đúng bài contest Q4 dễ nữa chứ

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

nahnahinin đã nói:

cau 2 doc de voi sai mat bo no 2 lan, cay vc

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

youknowwho151 đã nói:

OR là destructive éo dùng sliding window theo kiểu + - được cay vl fail r

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

TLE_WA đã nói:

spoil chút là vẫn dùng được nhé

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

seastar đã nói:

Xem tệp đính kèm 2413290
Phút cuối cùng submit ăn đc câu cuối,

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

chiyeuemthoi đã nói:

xin cách với thím

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