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

freedom.9 said:

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

Click to expand...

freedom.9 said:

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

Click to expand...

wibu_that_tinh said:

Mị dùng Kadane đó fen.

Click to expand...

• 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 said:

Đ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++

Click to expand...

freedom.9 said:

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?

Click to expand...

freedom.9 said:

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?

Click to expand...

wibu_that_tinh said:

Chuẩn rồi fen

Click to expand...

Hover said:

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)

Click to expand...

wibu_that_tinh said:

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 đã.

Click to expand...

freedom.9 said:

Đậ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

Click to expand...

freedom.9 said:

Đậ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

Click to expand...

Hover said:

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

Click to expand...

Hover said:

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

Click to expand...

wibu_that_tinh said:

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

Click to expand...

freedom.9 said:

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

Click to expand...

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

Hover said:

Code:

    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.

Click to expand...