Home » 国际竞赛 » Details

USACO 2020 December Contest, Platinum Problem 2. Spaceship

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午3:13

USACO 2020 December Contest, Platinum Problem 2. Spaceship

Bessie the cow has been abducted by aliens and is now trapped inside an alien spaceship! The spaceship has $N$ $(1 \leq N \leq 60)$ rooms labeled $1 \dots N$ , with one-way doors connecting between some pairs of rooms (due to the strange alien technology at play, it is even possible for a door to lead from a room back to itself!). However, no two doors share the same starting and end room. Additionally, Bessie has a remote with buttons numbered $1 \dots K$ $(1 \leq K \leq 60)$ .

The aliens will release Bessie if she can complete a strange task. First, they will choose two rooms, $s$ and $t$ $(1 \leq s, t \leq N)$ , and two numbers, $b_{s}$ and $b_{t}$ $(1 \leq b_{s}, b_{t} \leq K)$ . They will start Bessie in room $s$ and immediately have her press button $b_{s}$ . Bessie will then proceed to navigate the ship while pressing buttons. There are a few rules for what Bessie can do:

In each room, after pressing exactly one button, she must choose to either exit through a door to another (possibly the same) room or stop.
Once Bessie presses a button, it is invalid for her to press the same button again unless, in the time between uses, she has pressed a button with a higher number. In other words, pressing button number $x$ will make it unavailable for use, while all buttons with numbers $< x$ will be reset and again available for use.
If Bessie presses an invalid button, she automatically fails and the aliens will keep her.

Bessie is released only if she stops in room $t$ , the last button she pressed was $b_{t}$ , and no invalid buttons were ever pressed.

Bessie is worried that she may not be able to complete the task. For $Q$ $(1 \leq Q \leq 60)$ queries, each consisting of what Bessie considers a likely choice of $s, t, b_{s}$ , and $b_{t}$ , Bessie wants to know the number of sequences of rooms and button presses that would lead to her release. Report your answers modulo $10^{9} + 7$ as they may be very large.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N, K, Q$ .The next $N$ lines each contain $N$ bits (each 0 or 1). The $j$ -th entry of the $i$ -th line is 1 if there exists a door from room $i$ to room $j$ , and 0 if no such door exists.

This is followed by $Q$ lines, each containing four integers $b_{s}$ , $s$ , $b_{t}$ , $t$ , denoting the starting button, starting room, final button, and final room respectively.

OUTPUT FORMAT (print output to the terminal / stdout):

The number of sequences for each of the $Q$ queries modulo $10^{9} + 7$ on separate lines.

SAMPLE INPUT:

SAMPLE OUTPUT:

The doors connect rooms $1 \to 2$ , $2 \to 3$ , $3 \to 4$ , $4 \to 5$ , and $6 \to 6$ .

For the first query, Bessie must stop immediately after pressing the first button.

For the second query, the answer is clearly zero because there is no way to get to room 1 from room 3.

For the third query, Bessie's only option is to move from room 1 to room 2 to room 3 while pressing buttons 1, 2, and 3.

For the fourth query, Bessie's pattern of movement is fixed, and she has three possible sequences of button presses:

$(1, 2, 3, 2, 1)$
$(1, 2, 1, 3, 1)$
$(1, 3, 1, 2, 1)$

For the last query, Bessie has five possible sequences of button presses:

$(2)$
$(2, 3, 2)$
$(2, 3, 1, 2)$
$(2, 1, 3, 2)$
$(2, 1, 3, 1, 2)$

SAMPLE INPUT:

SAMPLE OUTPUT:

This test case satisfies the constraints for all subtasks aside from the first.

SAMPLE INPUT:

SAMPLE OUTPUT:

Make sure to output the answers modulo $10^{9} + 7$ .

SCORING:

In test cases 4-7, $K \leq 5$ and $(b_{s}, s)$ is the same for all queries.
In test cases 8-11, $b_{s} = K - 1$ and $b_{t} = K$ for each query.
In test cases 12-15, $N, K, Q \leq 20$ .
In test cases 16-23, there are no additional constraints.

Problem credits: Benjamin Qi

USACO 2020 December Contest, Platinum Problem 2. Spaceship 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Danny Mittal)

Subtask 1 ( $K \leq 5$ )

