Solution Outline

Explanation

First, we binary search on the initial velocity.

Then, we use dynamic programming on bitmasks to check whether an initial velocity is valid. Let $\texttt{dp}[i][j]$ be the minimum possible time to reach visit every mice in subset $i$ with $j$ as the last visited mouse. If it is not possible to reach subset $i$ with $j$ as the last visited mice, let $\texttt{dp}[i][j] = \infty$.

When transitioning, iterate through every mouse not in the current subset and try adding it to the current subset.

Finally, an initial velocity is possible iff there is an index $i$ such that $\texttt{dp}[2^{n}-1][i] \neq\infty$.

Implementation

Time Complexity: $\mathcal{O}(\log(M)N^2\cdot2^N)$, where $M$ is the maximum possible velocity.

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 15;
const long double PRECISION = 1e-3, INF = 1e18;

long double dp[1 << MAX_N][MAX_N], p[MAX_N];  // p[i] = pow(speed_red, i)

struct Mouse {
	long double x, y, time;

Copy
import java.io.*;
import java.util.*;

public final class CatAndMice {
	private static final long PRECISION = (long)1e4;
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int miceNum = Integer.parseInt(read.readLine());
		int[][] mice = new int[miceNum][];
		for (int m = 0; m < miceNum; m++) {