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

freedom.9 said:

À 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

Click to expand...

humanversion9x said:

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.

Click to expand...

freedom.9 said:

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

Click to expand...

humanversion9x said:

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.

Click to expand...

freedom.9 said:

Ừ 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)

Click to expand...

freedom.9 said:

À 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

Click to expand...

hieunm3538 said:

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

Click to expand...

freedom.9 said:

View attachment 2408064
Cày sml ăn quả rank 13k4 mất toi 30 điểm huhu.
Đúng bài contest Q4 dễ nữa chứ

Click to expand...

nahnahinin said:

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

Click to expand...

chiyeuemthoi said:

same với bác, c3 mng dùng gì vậy sliding win dc k nhỉ

Click to expand...

youknowwho151 said:

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

Click to expand...

TLE_WA said:

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

Click to expand...