Phân tích: New Lottery Game

Trong bài toán này, chúng ta được cho ba số nguyên dương \(A\), \(B\) và \(K\). Chúng ta cần tính số lượng cặp số nguyên \((a, b)\) sao cho:

1. \(0 \le a < A\)
2. \(0 \le b < B\)
3. \((a \text{ AND } b) < K\) (trong đó AND nghĩa là phép bitwise-AND của \(a\) và \(b\)).

Chúng ta sẽ ký hiệu tập hợp các cặp hợp lệ là \(S(A, B, K)\), và số lượng cặp hợp lệ là \(f(A, B, K)\).

Giải quyết Small dataset

Đối với Small dataset, chúng ta có thể đơn giản liệt kê tất cả các cặp \((a, b)\) thỏa mãn hai ràng buộc đầu tiên và đếm xem có bao nhiêu cặp thỏa mãn ràng buộc thứ ba. Hầu hết các ngôn ngữ lập trình đều có sẵn phép toán bitwise-AND, thường là ký tự &. Thủ tục này sẽ có độ phức tạp thời gian là \(O(AB)\), đủ nhanh cho Small dataset. Dưới đây là một ví dụ cài đặt bằng Python 3:

def f(A, B, K):
  return len([(a, b) for a in range(A) for b in range(B) if (a & b) < K])

Giải quyết Large dataset

Chúng ta trình bày hai cách tiếp cận để giải quyết Large dataset. Cách thứ nhất là giải pháp Quy hoạch động tiêu chuẩn (DP trên chữ số/bit) có thể áp dụng cho nhiều bài toán tương tự. Cách tiếp cận thứ hai chia không gian tìm kiếm thành các tập hợp khác nhau và tính toán kích thước của mỗi tập hợp theo cách đệ quy.

Cách tiếp cận thứ nhất

Trước khi đi sâu vào giải pháp thực tế, hãy bắt đầu suy nghĩ về một bài toán đơn giản hơn: cho một số nguyên \(M\), viết một hàm đệ quy để đếm tất cả các số nguyên không âm \(m\) sao cho \(0 \le m < M\). Câu trả lời hiển nhiên là \(M\), nhưng hãy kiên nhẫn vì mục đích của bài toán đơn giản này là để xây dựng trực giác cho hàm Quy hoạch động (DP) mà chúng ta sẽ viết cho bài toán thực tế.

Ý tưởng cốt lõi dựa trên việc đếm số cách tạo ra các bit cho số \(m\), sao cho chúng luôn nhỏ hơn hoặc bằng \(M\) nhưng sau đó chúng ta chỉ đếm những số thực sự nhỏ hơn \(M\). Chúng ta có thể bắt đầu tạo các bit của \(m\) từ bit có ý nghĩa nhất (MSB) đến bit ít ý nghĩa nhất (LSB), và đối với mỗi vị trí bit, chỉ tạo ra các giá trị khả thi. Lưu ý rằng các giá trị khả thi cho bit thứ \(i\) đôi khi có thể là cả 0 và 1, hoặc chỉ là 0.

Giả sử \(M\) là 29 (tức là \(11101_2\) trong hệ nhị phân). Bit có ý nghĩa nhất là bit ở vị trí thứ 4 và bit ít ý nghĩa nhất là ở vị trí thứ 0 như sau:

11101 (M = 29)
^^^^^
|||||
43210 (bit positions 4, 3, 2, 1, 0)

Chúng ta sẽ gọi bit thứ \(i\) là \(m_i\). Giả sử chúng ta đã tạo giá trị 1 cho \(m_4\), giá trị 0 cho \(m_3\), và chúng ta muốn tạo các giá trị khả thi cho bit ở vị trí \(i = 2\). Chúng ta có thể biểu diễn trạng thái hiện tại là: 10cyy, trong đó 1 và 0 là các giá trị chúng ta đã chọn, c là bit hiện tại (thứ \(i\)) chúng ta muốn tạo và y biểu thị các bit chúng ta sẽ cố gắng tạo trong tương lai. Chúng ta gọi các bit ở bên trái vị trí \(i\) là tiền tố (prefix). Tiền tố cho \(m_i = 10cyy\) đang được tạo một phần là 10 (với \(i = 2\)). Bây giờ chúng ta giải thích các quy tắc giúp quyết định các giá trị khả thi để sử dụng cho bit thứ \(i\) là c:

