LmaoSuVuong
Senior Member
7k người làm dc nhưng chắc 5k gcd r ko unrate hơi phíBài 3 tụi top nó có thằng nào làm sai đâu, 7k thằng làm đc đừng unrate nhé
via theNEXTvoz for iPhone
thảo luận Leetcode contest, đường tới Guardian
- Người tạo chủ đề freedom.9
- Ngày bắt đầu
- Trạng thái
NguyenQUy1801
Senior Member
q4 đọc giải xong thấy sao sao ấy 
)
)
hieunm3538
Senior Member
Chúc mừng bác lên Knight nhéBài 3 tụi top nó có thằng nào làm sai đâu, 7k thằng làm đc đừng unrate nhé
via theNEXTvoz for iPhone
))
freedom.9
Senior Member
Xài GCD accepted chắc unrate rồi fenceChúc mừng bác lên Knight nhé
Đúng là đề nó ko nói rõ thật
Mà ngày xưa Q4 tụi nó cũng weak testcase mà có unrate đâu
via theNEXTvoz for iPhone
humanversion9x
Senior Member
Rejudge thôi. Vì đề nói rõ là ghép các anagram vào. Lời giải dùng gcd là giải một bài toán khác hoàn toàn.Xài GCD accepted chắc unrate rồi fence
Đúng là đề nó ko nói rõ thật
Mà ngày xưa Q4 tụi nó cũng weak testcase mà có unrate đâu
via theNEXTvoz for iPhone
Violet_7
Member
Câu 4 chiều nay cx phải mất 1 tiếng ms giải đc
Về cơ bản là nếu cost1 < cost2 / 2 thì dùng nguyên cost1 thôi, cho tăng tất cả các số để bằng số lớn nhất
TH cost1 > cost2 / 2 thì phải áp dùng cost2 nhiều nhất có thể, bài này full greedy nên giải thích cx hơi khó
Về cơ bản là nếu cost1 < cost2 / 2 thì dùng nguyên cost1 thôi, cho tăng tất cả các số để bằng số lớn nhất
TH cost1 > cost2 / 2 thì phải áp dùng cost2 nhiều nhất có thể, bài này full greedy nên giải thích cx hơi khó
Python:
from sortedcontainers import SortedList
class Solution:
def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int:
max_num = max(nums)
n = len(nums)
if cost1 * 2 <= cost2:
return (max_num * len(nums) - sum(nums)) * cost1 % int(1e9 + 7)
lefts = [max_num - num for num in nums if num < max_num]
if len(lefts) == 0:
return 0
max_left = max(lefts)
sum_lefts = sum(lefts)
cost2_count = 0
cost1_count = 0
if max_left * 2 <= sum_lefts:
cost2_count = sum_lefts // 2
cost1_count = sum_lefts % 2
else:
cost2_count = sum_lefts - max_left
cost1_count = max_left - cost2_count
base_cost = cost1_count * cost1 + cost2_count * cost2
if (n - 1) * cost2 >= (n - 2) * cost1:
return base_cost % int(1e9 + 7)
min_cost = base_cost
increase = cost1_count // (n - 2)
cost1_count -= increase * (n - 2)
cost2_count += increase * (n - 1)
min_cost = min(min_cost, cost1_count * cost1 + cost2_count * cost2)
for _ in range(2):
cost2_count += (n + cost1_count) // 2
cost1_count = (n - 1 - cost1_count - 1) % 2
min_cost = min(min_cost, cost1_count * cost1 + cost2_count * cost2)
return min_cost % int(1e9 + 7)
Bác cho em hỏi xíu vs ạ, hiện bác đã solve bn câu trên LC vậy ạkhông bác, nay em hết giờ mới sửa xong q4non vc
LmaoSuVuong
Senior Member
bài này nhìn đề giống dp thế mà ko dùng dp để giải dc hả bác ?Câu 4 chiều nay cx phải mất 1 tiếng ms giải đc
Về cơ bản là nếu cost1 < cost2 / 2 thì dùng nguyên cost1 thôi, cho tăng tất cả các số để bằng số lớn nhất
TH cost1 > cost2 / 2 thì phải áp dùng cost2 nhiều nhất có thể, bài này full greedy nên giải thích cx hơi khó
Python:from sortedcontainers import SortedList class Solution: def minCostToEqualizeArray(self, nums: List[int], cost1: int, cost2: int) -> int: max_num = max(nums) n = len(nums) if cost1 * 2 <= cost2: return (max_num * len(nums) - sum(nums)) * cost1 % int(1e9 + 7) lefts = [max_num - num for num in nums if num < max_num] if len(lefts) == 0: return 0 max_left = max(lefts) sum_lefts = sum(lefts) cost2_count = 0 cost1_count = 0 if max_left * 2 <= sum_lefts: cost2_count = sum_lefts // 2 cost1_count = sum_lefts % 2 else: cost2_count = sum_lefts - max_left cost1_count = max_left - cost2_count base_cost = cost1_count * cost1 + cost2_count * cost2 if (n - 1) * cost2 >= (n - 2) * cost1: return base_cost % int(1e9 + 7) min_cost = base_cost increase = cost1_count // (n - 2) cost1_count -= increase * (n - 2) cost2_count += increase * (n - 1) min_cost = min(min_cost, cost1_count * cost1 + cost2_count * cost2) for _ in range(2): cost2_count += (n + cost1_count) // 2 cost1_count = (n - 1 - cost1_count - 1) % 2 min_cost = min(min_cost, cost1_count * cost1 + cost2_count * cost2) return min_cost % int(1e9 + 7)
Violet_7
Member
Giống dp chỗ nào bác nhể. Nếu để ý 2 cái cost thì có thể nhận ra đc là bài greedy rồi bác. Vs dp bác phải tìm ra 1 trạng thái cụ thể theo yêu cầu đề bài nên ỏ bài này rất khó tìm ra trạng thái đó
honda stone
Junior Member
đây bác, em mới làm nên cũng còn ít lắm
nhiều câu nghĩ không ra còn phải đi tham khảo sol của người khác xong về code lại
LmaoSuVuong
Senior Member
250 câu mà bác toàn giải hardXem tệp đính kèm 2477374
đây bác, em mới làm nên cũng còn ít lắm
nhiều câu nghĩ không ra còn phải đi tham khảo sol của người khác xong về code lại
humanversion9x
Senior Member
Lúc mình biết bạn rating gần 2k sau tầm 3-4 contest. Mình nghĩ bạn phải giải tầm 1k5-2k câu hỏi trên leetcode rồi. Ai ngờ đâu chỉ giải có 244 câu mà đã khủng thế này.Xem tệp đính kèm 2477374
đây bác, em mới làm nên cũng còn ít lắm
nhiều câu nghĩ không ra còn phải đi tham khảo sol của người khác xong về code lại
h_ngyn
Senior Member
Bạn phải coi là base của bạn đó như thế nào, và trước khi luyện leetcode đã từng luyện trên trang nào khác chưa.
Ví dụ thanh niên này: https://leetcode.com/u/tmwilliamlin168/
Profile leetcode thì mới có 200 bài thôi. Nhưng ở codeforces (https://codeforces.com/profile/tmwilliamlin168) đã làm hơn 1k7 bài rồi, và bạn này cũng tham gia nhiều cuộc thi về algo và có giải rồi (nổi bật nhất chắc là vàng IOI)
honda stone
Junior Member
Em cũng đồng ý ạ, hồi cấp 3 em có học tin một tí (cũng có làm vnoj/codeforces).
Sau khoảng 5-6 năm không học hành gì thì giờ em mới bắt đầu học lại.
h_ngyn
Senior Member
Yeah, nhưng mà mình vẫn công nhận là bạn giỏi. Nhiều người (trong đó có mình) vẫn cày đều nhưng cảm giác vẫn k bứt lên được. Bạn bỏ ngang lâu nhưng giờ quay lại vẫn làm được thì tư duy cũng rất tốt rồi.
hieunm3538
Senior Member
Bạn ý tự làm được bài 4 contest rồi là tư duy đỉnh rồi mà bác, bài đấy 4 case xử lý mệt kinh :v Cả contest cũng có đúng hơn 300 người làm xong kịp
Em cũng nghĩ bác @honda stone cũng phải cày tầm > 1k mới solve đc cả 4Q và 3Q đều đều vậy. Hiện em cày nhưng bị "chững lại", không giải đều đc Q3, thường 2Q, câu Q3 thì hên xui ạ, còn solve cả 4Q thì chưa được lần nào. Không biết bác nào đang mắc ở contest như em không ạ. Giờ mình cày thêm bài hard hay sao á. (Em cũng có luyện theo từng topic rồi, dạo này thì đang tích cực giải câu hard, nhưng 1 ngày tốt lắm là đc 1 bài => giải lại, còn không phải 2 ngày mới hiểu đc và giải lại)
- Trạng thái
Chủ đề tương tự
