Tàu vũ trụ

Lời giải: Tàu vũ trụ

Nhận xét quan trọng

Chuỗi nút nhấn hợp lệ của Bessie có cấu trúc đặc biệt: khi nhấn nút $x$, tất cả các nút nhỏ hơn $x$ được "reset" và có thể dùng lại, nhưng nút $x$ trở nên không hợp lệ cho đến khi có nút lớn hơn được nhấn. Điều này có nghĩa là tập hợp các nút đang "hoạt động" luôn có dạng một tập hậu tố (suffix) liên tục không có lỗ hổng, và đây chính là cấu trúc của số Zeckendorf trong hệ đánh số đặc biệt.

Hướng tiếp cận

Chúng ta sử dụng quy hoạch động (DP) với node ảo (virtual node) cho mỗi truy vấn.

Định nghĩa $dp[a][b]$ là số chuỗi hành trình và nhấn nút hợp lệ sử dụng các nút có số không vượt quá mức hiện tại, bắt đầu tại node $a$ và kết thúc tại node $b$.

• $a,b\in \{0,1,\dots ,N-1\}$: các phòng thực
• $a=N+j$: node ảo ${\alpha }_j$ — đại diện cho trạng thái "bắt đầu ở phòng $s_j$ nhấn nút $b_s^{(j)}$"
• $b=N+j$: node ảo ${\beta }_j$ — đại diện cho trạng thái "kết thúc ở phòng $t_j$ nhấn nút $b_t^{(j)}$"

Câu trả lời cho truy vấn $j$ là $dp[N+j][N+j]$ sau khi xử lý tất cả $K$ mức nút.

Thuật toán

Với mỗi mức nút $h$ (từ $0$ đến $K-1$, tương ứng nút $h+1$):

1. Sao chép $dp$ từ mức trước (chuỗi không dùng nút $h+1$ vẫn hợp lệ).

2. Với mỗi phòng "trung tâm" $c$ (nơi nhấn nút $h+1$):

   • Tính mảng $\text{left}[a]$: số chuỗi bắt đầu tại $a$ kết thúc ngay trước khi vào $c$:
     • $\text{left}[c]=1$ (chuỗi trái rỗng, Bessie bắt đầu ở $c$)
     • $\text{left}[N+j]+=1$ nếu $h=b_s^{(j)}-1$ và $c=s_j$ (node alpha kích hoạt)
     • $\text{left}[a]+={\sum }_{b^{\prime }:\text{adj}[b^{\prime }][c]}dp[a][b^{\prime }]$ (chuỗi DP đi vào $c$)
   • Tính mảng $\text{right}[b]$: số chuỗi bắt đầu ngay sau $c$ kết thúc tại $b$:
     • $\text{right}[c]=1$ (chuỗi phải rỗng, Bessie dừng ở $c$)
     • $\text{right}[N+j]+=1$ nếu $h=b_t^{(j)}-1$ và $c=t_j$ (node beta kích hoạt)
     • $\text{right}[b]+={\sum }_{a^{\prime }:\text{adj}[c][a^{\prime }]}dp[a^{\prime }][b]$ (chuỗi DP từ $c$)
   • Cộng vào DP mới: $d{p}^{\prime }[a][b]+=\text{left}[a]\times \text{right}[b]$

Độ phức tạp

• Số trạng thái DP: $O((N+Q{)}^2)$
• Với mỗi mức nút và mỗi phòng trung tâm: tính left và right mỗi cái mất $O(N·(N+Q))$, cộng vào DP mất $O((N+Q{)}^2)$
• Tổng: $O(N·(N+Q{)}^2·K)$

Với $N,K,Q\le 60$: $(N+Q{)}^2·K·N={120}^2·60·60\approx 5.2\times {10}^7$, hoàn toàn trong giới hạn thời gian.