Hôm nay có khá nhiều bài trí tuệ.

Tóm tắt đề bài

wash

Cho \(N\) máy giặt và \(M\) máy sấy chạy song song, thời gian giặt là \(A[1..N]\), sấy là \(B[1..M]\) cho từng máy. Tìm thời gian nhỏ nhất để giặt xong \(L\) quần áo.

Giới hạn

\(1 \le N, M \le 10^5\), \(1 \le L \le 10^6\), \(1 \le A[i], B[i] \le 10^9\).

mars

Cho \(N\) nhà kho với sức chứa \(C[1..N]\), ban đầu các nhà kho rỗng. Trong ngày thứ \(i\) (\(1 \le i \le D\)), nhà kho \(j\) nhận thêm \(A[i][j]\) món hàng, đồng thời bạn được chuyển tổng cộng \(d[i]\) món hàng ra khỏi các nhà kho. Việc chuyển ra được thực hiện sau khi nhận hàng. Hỏi sau \(N\) ngày liệu có thể chuyển tất cả hàng hóa đã nhận không?

Giới hạn

\(1 \le N, D \le 30\), \(1 \le C[i], A[i][j], d[i] \le 10^6\)

government

Cho \(N\) điểm, điểm \(i\) có trọng số \(A[i]\). Tìm cách đặt các điểm vào các tọa độ nguyên của đoạn thẳng \([1..M]\) (mỗi tọa độ chứa không quá 1 điểm) để tối đa hóa: \[\sum\limits_{i = 1}^N \sum\limits_{j = i + 1} ^N |x_i - x_j| \times A[i] \times A[j]\]

Với \(x_i\) là tọa độ điểm \(i\).

Giới hạn

\(1 \le M \le 10^6\), \(1 \le N \le 1000\), \(1 \le A[i] \le 100\).

permutation

Xét một hoán vị \(P\), gọi \(R[i]\) là bán kính của \(P_i\) nếu \(R[i]\) là số lớn nhất thỏa mãn:

• \(1 \le i - R[i]\) và \(i + R[i] \le N\)
• \(P_j < P_i\) với mọi \(i - R[i] \le j < i\)
• \(P_j < P_i\) với mọi \(i < j \le i + R[i]\)

Cho số \(N\) và dãy \(R[1..N]\), đếm số hoán vị \(P\) độ dài \(N\) có bán kính của \(P_i\) là \(R[i]\) với mọi \(1 \le i \le N\).

Giới hạn

\(1 \le N \le 1000\).

Lời giải

wash

Tham lam trên một máy

Giả sử bài toán chỉ có một loại máy (máy giặt chẳng hạn, phơi thôi sấy làm gì tốn điện), ta có thể sử dụng thuật toán tham lam: Với mỗi bước ta chọn máy giặt mà có thời điểm hoàn thành đồ tiếp theo (không phải đồ máy đó đang giặt - nếu có) là nhỏ nhất.

Không khó để chứng minh thuật toán này là tối ưu. Việc cài đặt cũng không khó khăn, chỉ cần sử dụng 1 priority_queue.

Độ phức tạp là \(O(L \log N)\).

Mạnh hơn thế, thuật toán này cho ta không chỉ đáp án tối ưu, mà từng phần tử cũng tối ưu: Không thể giặt đồ thứ \(i\) xong trước thời điểm \(T[i]\).

Chặt nhị phân kết quả

Theo tính chất bài toán, ta có thể chặt nhị phân kết quả. Bài toán trở thành kiểm tra, liệu trong thời gian \(X\) có thể giặt và sấy \(L\) quần áo không?

Để kiểm tra, đầu tiên ta sẽ tham lam theo thuật toán trên để có tập thời gian giặt xong của từng đồ, \(T[i]\).

Sau đó, ta “lật ngược” trục trời gian lại, xuất phát từ thời điểm \(L\) và thực hiện tính tập thời gian sấy \(V[i]\), cũng bằng thuật tham lam trên. Tại sao thuật tham lam vẫn đúng? Tại vì, với mỗi máy, ta chỉ cần đảo ngược thứ tự sấy các đồ của máy đó là tổng thời gian vẫn không đổi, các đồ được sấy đúng thứ tự xuôi trục thời gian.

Việc cuối cùng là dựng lên cặp ghép \(T[i]\) - \(V[i]\) sao cho \(i\) ghép với \(j\) thì \(T[i] + V[j] < X\). Ta có thể tưởng tượng là giặt mất \(T[i]\), đợi đến \(X - V[j]\) rồi sấy mất \(V[j]\).

Hiển nhiên cách ghép tối ưu nhất là ghép \(T[i]\) nhỏ nhất với \(V[j]\) lớn nhất, nhỏ nhì với lớn nhì và vân vân…

Ta có thuật toán \(O(L \log N \log 10^{15})\), chưa đủ mạnh.

Khử chặt nhị phân

Ta nhận thấy việc tính mảng \(T[i]\) và \(V[i]\) không liên quan đến việc chặt nhị phân, vì thế thực chất việc chặt nhị phân của ta chỉ là tìm giá trị max của việc ghép cặp.

