LmaoSuVuong
Senior Member
Q3 cảm giác gần ra r mà testcase ko qua
thảo luận Leetcode contest, đường tới Guardian
- Thread starter freedom.9
- Start date
LmaoSuVuong
Senior Member
hôm nay làm dc có 2 câu mà vẫn rank 3k, chắc tại đề khó r
honda stone
Junior Member
ý tưởng q4 của em:
-với số thứ i trong dãy big_nums, ta sẽ đi đếm từ 1 cho đến i xem có bao nhiêu bit 0, bao nhiêu bit 1, bao nhiêu bit 2... => lưu vào 1 dãy gọi là F
- với mỗi query [from, to, mod], chỉ cần tính F(to) - F(from - 1), rồi đi tính tích là xong.
nhìn thì rất ngắn nhưng cài sml không đúng được hàm F
-với số thứ i trong dãy big_nums, ta sẽ đi đếm từ 1 cho đến i xem có bao nhiêu bit 0, bao nhiêu bit 1, bao nhiêu bit 2... => lưu vào 1 dãy gọi là F
- với mỗi query [from, to, mod], chỉ cần tính F(to) - F(from - 1), rồi đi tính tích là xong.
nhìn thì rất ngắn nhưng cài sml không đúng được hàm F
JustAnOtherClone
Senior Member
nó chưa update thôi, chứ fen làm tận 1h30 chắc phải lên 7k 8k
honda stone
Junior Member
chưa kể nữa là q3 không quá khó (> 4k user LCUS accepted), và ranking cuối thì tính dựa trên cả LCCN + LCUS gộp lại
Mỹ Chu Lang
Senior Member
hix weekly contest trước giải được 3 câu mà biweekly tuần này được có 1 câu, câu 2 chạy đúng được 3 cái example, submit thì bị sai
honda stone
Junior Member
Em cũng chạy O(26*n^2) đây.Bà mẹ nó bài 3 giải O(n2)*26 mà chết là sao nhỉ, cay vcl
Loay hoay cả tiếng rồi còn éo làm cả bài 2 đcm. Thôi ăn cứt gà rồi huhu
f[j] = min(f[j], f['i'] + 1) nếu như 2 đoạn từ 0 đến i và từ i+1 đến j là hợp lệ
LmaoSuVuong
Senior Member
câu 2 brute force TLE, hôm bữa bác nào bên thớt daily xúi Q1, Q2 auto bruteforce nghe theo lừa vlBà mẹ nó bài 3 giải O(n2)*26 mà chết là sao nhỉ, cay vcl
Loay hoay cả tiếng rồi còn éo làm cả bài 2 đcm. Thôi ăn cứt gà rồi huhu
freedom.9
Senior Member
Má nó mình chủ quan ko dùng cái template là for j in range(i, n) ở trong DP mà set nó thành dp(prevIndex, index) rồi tính frequency ở bên ngoài vì nghĩ là time complexity là như nhau.
Vẫn O(n^2)26 mà TLE loay hoay còn bỏ cả bài 2
RIP rank
honda stone
Junior Member
Sol Q2 của em:câu 2 brute force TLE, hôm bữa bác nào bên thớt daily xúi Q1, Q2 auto bruteforce nghe theo lừa vl
Với mỗi điểm (x, y) thì nó sẽ nằm trên cạnh của hình vuông có cạnh edge = max(abs(x), abs(y)).
Từ đó ta tạo 1 mảng gồm các edge['i'] và s['i'], xếp theo thứ tự tăng dần theo edge['i']
Mỗi lần duyệt đến phần tử thứ i. Nếu s['i'] đã xuất hiện, ta trả về kết quả là i.
Nếu s['i'] chưa xuất hiện ta duyệt các phần tử j liên tiếp phía sau nó sao cho edge['i'] = edge[j].
Đến 1 phần tử j nào đó mà s[j] đã xuất hiện thì trả về kết quả là i.
Tiếp tục vòng lặp bằng cách tịnh tiến i = j + 1.
Cuối cùng, trả về n.
Em phát hiện ra rồi, khai báo bool label[26] = {false} thì submit mới đúng. Tưởng default array thì tất cả phần từ phải false chứ nhỉ
h_ngyn
Senior Member
Q2
Thì ý tưởng của em là chặt nhị phân tìm kiếm khoảng cách lớn nhất tính từ điểm (0,0) mà thoả mãn các điểm nằm trong khoảng cách đó có tag là unique
Cứ tìm được 1 khoảng cách thoả mãn thì sẽ update kết quả là số lượng những thằng nằm trong khoảng cách đó và tìm kiếm tiếp với khoảng lớn hơn
via theNEXTvoz for iPhone
Thì ý tưởng của em là chặt nhị phân tìm kiếm khoảng cách lớn nhất tính từ điểm (0,0) mà thoả mãn các điểm nằm trong khoảng cách đó có tag là unique
Cứ tìm được 1 khoảng cách thoả mãn thì sẽ update kết quả là số lượng những thằng nằm trong khoảng cách đó và tìm kiếm tiếp với khoảng lớn hơn
via theNEXTvoz for iPhone
LmaoSuVuong
Senior Member
câu này đề đọc sao e làm v luôn. tìm hình vuông bé thứ 2 chứa tag trùng r đếm xem bao nhiêu điểm nằm bên trong đó
lúc đầu bruteforce bị TLE, bỏ vào hashmap tìm hình vuông thì qua
honda stone
Junior Member
Nếu em nhớ không nhầm thì 1 biến hay mảng được khai báo global mà không gán giá trị gì thì mới nhận giá trị mặc định. Còn nếu được khai báo bên trong hàm thì sẽ nhận 1 giá trị tuỳ ý nào đó (thực ra không hẳn là tuỳ ý
).Uk, em mới check thì thấy bảo tùy bộ compiler và setup môi trường nữa. Nên thôi rút kinh nghiệm chuyển sang dùng vector.Nếu em nhớ không nhầm thì 1 biến hay mảng được khai báo global mà không gán giá trị gì thì mới nhận giá trị mặc định. Còn nếu được khai báo bên trong hàm thì sẽ nhận 1 giá trị tuỳ ý nào đó (thực ra không hẳn là tuỳ ý
Mà chạy subtest thì dudgns, nhưng submit chạy all test mới sai nên ko nghĩ là sai chỗ đó
---
In C++, the behavior of bool arrays (bool arr[n]
can be non-standard and may cause unexpected issues, especially with standard library containers and iterators. Instead of using a C-style array, you can use std::vector<bool> for better compatibility and behavior:
freedom.9
Senior Member
Giải O(n^2)*26 n chết ko hiểu sao nhỉ đm lần sau ko sáng tạo DP nữa mà xài template có sẵn thôi, ngồi sáng tạo ra cái frequency check loay hoay cả tiếng éo biết tại sao lại TLE
đm lần sau ko sáng tạo DP nữa mà xài template có sẵn thôi, ngồi sáng tạo ra cái frequency check loay hoay cả tiếng éo biết tại sao lại TLE
Python:
class Solution:
def minimumSubstringsInPartition(self, s: str) -> int:
n = len(s)
frequencyCheck = [[False] * n for _ in range(n)]
for i in range(len(s)):
frequency = defaultdict(int)
frequency[s[i]] += 1
frequencyCheck[i][i] = True
for j in range(i + 1, len(s)):
frequency[s[j]] += 1
if len(set(frequency.values())) == 1:
frequencyCheck[i][j] = True
@lru_cache(None)
def dp(prev_index, index):
if index == len(s) - 1:
if frequencyCheck[prev_index][index]:
return 1
else:
return float('inf')
ans = float('inf')
if frequencyCheck[prev_index][index]:
ans = min(ans, 1 + dp(index + 1, index + 1))
ans = min(ans, dp(prev_index, index + 1))
return ans
return dp(0, 0)
maskup
Senior Member
Bài 3 O(n2) của em, ý tưởng là dp tương tự bài word break + sliding window
Python:
class Solution:
def minimumSubstringsInPartition(self, s: str) -> int:
@cache
def dp(end):
if end < 0:
return 0
ans = math.inf
counter = Counter()
eqMax = 0
maxCnt = 0
for l in range(end, -1, -1):
counter[s[l]] += 1
if counter[s[l]] == maxCnt:
eqMax += 1
elif counter[s[l]] > maxCnt:
maxCnt = counter[s[l]]
eqMax = 1
if eqMax == len(counter):
ans = min(ans, 1 + dp(l - 1))
return ans
n = len(s)
return dp(n - 1)