• Quy tắc 1: chúng ta luôn có thể sử dụng giá trị 0 cho bit ở vị trí \(i\).
• Chúng ta có thể sử dụng giá trị 1 cho bit ở vị trí \(i\) nếu:
  • Quy tắc 2a: Tiền tố của các bit trước vị trí \(i\) trong \(m\) (đã được tạo) nhỏ hơn tiền tố của các bit trước vị trí \(i\) trong \(M\), hoặc
  • Quy tắc 2b: Bit thứ \(i\) của \(M\) là 1.

Sử dụng các quy tắc trên, chúng ta có thể đảm bảo rằng tiền tố được tạo cho \(m\) trước vị trí \(i\) sẽ không bao giờ lớn hơn tiền tố của \(M\) trước vị trí \(i\). Hãy khám phá ba tình huống liên quan đến các quy tắc trên:

1. Giả sử trạng thái hiện tại của chúng ta là \(m = 10cyy\) như trước. Chúng ta muốn xác định các giá trị ứng viên cho c. Trong trường hợp này, tiền tố là 10, và tiền tố của \(M\) là 11, do đó cả hai giá trị 0 và 1 đều khả thi. Giá trị 0 luôn khả thi (Quy tắc 1) trong khi từ Quy tắc 2a, giá trị 1 cũng khả thi.
2. Nếu trạng thái hiện tại của chúng ta là \(m = 11cyy\), thì cả hai giá trị 0 và 1 đều khả thi vì giá trị 0 luôn khả thi (Quy tắc 1) trong khi từ Quy tắc 2b, giá trị 1 khả thi.
3. Nếu trạng thái hiện tại của chúng ta là \(m = 111cy\), thì chỉ giá trị 0 là khả thi (Quy tắc 1) nhưng giá trị 1 không khả thi vì cả Quy tắc 2a và Quy tắc 2b đều không được thỏa mãn.

Lưu ý rằng ngay khi tiền tố hiện tại của \(m\) trước vị trí \(i\) nhỏ hơn tiền tố của \(M\) trước vị trí \(i\), chúng ta có thể sử dụng cả hai giá trị 0 và 1 cho các vị trí bit còn lại từ \(i\) xuống 0. Hãy nhớ rằng chúng ta tạo các bit từ bit có ý nghĩa nhất đến thấp nhất (tức là \(i\) giảm dần).

Bây giờ chúng ta tiến hành mô tả việc cài đặt. Chúng ta định nghĩa một hàm đệ quy count(i, lessM, M), trong đó \(i\) là bit thứ \(i\) đang được tạo và lessM là một giá trị boolean cho biết liệu tiền tố của \(m\) trước vị trí \(i\) có nhỏ hơn tiền tố của \(M\) trước vị trí \(i\) hay không.

Như đã lưu ý trước đó, chúng ta bắt đầu tạo số từ bit có ý nghĩa nhất (bit ngoài cùng bên trái) đến bit ít ý nghĩa nhất (bit ngoài cùng bên phải). Do đó, trường hợp cơ sở là khi \(i\) bằng -1, điều này ngụ ý rằng chúng ta đã xây dựng thành công toàn bộ số \(m\). Đối với trường hợp cơ sở, chúng ta trả về 1 nếu số \(m\) được tạo nhỏ hơn \(M\), ngược lại chúng ta trả về 0 (vì chúng ta chỉ muốn đếm những \(m\) thực sự nhỏ hơn \(M\)).