Như vậy, không cần chặt nhị phân, ta chỉ cần tìm 2 mảng trên, thực hiện ghép cặp rồi tìm giá trị max.

Độ phức tạp là \(O(L \log N)\).

mars

Luồng

Ta có thể để ý, đề bài gồm một số đầu vào, một số đầu ra và yêu cầu kiểm tra xem có thể truyền từ đầu vào sang đầu ra không. Đây chính là đặc điểm của bài toán luồng cực đại - vì thế đây là bài luồng cơ bản.

Ngoài ra, giới hạn nhỏ của đề bài cũng ủng hộ ý tưởng luồng.

Dựng luồng như thế nào?

• Với mỗi ngày ta chỉ có thể giữ lại \(C_i\) đơn vị ở nhà kho \(i\) => Ta sẽ cần phải dựng đỉnh quản lí \(V[i][j]\) quản lí nhà kho \(i\) trong ngày \(j\), từ \(V[i][j]\) đi đến \(V[i][j + 1]\) với capacity \(C_i\).
• Trong ngày \(i\) chỉ được chuyển \(D_i\) đơn vị => Ta dựng đỉnh \(Q[i]\) quản lí lượng chuyển ra trong ngày \(i\). Từ \(Q[i]\) đến đích có capacity \(D_i\), từ các \(V[i][j]\) đến \(Q[j]\) có capacity vô tận.
• Kho \(j\) ngày \(i\) tăng thêm \(A[i][j]\) đơn vị => từ nguồn vào \(V[i][j]\) có capacity \(A[i][j]\).
• Chuyển vào trước khi chuyển ra: để xử lí phần này ta cần tách \(V[i][j]\) thành \(V_in[i][j]\) và \(V_out[i][j]\), từ \(V_out[i][j - 1]\) vào \(V_in[i][j]\) như trên, \(V_out[i][j]\) vào \(Q[j]\) như trên và \(V_in[i][j]\) vào \(V_out[i][j]\) có capacity \(C_i\).

Sau đó ta tìm luồng cực đại và kiểm tra nó có bằng tổng \(A[i][j]\) không.

Độ phức tạp là O(luồng 2000 đỉnh 2000 cạnh).

government

Biến đổi công thức

Ta có thể hiểu công thức chính là khoảng cách có trọng số của từng cặp. Sử dụng công thức này có điểm bất lợi là có quá nhiều biến. Ta sẽ biến đổi công thức một chút.

Giả sử các điểm \(1..N\) đã được xếp từ trái sang phải, đáp số sẽ là \[ \sum\limits_{i = 1}^{N - 1}(x_{i + 1} - x_i) (\sum\limits_{j = 1}^i A[j]) (\sum\limits_{k = i + 1}^N A[k])\]

Với mỗi đoạn liên tiếp, số lần nó bị tính vào đáp số sẽ là tổng trọng số những điểm bến trái nó nhân với tổng trọng số những điểm bên phải.

Dồn về 2 bên

Giả sử ta đã có thứ tự các số \(A[i]\), vậy đặt chúng vào đâu thì hợp lí nhất?

Dựa theo công thức phía trên, ta có:

• Tổng các \((x_{i + 1} - x_i)\) không quá \(M\). Vì ta cần tối đa hóa nên ta coi tổng là \(M\) luôn.
• Vị trí có phần tích \(A[i]\) lớn nhất là khi tổng bên trái và bên phải gần nhau nhất. Gọi vị trí này là \((x_{l + 1} - x_l)\).

Từ đây ta suy ra luôn có thể tối đa hóa đáp án bằng cách tối đa hóa đoạn \(l\), tức cho \((x_{l + 1} - x_l) = M - N + 1\) và các đoạn còn lại là 1. Nói cách khác, ta sẽ dồn tập điểm về 2 bên sao cho tổng trọng số của chúng gần nhau nhất, tức \(l\) lớn nhất thỏa mãn tổng \(A[1..l - 1]\) bé hơn nửa tổng.

Thứ tự của từng bên

Giả sử ta biết tập con của từng bên, làm sao để tìm thứ tự sắp xếp của chúng?

Xét tập bên trái \(A[1..k]\). Dễ dàng nhìn thấy phần đáp số của các đoạn trong tập chính là \[A[1] \times (S - A[1]) + (A[1] + A[2]) \times (S - A[1] - A[2]) + … + (A[1] + … + A[k - 1]) \times (S + A[k])\]

Ta nhận thấy \(A[1]\), \(A[1] + A[2]\), … đều sẽ nhỏ hơn số hạng còn lại tương ứng (theo nhận xét phía trên), vì vậy để tổng các tích này max, thì \(A[1]\), \(A[1] + A[2]\), …, \(A[1] + … + A[k - 1]\) đều phải lớn nhất có thể. Vậy dãy \(A[1..K]\) phải được sắp xếp giảm dần.

Tương tự ta sẽ chứng minh được dãy bên phải phải được sắp xếp tăng dần.

Quy hoạch động

