thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

freedom.9 đã nói:

Câu C làm binary search được luôn à ảo thế nhỉ, mình cứ nghĩ cách dùng Kadane tính sum của tụi ko có cái element X. Còn include X vào như nào thì éo biết

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

freedom.9 đã nói:

Câu C làm binary search được luôn à ảo thế nhỉ, mình cứ nghĩ cách dùng Kadane tính sum của tụi ko có cái element X. Còn include X vào như nào thì éo biết

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

wibu_that_tinh đã nói:

Mị dùng Kadane đó fen.

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

• Các đoạn con không chứa X: 1 -> pos - 1 và pos + 1 -> N. Xử lí cái này dùng Kadane tìm tổng nhỏ nhất có thể (min) và tổng lớn nhất có thể (max) rồi thêm các tổng từ min -> max vào tập kết quả.
• Các đoạn con có chứa X: Tìm về hai bên trái phải của pos để tìm đoạn con chứa X có tổng nhỏ nhất có thể (min) và tổng lớn nhất có thể (max) rồi thêm các tổng từ min -> max vào tập kết quả.

wibu_that_tinh đã nói:

Đoạn include X vào thì không cần dùng Kadane fen à.
Thuật của Bu như này:
Giả sử X ở vị trí pos, chia dãy ra làm 2 trường hợp:

• Các đoạn con không chứa X: 1 -> pos - 1 và pos + 1 -> N. Xử lí cái này dùng Kadane tìm tổng nhỏ nhất có thể (min) và tổng lớn nhất có thể (max) rồi thêm các tổng từ min -> max vào tập kết quả.
• Các đoạn con có chứa X: Tìm về hai bên trái phải của pos để tìm đoạn con chứa X có tổng nhỏ nhất có thể (min) và tổng lớn nhất có thể (max) rồi thêm các tổng từ min -> max vào tập kết quả.

Code C++

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

freedom.9 đã nói:

Lol tự dưng mình quên mất cái prefixsum, đi từ pos tới n để tìm max prefixsum trong dãy, đi từ pos - 1 về 0 để tìm min prefixSum trong dãy là tính đc max nhỉ.
Làm ngược lại sẽ tính được min rồi bruteforce?

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

freedom.9 đã nói:

Lol tự dưng mình quên mất cái prefixsum, đi từ pos tới n để tìm max prefixsum trong dãy, đi từ pos - 1 về 0 để tìm min prefixSum trong dãy là tính đc max nhỉ.
Làm ngược lại sẽ tính được min rồi bruteforce?

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

wibu_that_tinh đã nói:

Chuẩn rồi fen

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

Hover đã nói:

Tìm 2 min, 2 max hai bên. Tính sum 2 min, sum 2 max, đẩy range lên X là ra mà thím.
Ví dụ (-2,4) 10 (-3,6) -> (5,20)

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

wibu_that_tinh đã nói:

Cảm ơn fen @freedom.9 nhé, gần 1 năm không chơi Codeforces tự nhiên lướt forum thấy có thread vui quá nên comeback. Mất cả năm nằm thẳng đánh LOL tù hết người.
Cố gắng chăm chỉ tí lên CM cho thỏa mãn cái đã.

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

freedom.9 đã nói:

Đậu xanh skill issue rồi, tự dưng quên mẹ mất cái prefix sum để tính.
Câu 2 chỗ chia cho 7 nhìn ko ra, tụi này toàn cho toán ngọng quá thật buồn

Ờ nhỉ, đơn giản vậy mà ko nghĩ ra nhưng mà trường hợp như max sum bên trái âm mà bên phải dương thì sao fence nhỉ.


1 năm nằm thẳng mà giải 4Q Div 2 như nhai kẹo thế này

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

freedom.9 đã nói:

Đậu xanh skill issue rồi, tự dưng quên mẹ mất cái prefix sum để tính.
Câu 2 chỗ chia cho 7 nhìn ko ra, tụi này toàn cho toán ngọng quá thật buồn

Ờ nhỉ, đơn giản vậy mà ko nghĩ ra nhưng mà trường hợp như max sum bên trái âm mà bên phải dương thì sao fence nhỉ. Mình nghĩ phải dùng combination chỗ này.


1 năm nằm thẳng mà giải 4Q Div 2 như nhai kẹo thế này

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

Hover đã nói:

Chưa hiểu ý thím lắm. Max sao âm được, tối thiểu nó là 0 (dãy rỗng).

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

Hover đã nói:

Chưa hiểu ý thím lắm. Max sao âm được, tối thiểu nó là 0 (dãy rỗng).

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

wibu_that_tinh đã nói:

Nghỉ thôi các fence, tối 28 chiến tiếp.

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

freedom.9 đã nói:

Ae xài Python codeforces hạn chế xài set nhé, xài list thôi chấp nhận value bị trùng cũng được
Code của mình bị nó hack TLE, nếu đoạn prices = sorted(list(a + b)) thì pass

Python:

from bisect import bisect_left, bisect_right
 
 
t = int(input())
 
def solve():
    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a = sorted(a)
    b = sorted(b)
    prices = sorted(set(a + b))
    ans = 0
    for price in prices:
        totalBought = N - bisect_left(b, price)
        boughtWithPossitiveReviews = N - bisect_left(a, price)
        if totalBought - boughtWithPossitiveReviews <= K:
            ans = max(ans, price* totalBought)
 
    return ans
 
for _ in range(t):
    print(solve())

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

    a = sorted(a)
    b = sorted(b)
    prices = sorted(set(a + b))

Hover đã nói:

Mã:

    a = sorted(a)
    b = sorted(b)
    prices = sorted(set(a + b))

Thím dùng nhiều hàm built in lồng nhau thế này nhìn hơi rợn, cảm giác không biết bên trong nó làm có tối ưu không.
Nghe thím nói bị hack mình cũng không bất ngờ lắm.
Tiện tay thì code nhanh đoạn merge 2 list thôi.

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