Chúng ta có thể thực hiện Quy hoạch động bằng cách lưu trữ (memoizing) trên các tham số \(i\) và lessM và kết quả. Dưới đây là một ví dụ cài đặt bằng Python 3 (lưu ý rằng lru_cache cung cấp việc ghi nhớ cần thiết):

from functools import lru_cache

def getBit(num, i):
  return (num >> i) & 1  # Returns the i-th bit value of num.

@lru_cache(maxsize = None)
def count(i, lessM, M):
  if i == -1:  # The base case.
    return lessM  # only count if it is strictly less than M.

  maxM = lessM or getBit(M, i) == 1

  res = count(i - 1, maxM, M)  # Value 0 is always feasible. See (1) below.

  if maxM: # Value 1 is feasible if maxM is true. See (2) below.
    res += count(i - 1, lessM, M)  # See (3) below.

  return res

# Prints how many non-negative numbers that are less than 123456789
print(count(31, False, 123456789))

Ghi chú:

• (1): Để tính giá trị boolean của lessM cho bit tiếp theo của \(m\) trong lời gọi đệ quy, chúng ta nhìn vào giá trị của lessM hiện tại. Nếu lessM hiện tại đã là true, thì lessM cho bit tiếp theo trong đệ quy cũng sẽ là true. Một trường hợp khác khi lessM cho bit tiếp theo là true là khi bit thứ \(i\) của \(M\) bằng 1. Vì chúng ta chọn giá trị 0 cho bit hiện tại (\(i\)) trong \(m\) và nó nhỏ hơn bit thứ \(i\) của \(M\) (là 1), điều đó có nghĩa là lessM là true cho bit tiếp theo. maxM nắm bắt những gì chúng ta vừa mô tả, do đó giá trị tiếp theo cho lessM cho bit tiếp theo trong đệ quy được đặt thành maxM.
• (2): Giá trị 1 là khả thi nếu lessM là true (có nghĩa là chúng ta tự do sử dụng cả hai giá trị 0 và 1) hoặc bit thứ \(i\) của \(M\) là 1 (có nghĩa là chúng ta vẫn đang tạo số \(m\) từng phần khả thi nhỏ hơn hoặc bằng \(M\)).
• (3): Giá trị cho lessM trong bit tiếp theo chỉ có thể là true nếu lessM trước đó là true. Nếu lessM hiện tại là false, thì chúng ta biết rằng bit thứ \(i\) của \(M\) là 1. Vì chúng ta đã chọn giá trị 1 cho bit hiện tại, giá trị tiếp theo cho lessM sẽ không thay đổi (vì 1 không nhỏ hơn 1).

Bây giờ, với trực giác trên để tạo các số không âm nhỏ hơn \(M\), chúng ta có thể tổng quát hóa nó để đếm tất cả các cặp \((a, b)\) khả thi lần lượt nhỏ hơn \(A\) và \(B\) và trong đó phép AND bitwise của cặp \((a, b)\) nhỏ hơn \(K\). Chúng ta liệt kê tất cả các giá trị có thể có cho bit hiện tại trong \(a\) và \(b\) (tức là 4 giá trị có thể có (0, 0), (0, 1), (1, 0), (1, 1)) và thêm các ràng buộc mới để đảm bảo rằng phép AND bitwise của cặp \((a, b) < K\).

Mã cho bài toán gốc có phong cách tương tự như trong bài toán đơn giản hơn. Mã được trình bày bên dưới. Mục đích của biến lessA tương đương với lessM, tương tự cho lessB và lessK. Chúng ta cố gắng tạo ra tất cả các giá trị khả thi cho \(a\) và \(b\) và giữ cho \(k\) trong tầm kiểm soát (xem các ghi chú sau).

