Phân tích: Increasing Speed Limits

Đây là bài toán khó của vòng 1C, với 398 người giải được bộ dữ liệu nhỏ và 49 người giải được bộ dữ liệu lớn trong suốt cuộc thi.

Bài toán yêu cầu chúng ta đếm số lượng dãy con tăng nghiêm ngặt của dãy ban đầu. Điều này rất phù hợp với một giải pháp quy hoạch động cho dữ liệu nhỏ.

Gọi \(f(x)\) là số lượng dãy con tăng nghiêm ngặt kết thúc tại vị trí \(x\) và \(S[x]\) là giá trị của dãy tại vị trí \(x\). Tại bất kỳ vị trí \(x\) nào, chúng ta có thể coi \(S[x]\) là một dãy con độ dài 1, hoặc kết nối nó vào bất kỳ dãy con nào đã kết thúc ở các vị trí trước đó có giá trị nhỏ hơn \(S[x]\). Do đó, bạn có thể làm điều gì đó như thế này để tìm xem có bao nhiêu dãy con tăng nghiêm ngặt kết thúc tại mỗi chỉ số.

(Lưu ý: Phân tích gốc mô tả \(f(x)\) bắt đầu tại \(x\), nhưng cách tiếp cận phổ biến và mã nguồn dưới đây thực hiện theo hướng kết thúc tại \(x\)).

f(x) = 1
for i = n to 1
  f(i) = 1
  for j = i + 1 to n
    if S[i] < S[j]
      f(i) = f(i) + f(j)

Sau khi thực hiện việc đó, việc giải bài toán ban đầu chỉ là vấn đề tính tổng số cách tạo ra một dãy con tăng nghiêm ngặt kết thúc tại mỗi vị trí.

Chìa khóa để giải bộ dữ liệu lớn là nhận ra chúng ta có thể làm cho vòng lặp bên trong chạy nhanh hơn nhiều. Những gì chúng ta thực sự muốn làm là tính tổng tất cả các \(f(j)\) trước đó mà \(S[j] < S[i]\). Đây là một bài toán cây điển hình. Có một số cấu trúc dữ liệu cây bạn có thể sử dụng bao gồm Binary Indexed Tree (Cây chỉ số nhị phân - BIT), Segment Tree (Cây phân đoạn), hoặc Binary Search Tree (Cây tìm kiếm nhị phân), để kể tên một số loại, cho phép bạn giải bài toán trong thời gian \(O(n \log n)\) cho mỗi bộ test.

Hai loại cây đầu tiên khá dễ cài đặt mặc dù chúng có một chút phức tạp vì chúng sử dụng lượng bộ nhớ tỷ lệ thuận với giá trị tối đa trong dãy. May mắn thay, điều này có thể được giải quyết bằng cách chuẩn hóa \(S\) để chỉ chứa các giá trị từ \(0\) đến \(n-1\) mà không làm thay đổi tính chất \(S[i] < S[j]\) cho bất kỳ \(i\) và \(j\) nào. Điều này có thể được thực hiện bằng cách thay thế \(S[i]\) bằng thứ hạng của nó trong danh sách đã sắp xếp của các giá trị \(S\) duy nhất.

Dưới đây là một bản cài đặt các ý tưởng này bằng C++.

#define MAXN (1<<20)
int sum_bit[MAXN];

int sum_bit_get(int x)
{
  int ret = 0;
  for(int i = x | MAXN; i < 2 * MAXN; i += i & -i)
    ret = (ret + sum_bit[i ^ MAXN]) % 1000000007;
  return ret;
}

void sum_bit_add(int x, int v)
{
  for(int i = x | MAXN; i; i &= i - 1)
    sum_bit[i ^ MAXN] = (sum_bit[i ^ MAXN] + v) % 1000000007;
}

int S[1000000];
int S2[1000000];

int main()
{
  int T; cin >> T;
  long long X, Y, Z, A[100];
  for(int t = 1; t <= T; t++) {
    int n, m; cin >> n >> m >> X >> Y >> Z;
    for(int i = 0; i < m; i++) cin >> A[i];

    // Generate S
    for(int i = 0; i < n; i++) {
      S[i] = A[i % m];
      A[i % m] = (X * A[i % m] + Y * (i + 1)) % Z;
    }

    // Normalize S
    memcpy(S2, S, sizeof(S));
    sort(S2, S2+n);
    for(int i = 0; i < n; i++)
      S[i] = lower_bound(S2, S2+n, S[i]) - S2;

    // Calculate f(i) and sum them in to result.
    int result = 0;
    memset(sum_bit, 0, sizeof(sum_bit));
    for(int i = n - 1; i >= 0; i--) {
      int add = 1 + sum_bit_get(S[i] + 1);
      sum_bit_add(S[i], add);
      result = (result + add) % 1000000007;
    }

    cout << "Case #" << t << ": " << result << endl;
  }
  return 0;
}

Ngoài các loại cây, còn có một giải pháp "hacker" \(O(n \sqrt{n})\). Ý tưởng đằng sau nó tương tự như ý tưởng được đề cập trong lời giải 1 của bài Mousetrap (từ Vòng 1B), trong đó, ngoài việc duy trì giá trị tại mỗi vị trí, chúng ta duy trì tổng cho các khoảng có độ dài \(\sqrt{n}\). Các bảng này có thể được duy trì trong thời gian hằng số và mất thời gian \(\sqrt{n}\) để truy vấn.

Thông tin thêm:
Binary Indexed Tree

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