## Intuition The problem is about determining the connectivity between rooms in a directed graph where each room is connected to every other room by a single directed edge. We need to deduce the reachability between all pairs of rooms using a limited number of queries. This is a classic problem of determining the transitive closure of a directed graph. ## Approach 1. **Understanding the Graph Structure**: - Each room is connected to every other room by a single directed edge. This forms a directed graph where each node has exactly one outgoing edge to each other node. - The task is to determine if there exists a path from room `i` to room `j` for all pairs `(i, j)`. 2. **Queries**: - We have two types of queries: - Type 1: Ask if there's a passage from room `a` to room `b`. - Type 2: Ask about the direction of the passage between rooms `a` and `b`. - The constraints allow us to make at most `9n` queries of the first type and `2n` queries of the second type. 3. **Strategy**: - Use the queries to determine the direction of edges between rooms. - Once the directions are known, compute the transitive closure using the Floyd-Warshall algorithm or a similar method to determine reachability between all pairs of rooms. 4. **Implementation**: - For each test case, initialize a reachability matrix `reachable` of size `n x n` with all zeros. - Use queries to fill in the direct connections. - Use a graph traversal method to fill in the transitive closure of the graph. - Output the reachability matrix for each test case. ## Complexity - **Time Complexity**: O(n^3) per test case due to the transitive closure computation. - **Space Complexity**: O(n^2) for storing the reachability matrix. ## Solution (C++) ```cpp #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; vector> reachable(n, vector(n, 0)); // Initialize reachability matrix with self-loops for (int i = 0; i < n; ++i) { reachable[i][i] = 1; } // Use queries to determine direct connections for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (i != j) { cout << "1 " << i << " " << j << endl; int response; cin >> response; if (response == 1) { reachable[i][j] = 1; } } } } // Compute transitive closure using Floyd-Warshall for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (reachable[i][k] && reachable[k][j]) { reachable[i][j] = 1; } } } } // Output the reachability matrix cout << "3" << endl; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cout << reachable[i][j]; } cout << endl; } int verdict; cin >> verdict; if (verdict == -1) { return 0; // Terminate if the answer is incorrect } } return 0; } ``` This solution utilizes the Floyd-Warshall algorithm to compute the transitive closure of the graph, ensuring that we determine the reachability between all pairs of rooms efficiently. The interactive nature of the problem is handled by querying the interactor and adjusting the reachability matrix based on the responses.

Baby Ehab's Hyper Apartment

Problem Details