Hướng dẫn cho SPyofgame Editorial


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

Welcome to my editorial page.



Bình luận


  • 26
    SPyofgame    7:20 p.m. 29 Tháng 4, 2021 đã chỉnh sửa

    Thi thử duyên hải 2021 lần hai bài CPU


    • 24
      SPyofgame    7:49 p.m. 29 Tháng 4, 2021 chỉnh sửa 2

      \(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

      \(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

      \(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)



      \(\color{orange}{\text{Hướng dẫn}}\)

      • Gọi cách chia \(X\) là chia \(2n\) chương trình thành \(n\) cặp \((A_1, B_1), (A_2, B_2), \dots, (A_n, B_n)\)

      Gọi thời gian xử lí của một cặp \((A_i, B_i)\)\(f(A_i, B_i)\)

      Thời gian xử lí toàn bộ chương trình cách chia \(P\)\(g(X) = max(f(A_i, B_i))\)

      Yêu cầu bài toán là tìm \(res = min(g(X)) = min(max(f(A_i, B_i)))\) [1]

      • Với mỗi cặp \((A, B)\)

      Từ [1] ta có \(f(A, B)\) càng nhỏ càng tốt, nên ta phải tìm cách để xử lí 2 chương trình một cách tối ưu

      Khi phát xung nhịp, gọi \(a\) là kí tự đầu của \(A\)\(b\) là kí tự đầu của \(B\)

      Khi \(a = b\) thì ta loại cả \(a\)\(b\) cùng lúc và tăng một đơn vị thời gian

      Khi \(a \neq b\) thì ta sẽ thử loại một trong hai và tăng một đơn vị thời gian


      \(\color{goldenrod}{\text{Tiếp cận}}\)

      • Để xử lí cặp \((A, B)\), ta dùng quy hoạch động đếm

      Xét \(f(i, j)\) là thời gian nhỏ nhất để loại bỏ \(A[i \dots n]\)\(B[j \dots m]\) với \(n = |A|\)\(m = |B|\)

      Khi \(A_i = B_j\) thì \(f(i, j) = f(i + 1, j + 1) + 1\)

      Khi \(A_i \neq B_i\) thì \(f(i, j) = min(f(i + 1, j), f(i, j + 1)) + 1\)

      • Để xử lí \(res = min(max(f(A_i, B_i)))\), ta dùng quy hoạch động trạng thái

      \(2n\) nhỏ, xét \(2^{2n}\) trạng thái \(S\) đánh dấu các chương trình đã được ghép cặp

      Khi xét tới chương trình thứ \(i\) chưa được ghép cặp, ta thử xét trong \(2n\) chương trình còn lại có cái nào chưa ghép cặp ta ghép luôn

      \(g(i, S) = min\Bigg(\ max\bigg(\ g(i + 1, S\ \cup\) {\(\ j\ \(}\)\ )\ \ ,\ \ f(A_i, A_j)\ \bigg)\ \Bigg)\)

      • Khi đó kết quả bài toán sẽ là \(res = min(g(i, S))\)

      \(\color{purple}{\text{Độ phức tạp}}\)

      • Với cách đề cập trên

      Có tất cả \(O(n \times 2^{2n})\) giá trị \(g(i, S)\) cần duyệt qua để tính \(res\)

      Hàm \(g(i, S)\) chuyển trạng thái mất \(|S| \times f(i, j) = 2n \times |A_i| \times |A_j|\)

      Vậy độ phức tạp rơi vào khoảng \(O(2n^2 \times 2^{2n} \times max(|A_i|)^2)\)

      Có thể coi là \(O(2^{2n})\) với hằng số cao

      • Tối ưu

      Ta truyền bitmask thay vì tập đánh dấu

      Ta sẽ tiền xử lí tính toán trước các giá trị \(f(i, j)\)

      Ta sẽ luôn ghép cặp từ thằng \(i\) với các thằng khác, nên biến \(i\) là không quan trọng, vì với mọi \(S\) bất kì ta có thểm tìm được \(i\) tương ứng

      Độ phức tạp lúc này chỉ còn \(O(n^2 \times max(|A_i|)^2 + 2^{2n})\)


      \(\color{green}{\text{Code tham khảo }}\): Approach

      \(^{^{\color{purple}{\text{Độ phức tạp : }} O(2^{2n})\ \color{purple}{\text{thời gian}}\ ||\ O(2^{2n})\ \color{purple}{\text{bộ nhớ}}}}\)

      C++
      const int INF = 0x3f3f3f3f;
      const int LIM = 111;
      
      int n, k;
      string a[111];
      int cost[111][111];
      
      string u, v;
      int f[111][111];
      
      /// Solve for each pair
      int calc(int i = 0, int j = 0)
      {
          if (i >= u.size()) return int(v.size()) - j; /// da xoa het (u), con lai (|v| - j) ki tu cua (v)
          if (j >= v.size()) return int(u.size()) - i; /// tuong tu nhu tren
      
          int &res = f[i][j];
          if (res != -1) return res;
          res = +INF;
      
          res = min(calc(i + 1, j), calc(i, j + 1)) + 1;
          if (u[i] == v[j])
              minimize(res, calc(i + 1, j + 1) + 1);
      
          return res;
      }
      
      int g[1 << 22];
      /// Solve for all pairs
      int solve(int i = 1, int mask = 0)
      {
          if (i > n) return 0;
          if (mask >> i & 1) return solve(i + 1, mask);
      
          int &res = g[mask];
          if (res != -1) return res;
          res = +INF;
      
          for (int j = i + 1; j <= n; ++j)
          {
              if (mask >> j & 1) continue; /// (j) is used
              minimize(res, max(solve(i + 1, mask | (1 << j)), cost[i][j]));
          }
      
          return res;
      }
      
      int main()
      {
          /// Input
          cin >> n;
          k = 1 * n;
          n = 2 * n;
          for (int i = 1; i <= n; ++i)
              cin >> a[i];
      
          /// Precalculating
          for (int i = 1; i <= n; ++i)
          {
              for (int j = i + 1; j <= n; ++j)
              {
                  u = a[i];
                  v = a[j];
                  memset(f, -1, sizeof(f));
                  cost[i][j] = cost[j][i] = calc();
              }
          }
      
          /// Solving
          memset(g, -1, sizeof(g));
          cout << solve();
          return 0;
      }
      
      4 bình luận nữa