Ngẫm về Ice Cream - VNG

2022, Nov 15    
Category: algorithm

Đề bài

problem

Cho n thùng kem. Mỗi lần lấy kem, có thể lấy nhiều cái kem một lúc, khi lấy hết kem khỏi thùng thì đổ thêm 1 lượng kem bằng 1 nửa (làm tròn xuống) lượng kem vừa lấy ra.

Hỏi sau m lần lấy kem, số lượng kem lớn nhất thu được là bao nhiêu?

Dữ liệu vào

  • Dòng 1: 2 số nguyên dương n - số thùng kem, m - giới hạn số lần phục vụ kem.

  • Dòng 2: n số nguyên dương không âm, số nguyên thứ i là số lượng kem trong thùng thứ i.

Giới hạn: n <= 5*10^5, m <= 10^6.

Dữ liệu ra

1 dòng duy nhất là số kem nhiều nhất có thể lấy ra sau m lần.

Cách giải

Đặt bit_len(n) là hàm tính độ dài của n khi viết dưới dạng nhị phân.

Ví dụ: bit_len(21) = bit_len(0b10101) = 5.

Nếu một thùng kem có số lượng kem ban đầu là x thì ta có thể thao tác lấy + đổ thêm kem (nếu có) trong tối đa bit_len(x) lần.

Ví dụ: x = 7 = 0b111:

  • sau lần lấy đầu tiên, ta sẽ đổ thêm 1 lượng kem là 3 = 0b11
  • sau lần lấy thứ 2, ta sẽ đổ thêm 1 lượng kem là 1 = 0b1
  • sau lần lấy thứ 3, ta không đổ kem vào nữa.

Giả sử 1 thùng kem được mở k lần (k <= bit_len(x)), tổng số lượng kem được lấy ra là

open(x, k) = x + floor(x / 2^1) + floor(x / 2^2) + ... + floor(x / 2^(k-1))

hay

open(x, k) = \sum_{i=0}^{k-1} (x >> i)

Bổ đề 1

Với cùng 1 giá trị k, bit_len(x) càng lớn thì tổng open(x, k) càng lớn.

Với 2 số x1 và x2 thoả mãn bit_len(x1) == bit_len(x2), ta ưu tiên chọn số nào có giá trị lớn hơn.

Chứng minh: Thật vậy, giả sử `x1` viết dưới dạng nhị phân là `b_(p-1) b_(p-2) ... b_0` và `x2` viết dưới dạng nhị phân là `c_(p-1) c_(p-2) ... c_0`. Không mất tính tổng quát, giả sử `x1 < x2`. Chiếu theo định nghĩa so sánh 2 dãy, đặt `i` là vị trí đầu tiên mà `b_i < c_i` (trước đó `b_j == c_j` với mọi `j > i`). - Nếu `k < i`, `(x1 >> j) < (x2 >> j)` với mọi `j <= k`, do vậy `open(x1, k) < open(x2, k)`. - Nếu `k >= i`, `(x1 >> j) < (x2 >> j)` với mọi `j < i` và `(x1 >> j) == (x2 >> j)` với mọi `k >= j >= i`, do vậy `open(x1, k) < open(x2, k)`.

Ví dụ: x1 = 21 = 0b10101, x2 = 23 = 0b10111 -> i = 2.

  • Với k = 1 < i: (x1 >> 0) == 21 < (x2 >> 0) == 23, (x1 >> 1) == 10 < (x2 >> 1) == 11 -> open(x1, k) < open(x2, k)

  • Với k = 2 == i: (x1 >> 0) < (x2 >> 0), (x1 >> 1) < (x2 >> 1), (x1 >> 2) == 5 == (x2 >> 2) == 5 -> open(x1, k) < open(x2, k)

Bổ đề 2

Ta đã chứng minh được bổ đề: với cùng 1 giá trị k, ta luôn ưu tiên chọn thùng kem lớn hơn để lấy ra k lần.

Ta sẽ chuyển sang một bổ đề khác: với k lần lấy kem từ 2 thùng x1 và x2, lấy kem như thế nào cho tối ưu?

Không mất tính tổng quát, giả sử x1 < x2. Đặt q = bit_len(x2) - bit_len(x1).

Nếu q > 0 (hay bit_len(x1) < bit_len(x2)), ta cứ lấy kem từ thùng x2 cho đến khi nào lấy đủ k lần hoặc bit_len(x1) == bit_len(x2). Điều này là dễ thấy vì cùng 1 số lần lấy kem, số kem mỗi lần lấy ra ở thùng lớn thậm chí còn lớn hơn cả số kem ban đầu ở thùng nhỏ. Số lần lấy kem là min(q, k).

Nếu 0 <= q < k, bit_len(x1) == bit_len(x2 >> q). Mỗi lần lấy kem, ta không chỉ lấy kem từ 1 thùng duy nhất mà lựa chọn thùng có số kem lớn hơn để lấy kem.

Lời giải tổng quát cho n cây kem

Từ 2 bổ đề trên, ta rút ra lời giải tổng quát, áp dụng với m bước:

  • Lựa chọn thùng kem có giá trị lớn nhất trong danh sách các thùng kem. Giả sử thùng kem này có số lượng kem là x. Ta lấy hết kem trong thùng đó và đổ thêm 1 lượng kem là floor(x / 2).

  • Cập nhật số lượng kem trong các thùng.

Vì ta chỉ quan tâm đến giá trị lớn nhất trong danh sách các thùng kem nên ta sẽ dùng cấu trúc dữ liệu heap để lưu trữ. Độ phức tạp không gian là O(n) và thời gian lấy kem và đổ thêm kem (nếu có) ở mỗi bước là O(log n).

Mã giả:

heap = {a_i} // tạo heap từ số kem ban đầu của các thùng
ans = 0

for times = 1 -> m:
	x = heap.get_top() // lấy ra giá trị lớn nhất khỏi heap
	ans += x // cập nhật x vào kết quả
	if x > 1:
		heap.push(x >> 1) // đổ thêm kem vào thùng đó

Độ phức tạp tổng là O((n+m) log n).

Twitter Facebook