Hướng dẫn giải của Lưới lục giác
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Subtask 1: ~k \le 5~ và tổng ~n~ không vượt quá ~15~
Giải hệ phương trình, đặt lượng thêm vào mỗi hàng là một biến, tổng cộng có ~6n + 3~ biến. Mỗi ô trên lưới ứng với một phương trình ~q + r + s + a = 0~, tổng cộng có ~3n^2 + 3n + 1~ phương trình.
Đây là hệ phương trình tuyến tính do đó có thể sử dụng khử gauss để tìm ra tất cả các nghiệm. Duyệt qua toàn bộ trường hợp của các biến tự do ta có thể xây dựng được tất cả các nghiệm có thể. Số nghiệm của bài khoảng ~k^3~ do ma trận có hạng(rank) ~6n~ (chứng minh ở sau).
Độ phức tạp: ~\mathcal{O}(n^4k^3)~
Subtask 2: ~k \le 5~
Có thể thấy bước khử gauss chỉ giúp ta tìm ra một bộ "ba hàng tự do" – ba hàng mà khi cố định lượng tăng lên thì lượng tăng lên ở các hàng còn lại cũng được xác định. Ta có thể chọn bộ ~\{\texttt{(0 r)}, \texttt{(-1 r)}, \texttt{(0 s)}\}~ khi đó ta có thể xác định lượng tăng của tất cả hàng thuộc trục ~\texttt{q}~, ~\texttt{s}~:
Các hàng nét liền là các hàng cố định, các hàng nét đứt là các hàng được xác định sau một số thao tác. Nếu cứ tiếp tục như vậy, ta có thể xác định hết tất cả hàng thuộc trục ~\texttt{q}~ và ~\texttt{s}~. Vậy còn trục ~\texttt{r}~? Dễ thấy rằng lúc này các hàng trục ~\texttt{r}~ còn lại không giao nhau, nên chỉ có duy nhất một lựa chọn hợp lệ để tất cả các ô trên hàng đó bằng ~0~ do đó các hàng này cũng được xác định giá trị cần thêm.
Độ phức tạp: ~\mathcal{O}(n^2k^3)~
Do giới hạn thời gian không quá chặt, một số cách tối ưu bước khử gauss từ Subtask 1 có thể qua được Subtask này.
Subtask 3: Tổng ~k~ không vượt quá ~500~
Nhận xét: Ta luôn có thể chuyển đổi từ một lời giải sang một lời giải khác bằng cách thêm tất cả hàng của trục ~\texttt{q}~ một lượng ~\Delta q~, thêm tất cả hàng của trục ~\texttt{r}~ một lượng ~\Delta r~, thêm tất cả hàng của trục ~\texttt{s}~ một lượng ~\Delta s~ sao cho ~\Delta q + \Delta r + \Delta s \equiv 0~. Do đó
Việc cố định ~\texttt{(q, 0)}~ là không cần thiết do việc tăng ~\texttt{(q, 0)}~ ứng với tăng ~\Delta q~, ta có thể cố định từ đầu là ~0~ sau đó duyệt các bộ ~(\Delta q, \Delta r, \Delta s)~ hợp lệ.
Tương tự, việc cố định ~\texttt{(r, 0)}~ cũng không cần thiết, ta có thể cố định là ~0~ và để ~\Delta r~ thực hiện nhiệm vụ còn lại.
Như vậy ta chỉ còn đúng một hàng cần duyệt ~\texttt{(r, 1)}~ để tìm ra ~k~ phương án. Với mỗi phương án hợp lệ, ta duyệt lần lượt các bộ ~(\Delta q, \Delta r, \Delta s)~ hợp lệ, có tổng cộng ~k^2~ bộ với mỗi phương án.
Độ phức tạp: ~\mathcal{O}(k(n^2 + k^2))~
Subtask 4: Không có ràng buộc gì thêm
Đặt lượng tăng ở hàng ~\texttt{(r, 1)}~ là ~x~. Khi đó ta có thể giải ra tất cả các hàng còn lại dưới dạng ~ax + b~.
Nếu chỉ quan tâm đến hệ số ~a~ thì:
Dễ thấy các hệ số ~a~ chỉ chênh nhau ~1~ giữa các hàng liên tiếp trên cùng một trục. Do đó nếu ~k \ge 2n + 1~, các hệ số ~a~ hoàn toàn khác nhau, do đó với mỗi cặp hàng, tồn đại một và chỉ một ~x~ để chúng bằng nhau. Gọi một "nhóm" là một tập hợp cực đại các hàng có giá trị bằng nhau ở một ~x~ xác định. Dễ thấy có tối đa ~n^2~ "nhóm" như vậy.
Nhận xét rằng luôn tồn tại lời giải tối ưu chứa ít nhất một "nhóm", và ta có thể xử lý từng nhóm với độ phức tạp ~\mathcal{O}(n)~ trong trường hợp xấu nhất (các nhóm xuất hiện ở các ~x~ khác nhau).
Độ phức tạp: ~\mathcal{O}(n^3)~, lưu ý rằng hằng số ở cách này khá lớn.
Với ~k < 2n + 1~ ta chỉ cần sử dụng lời giải của subtask 3.
#include <bits/stdc++.h> using namespace std; const int N = 201 + 5; const int M = 5e5 + 5; int MOD; int n, k, numCell, a[2 * N][2 * N]; array<int, 2> coor[M]; int powmod(int a, int b) { int res = 1; while (b) { if (b & 1) res = 1LL * res * a % MOD; a = 1LL * a * a % MOD; b >>= 1; } return res; } int inv(int a) { return powmod(a, MOD - 2); } inline void add(int &x, const int &y) { x += y; if (x >= MOD) x -= MOD; } inline void sub(int &x, const int &y) { x -= y; if (x < 0) x += MOD; } void solve() { cin >> n >> k; MOD = k; numCell = 3 * (n + 1) * (n + 1) - 3 * (n + 1) + 1; int index = 0; for (int x = -n; x <= n; ++x) { int y = n - max(0, x); int num = 2 * n + 1 - abs(x); for (int i = 0; i < num; ++i) { cin >> a[x + n][y - i + n]; coor[index++] = {x, y - i}; } } vector<array<int, 2>> dx(2 * n + 1, {-1, -1}), dy(2 * n + 1, {-1, -1}), dz(2 * n + 1, {-1, -1}); dz[n] = {0, 0}; dz[n - 1] = {MOD - 1, 0}; dx[0] = {0, 0}; int curX = 0, curY = 2 * n; dy[curY][0] = 0; sub(dy[curY][0], dx[curX][0]); sub(dy[curY][0], dz[n][0]); dy[curY][1] = 0; sub(dy[curY][1], a[curX][curY]); sub(dy[curY][1], dx[curX][1]); sub(dy[curY][1], dz[n][1]); for (int i = 1; i <= 2 * n; ++i) { ++curX, --curY; dx[curX][0] = 0; sub(dx[curX][0], dy[curY + 1][0]); sub(dx[curX][0], dz[n - 1][0]); dx[curX][1] = 0; sub(dx[curX][1], a[curX][curY + 1]); sub(dx[curX][1], dy[curY + 1][1]); sub(dx[curX][1], dz[n - 1][1]); dy[curY][0] = 0; sub(dy[curY][0], dx[curX][0]); sub(dy[curY][0], dz[n][0]); dy[curY][1] = 0; sub(dy[curY][1], a[curX][curY]); sub(dy[curY][1], dx[curX][1]); sub(dy[curY][1], dz[n][1]); } // check if solution exists for (int x = -n; x <= n; ++x) { for (int y = -n; y <= n; ++y) { int z = -(x + y); if (abs(z) > n) { continue; } array<int, 2> req = {0, 0}; sub(req[0], dx[x + n][0]); sub(req[0], dy[y + n][0]); sub(req[1], a[x + n][y + n]); sub(req[1], dx[x + n][1]); sub(req[1], dy[y + n][1]); if (dz[z + n][0] == -1) { dz[z + n] = req; } else if (dz[z + n] != req) { cout << "-1\n"; return; } } } int best = -1; int bestVal, bestX, bestY, bestZ; int cntSol = 0; // for counting number of solutions if (k < 2 * n + 1) { vector<int> fx(k), fy(k), fz(k); for (int val = 0; val < k; ++val) { auto process = [&](vector<int> &f, const vector<array<int, 2>> &d) { fill(f.begin(), f.end(), 0); for (auto [a, b] : d) { ++f[(1ll * a * val + b) % MOD]; } reverse(f.begin() + 1, f.end()); // f => -f }; process(fx, dx); process(fy, dy); process(fz, dz); for (int x = 0; x < k; ++x) { for (int y = 0; y < k; ++y) { int z = (2 * MOD - x - y) % MOD; if (best < fx[x] + fy[y] + fz[z]) { best = fx[x] + fy[y] + fz[z]; bestVal = val; bestX = x; bestY = y; bestZ = z; cntSol = 1; } else if (best == fx[x] + fy[y] + fz[z]) { ++cntSol; } } } } } else { // k >= 2 * n + 1; vector<array<int, 3>> fx, fy, fz; vector<int> pairsToSize((2 * n + 1) * (2 * n) / 2 + 1, -1); for (int i = 1; i <= 2 * n + 1; ++i) { int val = i * (i - 1) / 2; assert(val < pairsToSize.size()); pairsToSize[val] = i; } auto precalc = [&](vector<array<int, 2>> &d, vector<array<int, 3>> &f) { map<array<int, 2>, int> cnt; for (int i = 0; i <= 2 * n; ++i) { for (int j = i + 1; j <= 2 * n; ++j) { int a = 0, b = 0; add(a, d[i][0]); sub(a, d[j][0]); add(b, d[i][1]); sub(b, d[j][1]); assert(a != 0); int val = 1ll * (MOD - b) * inv(a) % MOD; int x = (1ll * d[i][0] * val + d[i][1]) % MOD; x = (MOD - x) % MOD; ++cnt[{val, x}]; } } for (auto [key, val]: cnt) { assert(val < pairsToSize.size() && pairsToSize[val] != -1); val = pairsToSize[val]; if (val > 1) { f.push_back({key[0], key[1], val}); } } }; precalc(dx, fx); precalc(dy, fy); precalc(dz, fz); vector<int> cntX(k, 0), cntY(k, 0), cntZ(k, 0); vector<int> candidateX, candidateY, candidateZ; vector<int> candidateX1, candidateY1, candidateZ1; while (fx.size() > 0 || fy.size() > 0 || fz.size() > 0) { int curVal = 0; if (fx.size() > 0) curVal = max(curVal, fx.back()[0]); if (fy.size() > 0) curVal = max(curVal, fy.back()[0]); if (fz.size() > 0) curVal = max(curVal, fz.back()[0]); candidateX.clear(); candidateY.clear(); candidateZ.clear(); candidateX1.clear(); candidateY1.clear(); candidateZ1.clear(); while (fx.size() > 0 && fx.back()[0] == curVal) { candidateX.push_back(fx.back()[1]); fx.pop_back(); } while (fy.size() > 0 && fy.back()[0] == curVal) { candidateY.push_back(fy.back()[1]); fy.pop_back(); } while (fz.size() > 0 && fz.back()[0] == curVal) { candidateZ.push_back(fz.back()[1]); fz.pop_back(); } for (int i = 0; i <= 2 * n; ++i) { int x = (1ll * dx[i][0] * curVal + dx[i][1]) % MOD; x = (MOD - x) % MOD; if (++cntX[x] == 1) { candidateX1.push_back(x); } int y = (1ll * dy[i][0] * curVal + dy[i][1]) % MOD; y = (MOD - y) % MOD; if (++cntY[y] == 1) { candidateY1.push_back(y); } int z = (1ll * dz[i][0] * curVal + dz[i][1]) % MOD; z = (MOD - z) % MOD; if (++cntZ[z] == 1) { candidateZ1.push_back(z); } } auto updateAns = [&](int x, int y, int z, int cnt) { if (best < cnt) { best = cnt; bestVal = curVal; bestX = x; bestY = y; bestZ = z; cntSol = 1; } else if (best == cnt) { cntSol++; } }; for (auto x: candidateX) { for (auto y: candidateY1) { int z = 0; sub(z, x); sub(z, y); updateAns(x, y, z, cntX[x] + cntY[y] + cntZ[z]); } } for (auto y: candidateY) { for (auto z: candidateZ1) { int x = 0; sub(x, y); sub(x, z); updateAns(x, y, z, cntX[x] + cntY[y] + cntZ[z]); } } for (auto z: candidateZ) { for (auto x: candidateX1) { int y = 0; sub(y, x); sub(y, z); updateAns(x, y, z, cntX[x] + cntY[y] + cntZ[z]); } } for (int x: candidateX1) { cntX[x] = 0; } for (int y: candidateY1) { cntY[y] = 0; } for (int z: candidateZ1) { cntZ[z] = 0; } } } // x, y, z => r, s, q cout << 6 * n + 3 - best << '\n'; cerr << "n = " << n << " k = " << k << " best = " << best << " cntSol = " << cntSol << endl; for (int i = 0; i < 2 * n + 1; ++i) { int r = (1ll * bestVal * dx[i][0] + dx[i][1] + bestX) % MOD; int s = (1ll * bestVal * dy[i][0] + dy[i][1] + bestY) % MOD; int q = (1ll * bestVal * dz[i][0] + dz[i][1] + bestZ) % MOD; if (r) cout << i - n << " r " << r << '\n'; if (s) cout << i - n << " s " << s << '\n'; if (q) cout << i - n << " q " << q << '\n'; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if (fopen("hexagrid.inp", "r")) { freopen("hexagrid.inp", "r", stdin); } int t; cin >> t; while (t--) { solve(); } return 0; } /* 3 1 3 0 0 0 2 0 1 1 1 2 1 1 0 1 0 1 0 2 7 6 6 5 4 2 5 3 1 6 0 2 1 5 6 6 2 4 4 5 */
Bình luận