We can do this via bitmask DP. Our states will be pairs $(μ, r)$ where $μ$ is a bitmask of length $K$ and $r$ is a room. The bitmask $μ$ represents all sequences of button presses such that iff the $j$ th bit in $μ$ is on, Bessie has pressed button $j$ at least once and has not pressed any button with a higher number than $j$ since the last time she pressed button $j$ . The state $(μ, r)$ then represents all sequences of button presses and rooms beginning in room $s$ by pressing button $b_{s}$ , ending in room $r$ , and satisfying the conditions to correspond to mask $μ$ .

A transition in our DP is then moving to another (possibly the same) room as well as pressing another button. Bessie can move to room $r^{'}$ iff there is an edge from $r$ to $r^{'}$ . Additionally, Bessie can press button $j$ iff the $j$ th bit in the current mask $μ$ is off — otherwise, she would press button $j$ twice without pressing a button with a higher number in between.

We then must also consider how pressing a button changes $μ$ . It clearly sets the $j$ th bit to be on. Additionally, all lower bits are set off now that a higher button has been pressed. All higher bits are unaffected. It is important to note that the way this modification works implies that we always increase the numerical value of our bitmask when transitioning, meaning that there are no circular relations in our DP and that we should consider bitmasks in order of increasing numerical value.

Our DP then has $O (2^{K} N)$ states, from each of which we perform $O (K N)$ transitions, meaning that our DP runs in $O (K 2^{K} N^{2})$ .

To compute the answer for each query, we simply take the sum of the DP values of $(t, μ)$ over all bitmasks $μ$ such that the $b_{t}$ th bit is on and all lower bits are off, as these correspond precisely to the sequences where we end by pressing button $b_{t}$ . This takes $O (2^{K})$ time, so that our final computations take $O (2^{K} Q)$ time overall and thus our overall solution takes $O (2^{K} (K N^{2} + Q))$ .

Subtask 2 ( $b_{s} = K - 1$ and $b_{t} = K$ for each query)

First note that as Bessie always presses button $K$ at the end, she cannot press button $K$ before then, as there would be no higher button that she could press in between (as button $K$ is the highest button). This also means that she cannot press button $K - 1$ after the beginning as she could never press button $K$ , the only higher button. Thus, any sequence of button presses that Bessie takes, excluding the first and last button, uses buttons with numbers at most $K - 2$ .

We can then solve this using DP. $d p_{a, b, x}$ will be the number of sequences of rooms and button presses which start at room $a$ , end at room $b$ , and only involve pressing buttons with numbers at most $x$ . We can compute transitions as follows. First, we add all of $d p_{a, b, x - 1}$ to $d p_{a, b, x}$ , as a sequence only using buttons with numbers at most $x - 1$ will clearly also only use buttons with numbers at most $x$ .

We then consider the case where we do press button $x$ . Note that as we never press any higher buttons, we must only press button $x$ once. Let’s then fix the room $r$ that Bessie is in when she presses button $x$ , and consider in isolation the part of the sequence before pressing button $x$ (the left side) and after pressing button $x$ (the right side). The left side, if it is not empty, starts at some room $a$ , ends at some room $b$ such that there is an edge from $b$ to $r$ , and only presses buttons with number at most $x - 1$ . Similarly, the right side, if it is not empty, starts at some room $c$ such that there is an edge from $r$ to $c$ , ends at some room $d$ , and only presses buttons with number at most $x - 1$ .

The number of left sides is then $d p_{a, b, x - 1}$ for each $a, b$ and the number of right sides is $d p_{c, d, x - 1}$ for each $c, d$ . We only care about the endpoints $a$ and $d$ , so for each $a$ , we compute the sum over all $d p_{a, b, x - 1}$ such that there is an edge from $b$ to $r$ , and similarly for each $d$ . Note that we should account for the left side possibly being empty by adding $1$ to our calculation for $a = r$ , as in that case our overall left endpoint will just be $r$ (and similarly for the right side). Finally, for each $a, d$ , we can simply multiply these quantities together and add the result to $d p_{a, d, x}$ .

Each of these three computations is $O (N^{2})$ , so as we do them for each maximum number $x$ and “middle” room $r$ , our DP computation is $O (N^{3} K)$ overall.

Given this DP, for each query to compute the answer, given that we want to start at room $s$ and end at room $t$ , we loop through all second rooms $a$ (such that there is an edge from $s$ to $a$ ) and second-to-last rooms $b$ (such that there is an edge from $b$ to $t$ ) and add $d p_{a, b, K - 2}$ to our answer. This is $O (N^{2})$ for each query, making our overall algorithm $O (N^{3} K + Q N^{2})$ .