Khi đã biết sắp xếp các phần tử, ta đã có thứ tự quy hoạch động: ta sẽ thêm dần các phần tử vào bên trái hoặc bên phải, theo thứ tự \(A[i]\) giảm dần.

Để có thể vận dụng công thức tính phần giữa, trong hàm qhđ ta cần lưu lại tổng của 1 bên.

Ta có \(f[i][j]\) là tổng đáp số của 2 tập, sao cho tập bên trái có tổng là \(j\), cả 2 tập gồm các phần tử từ 1 đến \(i\), lớn nhất. Ta chuyển trạng thái từ \(f[i][j]\) bằng cách chọn \(i + 1\) vào tập trái hay phải:

• Sang trái: chuyển sang \(f[i + 1][j + A[i + 1]]\), tổng tăng thêm \(j \times (S - j)\).
• Sang phải: chuyển sang \(f[i + 1][j]\), tổng tăng thêm: \((S[i] - j) * (S - S[i] + j)\), với \(S[i]\) là tổng \(A[1..i]\).

Đáp số sẽ là \[ \max\limits_{i = 0}^{S}(f[N][i] + (M - N + 1) \times i \times (S - i))\]

Độ phức tạp là \(O(N^2 * A[i])\).

permutation

Vị trí đặt số \(N\)

Xét dãy \(R_i\). Ta nhận thấy số \(N\) có thể đặt ở \(i\) khi và chỉ khi:

• \(R_i\) phủ đến 1 hoặc đến \(N\).
• Không có \(R_j\) nào phủ \(i\).

Giả sử ta có một vị trí thỏa mãn \(x\). Nếu đặt \(x\) ở \(N\), ta nhận thấy không có \(j < x\) nào mà \(R_j\) phủ qua \(x\), cũng như không có \(j > x\) nào thỏa mãn. Vì thế \(R[1..x - 1]\) và \(R[x + 1..N]\) trở thành 2 bài toán riêng biệt.

Ta có thể giải riêng 2 bài toán này, nhân số cách với nhau, cùng với số cách chọn \(x - 1\) số trong \(N - 1\) số cho tập bên trái (và các số còn lại trong tập bên phải), tức \(C^{x - 1}_{N - 1}\).

Quy hoạch động

Gọi \(f[i][j]\) là số cách điền các số hoán vị thỏa mãn \(R[i..j]\). Ta có:

• \(x\) được gọi là thỏa mãn \(i..j\) nếu:
  • \(i \le x \le j\)
  • \(R_x\) phủ \(i\) hoặc phủ \(j\)
  • Không tồn tại \(i \le k \le j\), \(k \neq x\) mà \(R_k\) phủ \(x\).
• Ta định nghĩa đoạn đúng:
  • \(R[1..N]\) là đoạn đúng nếu không có 2 cặp nào phủ nhau.
  • Đoạn rỗng là đoạn đúng.
  • Nếu \(R[i..j]\) đúng và \(x\) thỏa mãn \(i..j\) thì \(R[i..x-1]\) và \(R[x+1..j]\) là đoạn đúng.
• \(f[i][j] = 1\) nếu \(R[i..j]\) là đoạn đúng và \(i = j\) hoặc \(i = j + 1\).
• \(f[i][j] = \sum\limits_{x \text{ t/m } i..j} f[i][x - 1] \times f[x + 1][j] \times C^{x - 1}_{N - 1}\)

Đáp số là \(f[1][N]\). Độ phức tạp là \(O(N^3)\), do với mỗi đoạn ta cần tìm \(x\) thỏa mãn.

Ta sẽ tối ưu việc lựa chọn này.

Số lượng \(x\) thỏa mãn

Xét đoạn \(i..j\). Gọi \(L[i][j]\) là \(k \le j\) lớn nhất thỏa mãn \(R[k]\) phủ \(i\), \(R[i][j]\) là \(k \ge i\) nhỏ nhất thỏa mãn \(R[k]\) phủ \(j\). Hiển nhiên \(L[i][j]\) phủ tất cả các số phủ \(i\) đứng trước nó, \(R[i][j]\) phủ tất cả các số phủ \(j\) đứng sau nó. Vậy chỉ có \(L[i][j]\) hoặc \(R[i][j]\) có thể thỏa mãn.

Ta có thể tính được 2 mảng này trong \(O(N^2)\), việc còn lại là kiểm tra tính thỏa mãn của 2 phần tử này.

Kiểm tra thỏa mãn

Ta còn điều kiện thỏa mãn: Không có phần tử nào cùng đoạn phủ nó. Ta có thể dựng mảng tính như sau:

• \(S[i][j] = 1\) nếu \(i\) phủ \(j\) và 0 nếu không.
• Ta có thể for trâu từng số và đánh dấu, tổng độ phức tạp sẽ là \(O(N^2 \log N)\) do tính chất của bán kính.
• Khi kiểm tra ta cần tính tổng \(S[ x ][i..j]\). Ta có thể sử dụng mảng tổng dồn để lấy tổng trong \(O(1)\).

Như vậy ta có thuật toán \(O(N^2 \log N)\).