Editorial for Bedao Regular Contest 02 - 8ROOKS


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Subtask 1:

Nếu biểu diễn cách xếp cờ bằng ~1~ chuỗi có ~8~ ký tự như trong đề thì với mọi cách xếp cờ thỏa mãn chuỗi này luôn là ~1~ hoán vị của các số từ ~1 → 8~.

Sinh mọi hoán vị của các số từ ~1 → 8~ rồi đếm số thao tác ít nhất để xếp bàn cờ thành ~1~ trong ~8!~ hoán vị

Độ phức tạp: ~O(8! \times 8 \times q)~.

Subtask 2:
  • k = 1

Gọi ~cnt_i~ là số con xe nằm ở hàng ~i~.

Mỗi lượt di chuyển của một con xe tương ứng với chuyển từ ~cnt_i~ sang ~cnt_{i-1}~ hoặc ~cnt_i~ sang ~cnt_{i+1}~ đúng ~1~ đơn vị ( Chú ý nếu ~i=1~ thì chuyển qua trái sẽ là chuyển tới ~cnt_8~, tương tự ~i=8~ chuyển qua phải sẽ là ~cnt_1~ )

Xem các quân xe là cục đá, lúc này, bài toán trở thành cho một vòng tròn có độ dài ~8~, ô thứ ~i~ có ~cnt_i~ cục đá. Mỗi lần có thể chọn ~i~ bất kì, chuyển ~1~ cục đá qua trái hoặc phải của ~i~ trên vòng tròn. Tính số bước ít nhất để ~cnt_i = 1 (1 \leq i \leq 8)~

Giả sử, bài toán ở trên một dãy chứ không phải vòng tròn. Ta sẽ có thuật tham lam như sau:

Nhận xét: để ~cnt_1 = 1~, thì nếu ~cnt_1 = 0~, thì ~cnt_1~ chỉ có thể nhận đá ở những ô bên phải. Nếu ~cnt_1 > 1~ thì phải chuyển đi ~cnt_1 - 1~ cục đá đang ở ô này qua các ô sau.

Từ nhận xét trên, ta duyệt ~i~ từ ~1~ đến ~8~:

  • Ta lưu biến ~num~ là tượng trưng cho số đá đang ở ~i~ cần di chuyển. Nếu ~num < 0~ nghĩa là cần chuyển từ phải sang, ngược lại là cần chuyển từ trái sang. Gọi ~ans~ là kết quả, ta có:

~num = num + cnt_i - 1~

~ans = ans + |num|~

Đó là thực hiện trên dãy, còn trên vòng tròn thì sao ?

Với những bài thao tác trên vòng tròn, ta sẽ nghĩ tới việc cắt vòng tròn ra và thực hiện trên một dãy. Ta sẽ duyệt ~i~ từ ~1~ đến ~8~ thể hiện cho mình sẽ không được chuyển qua trái ở thằng ~i~. Và bài toán lại trở thành bài trên dãy, ta sẽ tính và lấy min kết quả.

Độ phức tạp: ~O(Q \times 8^2)~

Subtask 3:

Sử dụng quy hoạch động trạng thái:

Vì bàn cờ tương đối nhỏ, chúng ta có thể sử dụng bitmask để biểu diễn các quân xe, nếu dòng ~i~ có quân xe thì bit thứ ~i = 1~, ngược lại nếu dòng i trống thì bit thứ ~i = 0~.

Gọi ~dp[n][mask]~ là số thao tác tối thiểu để xếp lại ~n~ cột đầu tiên của bàn cờ sao cho:

  • Không quân xe nào cùng dòng trong ~n~ cột đầu tiên.
  • bitmask biểu diễn ~n~ cột đầu tiên = mask.

Dễ thấy ~n~ bằng số bit bật của mask nên trong thực tế chúng ta có thể vứt chiều này đi, đáp án sau cùng là ~dp[2^8-1]~. Thuật này chạy trong khoảng ≈ ~1024~ phép tính.

Ta tiến hành loại bỏ trường hợp thừa: vì số query lên tới ~1000000~, nếu sử dụng dp bitmask cho mọi query thì không thể đảm bảo chương trình chạy trong ~1~ giây.

  • Nhận xét: ~2~ chuỗi biểu diễn bàn cờ mà là hoán vị của nhau thì đáp án luôn giống nhau (ví dụ : ~12121212~ và ~22112211~, ~12345672~ và ~12234567~,...).
  • Do mọi chuỗi đều có thể xếp thành một chuỗi không giảm (ví dụ : ~12121212~ thành ~11112222~, ~12345672~ thành ~12234567~,...) nên ta chỉ xét các chuỗi không giảm khác nhau, bằng công thức chia kẹo ta biết có khoảng ~6500~ chuỗi như thế.

hình

Vậy từ các nhận xét trên ta có thể:

  • Duy trì ~1~ map ( STL của C++ ) để lưu kết quả của các truy vấn cũ.
  • Với mỗi truy vấn, xếp lại chuỗi thành một chuỗi không giảm, gọi chuỗi này là ~S~.
  • Nếu ~S~ chưa từng xuất hiện trong map ta chạy dp bitmask rồi nhét kết quả vào map theo dạng key = ~S~ và value = ~dp[2^8-1]~, thao tác này phải chạy tối đa ~6500~ lần.
  • Nếu ~S~ đã từng xuất hiện, ta lấy value kết quả tương ứng với key = ~S~ trong thời gian tối đa là ~\log_2{(6500)}~.

Độ phức tạp: ~O(6500 \times 1024 + \log_2{(6500)} \times q)~.

Sử dụng tham lam:

  • k ~\leq~ ~10^9~

Xét các ô từ ~0~ đến ~7~

Nhận thấy từ phần tử ~i~ thì ta sẽ đi được tới ~(i + k) \% 8~, ~(i + 2 * k) \% 8~, ~\dots~, cho tới khi quay lại ô ~i~.

Ta sẽ tách các dãy như trên ra thành một số dãy độc lập với nhau. Và mỗi dãy làm thuật giống với với subtask 2: k = 1.


Lưu ý:

  • Để tăng tốc độ xử lý, vì mọi chuỗi có ~8~ ký tự trong khoảng từ ~1 → 8~, bạn nên chuyển chúng về dạng int trước khi lưu vào map.
  • Bài toán có thể AC hoàn toàn bằng tham lam, quy hoạch động, BFS và meet in the middle.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.