Subtask 3 ( $N, K, Q \leq 20$ )

We can solve this subtask by modifying our solution for the previous subtask. First note that our constraints are now low enough to allow computing our $O (N^{3} K)$ DP for each query. Given this, we can simply modify our DP as follows. $d p_{a, b, k}$ will be defined as usual, except that $a$ can also take a special value $α$ which will indicate that we are counting sequences which start at room $s$ but must also start by pressing button $b_{s}$ . Similarly, $b$ can take a special value $β$ which will indicate that we are counting sequences which end at room $t$ but must also end by pressing button $b_{t}$ .

These special values $α$ and $β$ then essentially function as normal rooms during our DP. There are only two differences: ones is that in our above loops through all $a, b$ and $c, d$ , the rooms $b$ and $c$ are not allowed to be $α$ or $β$ as that would lead to overcounting; the other is that we must properly account for the left side being empty by also adding $1$ to our calculation for $a = α$ if we are currently at $r = s$ and $x = b_{s}$ , and similarly for the right side.

Our answer is then simply $d p_{α, β, K}$ . These modifications do not affect the asymptotic runtime of our DP, but we do now do it for each query, giving the overall algorithm a runtime of $O (Q N^{3} K)$ .

Subtask 4 (original constraints)

Our solution for this is essentially the same as for the previous subtask, noting that we don’t actually really need to compute this DP for each query. We can compute this DP just once by, instead of having the two special values $α$ and $β$ , having values $α_{j}$ and $β_{j}$ for each $1 \leq j \leq Q$ such that $α_{j}$ corresponds to $(s, b_{s})$ for the $j$ th query and $β_{j}$ corresponds to $(t, b_{t})$ for the $j$ th query. The answer to the $j$ th query is then $d p_{α_{j}, β_{j}, K}$ .

Considering the additional states, the runtime of our algorithm is now $O (N (N + Q)^{2} K)$ , which is still fast enough.

Danny's code:

import java.util.Scanner;
 
public class LevelGraph {
    public static final long MOD = 1000000007;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int q = in.nextInt();
        boolean[][] adj = new boolean[n][n];
        for (int a = 0; a < n; a++) {
            String line = in.next();
            for (int b = 0; b < n; b++) {
                adj[a][b] = line.charAt(b) == '1';
            }
        }
        int[] xs = new int[q];
        int[] froms = new int[q];
        int[] ys = new int[q];
        int[] tos = new int[q];
        for (int j = 0; j < q; j++) {
            xs[j] = in.nextInt() - 1;
            froms[j] = in.nextInt() - 1;
            ys[j] = in.nextInt() - 1;
            tos[j] = in.nextInt() - 1;
        }
        long[][][] dp = new long[k][n + q][n + q];
        for (int h = 0; h < k; h++) {
            if (h > 0) {
                for (int a = 0; a < n + q; a++) {
                    for (int b = 0; b < n + q; b++) {
                        dp[h][a][b] = dp[h - 1][a][b];
                    }
                }
            }
            for (int c = 0; c < n; c++) {
                long[] left = new long[n + q];
                left[c] = 1;
                for (int j = 0; j < q; j++) {
                    if (h == xs[j] && froms[j] == c) {
                        left[n + j] = 1;
                    }
                }
                if (h > 0) {
                    for (int a = 0; a < n + q; a++) {
                        for (int b = 0; b < n; b++) {
                            if (adj[b][c]) {
                                left[a] += dp[h - 1][a][b];
                                left[a] %= MOD;
                            }
                        }
                    }
                }
                long[] right = new long[n + q];
                right[c] = 1;
                for (int j = 0; j < q; j++) {
                    if (h == ys[j] & tos[j] == c) {
                        right[n + j] = 1;
                    }
                }
                if (h > 0) {
                    for (int a = 0; a < n; a++) {
                        for (int b = 0; b < n + q; b++) {
                            if (adj[c][a]) {
                                right[b] += dp[h - 1][a][b];
                                right[b] %= MOD;
                            }
                        }
                    }
                }
                for (int a = 0; a < n + q; a++) {
                    for (int b = 0; b < n + q; b++) {
                        dp[h][a][b] += left[a] * right[b];
                        dp[h][a][b] %= MOD;
                    }
                }
            }
        }
        for (int j = 0; j < q; j++) {
            System.out.println(dp[k - 1][n + j][n + j]);
        }
    }
}

[/hide]