Phân tích

Thách thức đầu tiên với bài toán Password Problem là hiểu rõ về giá trị kỳ vọng. Khái niệm này xuất hiện rất thường xuyên và cực kỳ hữu ích, vì vậy rất đáng để học. (Chẳng hạn, giá trị kỳ vọng là chìa khóa để giải bài cuối cùng của Chung kết năm 2011!)

Một khi bạn hiểu bài toán yêu cầu gì, bạn chủ yếu cần đánh giá số lần nhấn phím kỳ vọng cho mỗi chiến lược:

• Chiến lược 1: Tiếp tục gõ mật khẩu, sau đó nhấn "enter".

  Xác suất để việc này thành công ngay lần thử đầu tiên là \(x = p_1 \times p_2 \times \dots \times p_A\). Trong trường hợp này, bạn cần \((B - A)\) phím để gõ nốt và \(1\) phím "enter", tổng cộng \(B - A + 1\) lần nhấn phím. Trong trường hợp ngược lại (có ít nhất một lỗi sai), bạn cần \((B - A + 1)\) phím cho lần đầu thất bại, cộng thêm \((B + 1)\) phím để gõ lại toàn bộ và nhấn "enter" lần hai, tổng cộng \(2B - A + 2\) lần nhấn phím. Do đó, số lần nhấn phím kỳ vọng là:

  \[E_1 = (B - A + 1) \times x + (2B - A + 2) \times (1 - x)\]
  \[E_1 = B - A + 1 + (B + 1) \times (1 - x)\]

• Chiến lược 2: Nhấn backspace \(k\) lần (\(1 \le k \le A\)), sau đó thực hiện như Chiến lược 1.

  Xác suất để việc này thành công ngay lần thử đầu tiên là \(x_k = p_1 \times p_2 \times \dots \times p_{A-k}\). Số phím cần thiết nếu thành công là \(k\) (xóa) \(+ (B - (A - k))\) (gõ nốt) \(+ 1\) (enter) \(= B - A + 2k + 1\). Nếu thất bại, số phím là \((B - A + 2k + 1) + (B + 1) = 2B - A + 2k + 2\). Số lần nhấn phím kỳ vọng là:

  \[E_{2,k} = (B - A + 2k + 1) \times x_k + (2B - A + 2k + 2) \times (1 - x_k)\]
  \[E_{2,k} = B - A + 2k + 1 + (B + 1) \times (1 - x_k)\]

• Chiến lược 3: Nhấn enter ngay lập tức và gõ lại toàn bộ mật khẩu.

  Việc này luôn tốn \(1\) (enter ngay) \(+ B\) (gõ lại) \(+ 1\) (enter cuối) \(= B + 2\) lần nhấn phím.

Bài toán yêu cầu tính giá trị nhỏ nhất trong tất cả các giá trị này. Tuy nhiên, còn một điểm cần lưu ý: nếu tính từng \(x_k\) lại từ đầu, chương trình có thể quá chậm. Có thể cần 99999 phép nhân để tính \(x\), 99998 phép nhân để tính \(x_1\), 99997 phép nhân để tính \(x_2\), v.v. Thay vào đó, hãy tính tất cả chúng cùng nhau:

• \(x_0 = p_1 \times p_2 \times \dots \times p_A\)
• \(x_1 = p_1 \times p_2 \times \dots \times p_{A-1}\)
• ...
• \(x_A = 1\) (xóa hết sạch các ký tự đã gõ)

Cách cài đặt

Dưới đây là một giải pháp ngắn gọn bằng Python:

import sys

for tc in xrange(1, int(sys.stdin.readline())+1):
  A, B = [int(w) for w in sys.stdin.readline().split()]
  p = [float(w) for w in sys.stdin.readline().split()]
  best, x = B + 2.0, 1
  for i in xrange(A):
    x *= p[i]
    best = min(best, (B - i) + (A - i - 1) + (B + 1) * (1 - x))
  print 'Case #%d: %f' % (tc, best)

Dữ liệu lớn và lỗi Underflow

Có một chi tiết trong bài toán này có thể khiến nhiều thí sinh gặp lỗi, đó là sự tinh vi trong cách hoạt động của số thực dấu phẩy động (floating point). Giả sử bạn tính \(x_i\) theo cách sau:

• \(x = p_1 \times p_2 \times \dots \times p_A\)
• \(x_1 = x / p_A\)
• \(x_2 = x_1 / p_{A-1}\)
• ...

Thoạt nhìn, cách này có vẻ tương đương với cách trên. Tuy nhiên, nó sai vì hai lý do. Thứ nhất, nếu một trong các giá trị \(p_i\) bằng \(0\), bạn sẽ gặp lỗi chia cho \(0\). Thứ hai, ngay cả số thực dấu phẩy động 64-bit cũng chỉ dành 11 bit cho phần mũ. Điều này có nghĩa là nó không thể lưu trữ các giá trị nhỏ hơn nhiều so với \(2^{-1000}\). Những giá trị cực nhỏ này sẽ bị làm tròn xuống \(0\). Thông thường bạn không quan tâm, nhưng nếu bạn nhân \(100,000\) xác suất với nhau, nó sẽ trở thành vấn đề. Sau khi bị làm tròn về \(0\), tất cả các giá trị \(x\) tiếp theo cũng sẽ là \(0\).

Một số người dùng long double trong C++ để khắc phục, nhưng đó chỉ là may mắn vì long double cũng có giới hạn tương tự. Nếu bạn cần kết hợp nhiều phép nhân và chia mà các giá trị trung gian có thể rất nhỏ, hãy làm việc trong không gian logarit:

A * B / C = exp( log(A) + log(B) - log(C) )

Bạn có thấy vì sao cách tiếp cận này tránh được vấn đề không?

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