@lru_cache(maxsize = None)
def countPairs(i, lessA, lessB, lessK, A, B, K):
  if i == -1:  # The base case.
    return lessA and lessB and lessK  # Count those that are strictly less.

  maxA = lessA or getBit(A, i) == 1
  maxB = lessB or getBit(B, i) == 1
  maxK = lessK or getBit(K, i) == 1

  # Use value 0 for a, b, and k which is always possible. See (1).
  count = countPairs(i - 1, maxA, maxB, maxK, A, B, K)

  if maxA:  # Use value 1 for a, and 0 for b and k. See (2).
    count += countPairs(i - 1, lessA, maxB, maxK, A, B, K)

  if maxB:  # Use value 1 for b, and 0 for a and k. See (3)
    count += countPairs(i - 1, maxA, lessB, maxK, A, B, K)

  if maxA and maxB and maxK:  # Use value 1 for a, b, and k. See (4)
    count += countPairs(i - 1, lessA, lessB, lessK, A, B, K)

  return count

Ghi chú:

• (1): Nếu chúng ta chọn 0 cho \(a\) và 0 for \(b\), giá trị cho \(k\) nên là 0 vì \(0 \text{ & } 0 = 0\).
• (2): Nếu chúng ta chọn 1 cho \(a\) và 0 for \(b\), giá trị cho \(k\) nên là 0 vì \(1 \text{ & } 0 = 0\).
• (3): Nếu chúng ta chọn 0 cho \(a\) và 1 for \(b\), giá trị cho \(k\) nên là 0 vì \(0 \text{ & } 1 = 0\).
• (4): Nếu chúng ta chọn 1 cho \(a\) và 1 for \(b\), giá trị cho \(k\) nên là 1 vì \(1 \text{ & } 1 = 1\).

Để tránh tràn số, bạn nên cẩn thận sử dụng số nguyên 64-bit. Ngoài ra, mẫu giải pháp này là một cách tiêu chuẩn để giải quyết các loại bài toán này và có thể được tổng quát hóa cho bất kỳ hệ cơ số nào (chứ không chỉ cơ số 2 như trường hợp trong bài toán của chúng ta).

Độ phức tạp của giải pháp này dựa trên kích thước của bảng DP, ở đây là \(31 \times 2 \times 2 \times 2\).

Cách tiếp cận thứ hai

Chúng ta có thể nhóm các cặp \((a, b)\) trong \(S(A, B, K)\) dựa trên việc \(a\) và \(b\) là số lẻ hay số chẵn, tức là có bit ít ý nghĩa nhất được thiết lập hay không. Mỗi cặp như vậy sẽ được tính trong một trong bốn tập hợp bên dưới (được viết bằng ký hiệu xây dựng tập hợp), vì vậy tổng kích thước của bốn tập hợp sẽ cho chúng ta giá trị \(f(A, B, K)\).

1. \(\{(a/2, b/2) \mid (a, b) \in S(A, B, K) \text{ \&\& } a \text{ chẵn \&\& } b \text{ chẵn}\}\)
   \(= S(\lceil A/2 \rceil, \lceil B/2 \rceil, \lceil K/2 \rceil)\)
2. \(\{(a/2, (b-1)/2) \mid (a, b) \in S(A, B, K) \text{ \&\& } a \text{ chẵn \&\& } b \text{ lẻ}\}\)
   \(= S(\lceil A/2 \rceil, \lfloor B/2 \rfloor, \lceil K/2 \rceil)\)
3. \(\{((a-1)/2, b/2) \mid (a, b) \in S(A, B, K) \text{ \&\& } a \text{ lẻ \&\& } b \text{ chẵn}\}\)
   \(= S(\lfloor A/2 \rfloor, \lceil B/2 \rceil, \lceil K/2 \rceil)\)
4. \(\{((a-1)/2, (b-1)/2) \mid (a, b) \in S(A, B, K) \text{ \&\& } a \text{ lẻ \&\& } b \text{ lẻ}\}\)
   \(= S(\lfloor A/2 \rfloor, \lfloor B/2 \rfloor, \lfloor K/2 \rfloor)\)

