Phân tích

Sau đây là một số thuật toán giải bài toán, theo thứ tự hiệu quả tăng dần.

Mô phỏng trực tiếp

Duyệt từng phút, từ lúc tiệm mở cửa ở thời điểm \(T=0\) cho đến khi khách cuối cùng được phục vụ. Tại thời điểm \(T\), gán khách mới cho tất cả các thợ đang rảnh; một thợ rảnh khi \(T\) là bội số của \(M\) của người đó. Cuối cùng, trả về thợ phục vụ bạn.

public int naiveGetBarberNumber(int N) {
  int customer = 1;
  for (int T = 0; ; T++) {
    for (int barber = 0; barber < B; barber++) {
      if (T % M[barber] == 0) {
        if (customer == N) return barber;
        customer++;
      }
    }
  }
}

Thuật toán này có độ phức tạp thời gian \(O(N\times\max(M)\times B)\), nên sẽ rất chậm ngay cả với dữ liệu nhỏ, vì \(N\) có thể lớn tới \(1\,000\,000\,000\).

Khai thác tính chu kỳ

Xét trường hợp có hai thợ \(B1\) và \(B2\), lần lượt mất 2 và 3 phút để cắt tóc cho một khách.

Tại \(T=6\), cả hai thợ lại cùng rảnh hệt như ở \(T=0\). Vì thế, trong 6 phút tiếp theo ta sẽ thấy đúng mẫu trạng thái rảnh như 6 phút đầu: tại \(T=2+6\), \(B1\) phục vụ khách số \(3+5\); tại \(T=3+6\), \(B2\) phục vụ khách số \(4+5\); cứ như vậy cho tới \(T=6+6\), khi quá trình lại bắt đầu lặp.

Điều đặc biệt của 6 là đây là bội chung nhỏ nhất (BCNN) của \(M1=2\) và \(M2=3\). Ở thời điểm \(T=\operatorname{LCM}(M1,M2)=6\), mọi thợ đều rảnh vì \(T\bmod M=0\) với từng thợ. Có thể tính BCNN của tất cả các \(M\) bằng

và

Ta có thể tận dụng chu kỳ để chỉ mô phỏng một số ít khách. Chẳng hạn, \(M1=2\), \(M2=3\) và bạn đứng thứ \(N=14\). Chu kỳ dài \(\operatorname{LCM}(2,3)=6\). Trong một pha, \(B1\) phục vụ \(6/M1=3\) khách và \(B2\) phục vụ \(6/M2=2\) khách, tổng cộng 5 khách. Do đó bạn được phục vụ trong pha thứ ba. Khi pha thứ ba bắt đầu, bạn đứng thứ tư trong pha vì hai pha trước đã phục vụ 10 khách. Cuối cùng, mô phỏng trực tiếp pha của bạn như lời giải đầu để xác định số thợ.

Vì chỉ mô phỏng một pha, ta chỉ cần mô phỏng nhiều nhất \(\operatorname{LCM}(M1,M2,M3,\ldots)\) phút. Độ phức tạp được cải thiện thành \(O(B\times\operatorname{LCM}(M1,M2,M3,\ldots))\). BCNN của tất cả các \(M\) không vượt quá \(\max(M)^B\); với dữ liệu nhỏ, nó nhỏ hơn \(25^5\).

public int slowGetBarberNumber(int N) {
  int period = M[0];
  for (int i = 1; i < B; i++)
    period = period / gcd(period, M[i]) * M[i];
  int customers_per_phase = 0;
  for (int i = 0; i < B; i++)
    customers_per_phase += period / M[i];
  int N_in_my_phase = N % customers_per_phase;
  return naiveGetBarberNumber(N_in_my_phase != 0
    ? N_in_my_phase : customers_per_phase);
}

Với dữ liệu lớn, \(B\) và các \(M\) có thể rất lớn nên BCNN có thể khổng lồ; cách này không hoạt động.

Tìm kiếm nhị phân

Với một thời điểm \(T\), ta dễ dàng tính số khách đã được gán cho thợ tính đến và bao gồm thời điểm \(T\). Số khách được gán cho thợ \(i\) là \(\lfloor T/M_i\rfloor+1\), nên chỉ cần cộng các giá trị này cho mọi thợ.

public int countServedCustomers(long T) {
  if (T < 0) return 0;
  int served_customers = 0;
  for (int barber = 0; barber < B; barber++)
    served_customers += T / M[barber] + 1;
  return served_customers;
}

Nhờ đó, ta có thể tìm kiếm nhị phân thời điểm \(T\) mà bạn được phục vụ. Sau đó chỉ còn xác định thợ nào trong số các thợ rảnh tại \(T\) sẽ phục vụ bạn.

Cần nhớ rằng nhiều thợ có thể cùng rảnh tại \(T\), nên phải tính cả những khách đứng trước bạn và cũng được phục vụ đúng thời điểm đó. Vì biết bạn sẽ được phục vụ tại \(T\), số khách có thể đứng trước bạn và được phục vụ tại \(T\) nhỏ hơn số thợ đang rảnh. Ta mô phỏng nhóm này sau khi biết số khách đã được phục vụ tính đến và bao gồm \(T-1\). Chính xác hơn, số khách ngồi vào ghế tại \(T\) bằng

Duyệt các thợ rảnh tại \(T\) theo thứ tự số tăng dần; người thứ \(N-\operatorname{countServedCustomers}(T-1)\) trong thứ tự đó là đáp án.

Cận tìm kiếm nhị phân nên là gì?

Với cận trên, hãy tưởng tượng trường hợp xấu nhất: mọi khách đứng trước bạn đều được thợ chậm nhất và duy nhất đang rảnh phục vụ. Vì vậy, chắc chắn bạn đã được phục vụ không muộn hơn \(\max(M)\times N\) phút. Với cận dưới, trường hợp tốt nhất là bạn được phục vụ ngay khi tiệm mở.

Mã dưới đây giả sử tại \(T=\text{high}\) bạn chắc chắn đã được phục vụ hoặc được phục vụ sớm hơn, còn tại \(T=\text{low}\) thì chưa. Do đó giá trị ban đầu của low phải là \(-1\), không phải 0.

Độ phức tạp cuối cùng là \(O(B\times\log(N\times\max(M)))\).

public int fastGetBarberNumber(int N) {
  long low = -1, high = 10000L*N;
  while (low + 1 < high) {
    long mid = (low + high) / 2;
    if (countServedCustomers(mid) < N)
      low = mid;
    else
      high = mid;
  }
  long T = high;
  int customers_served_before = 
    countServedCustomers(T - 1);
  int customers_to_be_served = 
    N - customers_served_before;
  for (int barber = 0; barber < B; barber++) 
    // Is the barber available at time T?
    if (T % M[barber] == 0) {
      customers_to_be_served--;
      if (customers_to_be_served == 0)
        return barber;
    }
}

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