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

LmaoSuVuong said:
osCpCsi.png
cái lày là sao nhỉ, e cũng tiếp cận kiểu count freq nhưng xếp kiểu aabb này thì phải trả ra 4 thay vì 2 chứ nhỉ
Click to expand...
1 anagram là ko quan tâm tới order, chỉ quan tâm tới frequency.
Ví dụ string ban đầu có 4a, 2b, 2c chả hạn thì để tạo ra string ban đầu thì cần dùng 2 string chứa 2a 1b 1c , + nó lại sẽ đc 4a 2b 2c.
Nên cái cần tìm là tìm GCD của tất cả các frequency thôi.

via theNEXTvoz for iPhone
 
freedom.9 said:
1 anagram là ko quan tâm tới order, chỉ quan tâm tới frequency.
Ví dụ string ban đầu có 4a, 2b, 2c chả hạn thì để tạo ra string ban đầu thì cần dùng 2 string chứa 2a 1b 1c , + nó lại sẽ đc 4a 2b 2c.
Nên cái cần tìm là tìm GCD của tất cả các frequency thôi.

via theNEXTvoz for iPhone
Click to expand...
vừa check thử code mấy top, mấy a c++ đầu vẫn xài gcd nhưng aabb vẫn trả về 4, còn check thử 1 a code ngắn ngắn như này thì fail với test case aabb, có khi contest này ko dc tính
u40wsAh.png

1714884554250.png

edit: có vẻ như gcd ko pass dc test case aabb rùi bác ạ. contest này hủy thôi.
vKigGok.png
 
freedom.9 said:
1 anagram là ko quan tâm tới order, chỉ quan tâm tới frequency.
Ví dụ string ban đầu có 4a, 2b, 2c chả hạn thì để tạo ra string ban đầu thì cần dùng 2 string chứa 2a 1b 1c , + nó lại sẽ đc 4a 2b 2c.
Nên cái cần tìm là tìm GCD của tất cả các frequency thôi.

via theNEXTvoz for iPhone
Click to expand...
test yếu thật, t thì là anagram chứ s là concatenation của các anagram của t mà, ví dụ s là aabbabab thì kết quả trả về t = ab thì đúng là từ không xếp được thật, vì làm gì có anagram nào của t ra aa đâu
 
JustAnOtherClone said:
nó có hiện input ko, sao phen ko chơi kiểu cục súc: if(input==="abc") return xyz; cho qua cái case đó đi.
Click to expand...
biết lí do fail test case đấy r, cái hàm check valid anagram e lụm của thằng beat 100% java bỏ vào tránh TLE làm code hỏng vì 1 lí do gì đó éo biết, unit test thì vẫn chạy bth
g8XXj8u.gif
vừa thay cái hàm valid của e tự impl thì pass ngon lành
1BW9Wj4.png
overthinking quá báo, ngựa ngựa chôm code hỏng xôi
 
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 said:
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)
Click to expand...
bài này nhìn đề giống dp thế mà ko dùng dp để giải dc hả bác ?
 
LmaoSuVuong said:
bài này nhìn đề giống dp thế mà ko dùng dp để giải dc hả bác ?
Click to expand...
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 đó
 
Bài 4 greedy nhưng mà ko biết greedy bằng cách nào cả. Nếu nghĩ ra cách tính min cost cho mỗi max value O(1) thì chắc ngon
Mình tính bằng heap nhưng nhận ra là ko chỉ có solution tăng tới max value nên bỏ cuộc luôn =((
1714915971014.png
 

Similar threads

B
thảo luận Project Manager software và những case Study ?
Replies
6
Views
546
codeforfood2015
codeforfood2015
K
tin tức Khởi động giải đấu lập trình “Da Nang Code League 2024” theo chuẩn quốc tế
Replies
0
Views
162
Kisuf
K
TrenTungCaySo7
tin tức Bộ Văn hóa vào cuộc vụ Đàm Vĩnh Hưng cài huy hiệu 'lạ' khi diễn
Replies
9
Views
954
thanhyen95
thanhyen95
Bing AI
  • Locked
Hai thầy trò Lâm Đồng bị từ chối cấp visa sang Mỹ dự Cuộc thi Khoa học kỹ thuật quốc tế
8 9 10
Replies
184
Views
16K
chuoi18_shop
chuoi18_shop
Bing AI
Nhà toán học Việt Nam được hội toán học tại Mỹ ghi nhận 'khởi đầu xuất sắc'
2
Replies
23
Views
2K
yeupanhmaj
yeupanhmaj

Share this page

Back
Top