Lưu ý rằng trong 4 tập hợp, các giá trị cho \(k\) bị ép buộc. Nếu \(a\) hoặc \(b\) chẵn, \(k\) cũng sẽ chẵn, trong khi nếu cả \(a\) và \(b\) đều lẻ, thì \(k\) cũng lẻ (do phép AND bitwise).

Hãy cung cấp thêm trực giác về 4 tập hợp. Chúng ta chỉ ra điều đó bằng một ví dụ liệt kê các số chẵn. Nếu \(A\) lẻ, ví dụ 7 thì các giá trị \(a\) chẵn có thể là 0, 2, 4, 6. Nếu \(A\) chẵn, ví dụ 8 thì các giá trị \(a\) chẵn có thể cũng là 0, 2, 4, 6. Các số trong biểu diễn nhị phân của chúng là \(000_2, 010_2, 100_2, 110_2\). 4 tập hợp này giống như việc cố định (hoặc loại bỏ) bit ít ý nghĩa nhất (tức là bằng cách dịch phải 1, tức là a >> 1) dẫn đến tập hợp: \(00_2, 01_2, 10_2, 11_2\) tức là các giá trị 0, 1, 2, 3. Giá trị mới cho \(A\) ở đây là 4 (tức là số nguyên đầu tiên lớn hơn 0, 1, 2, 3). Chúng ta tổng quát hóa và nói như sau: Nếu cân nhắc các giá trị chẵn cho \(a\), thì \(A\) mới được cho bởi (A+1) >> 1 (cũng là \(\lceil A/2 \rceil\)). Bằng cách thực hiện một bài tập tương tự cho trường hợp \(a\) lẻ và \(A\) lẻ hoặc chẵn (chúng tôi dành cho người đọc), chúng ta thấy \(A\) mới được cho bởi A >> 1 (cũng là \(\lfloor A/2 \rfloor\)).

4 tập hợp cho chúng ta một thủ tục đệ quy đơn giản để tính \(f(A, B, K)\), vì kích thước của các tập hợp ở vế phải của các phương trình chỉ đơn giản là các lời gọi đến \(f\). Các trường hợp cơ sở thích hợp ở đây là \(f(1, 1, K) = 1\) và \(f(A, B, K) = 0\) nếu bất kỳ giá trị nào trong \(A, B, K\) bằng không. Để biến thủ tục đệ quy này thành một thuật toán hiệu quả, chúng ta có thể ghi nhớ các giá trị đã tính. Điều này có nghĩa là sau khi tính toán một số \(f(A, B, K)\), chúng ta lưu kết quả vào bộ nhớ đệm để các tính toán trong tương lai với cùng các giá trị sẽ mất thời gian hằng số.

Ví dụ cài đặt bằng Python 3:

@lru_cache(maxsize = None)
def f(A, B, K):
    if A == 0 or B == 0 or K == 0:
        return 0
    if A == B == 1:
        return 1
    return f((A+1)>>1, (B+1)>>1, (K+1)>>1) + \
           f((A+1)>>1, B>>1, (K+1)>>1) + \
           f(A>>1, (B+1)>>1, (K+1)>>1) + \
           f(A>>1, B>>1, K>>1)

Phân tích độ phức tạp

Có thể chứng minh bằng quy nạp rằng một lời gọi đệ quy \(f(A', B', K')\) ở độ sâu đệ quy \(n\) có \(A'\) bằng \(\lfloor A / 2^n \rfloor\) hoặc \(1 + \lfloor A / 2^n \rfloor\), và \(B'\) và \(K'\) thỏa mãn các quan hệ tương tự. Từ đó, chúng ta có thể thấy rằng ở một độ sâu đệ quy nhất định có tối đa 8 lời gọi khác nhau đến \(f\). Do các trường hợp cơ sở đã chọn, chúng ta cũng có thể thấy rằng độ sâu đệ quy tối đa là \(O(\log(\max(A, B)))\). Chúng ta kết luận rằng thuật toán là \(O(\log(\max(A, B)))\).

Dựa trên phân tích chính thức của Google Code Jam.