(Analysis by Steven Hao)

Because the bounds on $N$ are small, a solution with exponential runtime will be fast enough. Following this train of thought, we naturally come upon a dynamic programming solution with $2^N$ states: the subsets of $\{0,1,2,...,N-1\}$.

For every set of movies $M$, we compute the maximum amount of time Bessie can stay safe watching movies only from $M$. Then, the final answer is the minimum size of any set which keeps Bessie safe for at least $L$ minutes.

The transiition between states is fairly simple. If Bessie has already watched movies from set $M$, and wishes to watch another movie $i$, then the new state will be $M \cup \{i\}$. To maximize the amount of time she stays safe, Bessie should catch the latest showing of $i$ possible.

This yields a recurrence: where

- $\textit{DP}_M$ is the maximum amount of time spent watching movies from $M$
- $D_i$ is the length of movie $i$
- $S_i$ is the set of showtimes of movie $i$

the amount of time Bessie is safe watching $S$ then $i$ is given by

$$t = max(s \in S_i \mid s \le \textit{DP}_M) + D_i$$

Where $M' = M \cup i$, we may then update $DP_{M'}$ as:

$$DP_{M'} = max(DP_{M'}, t)$$

The slowest step is in computing t; we binary search for the insertion point of $DP_{M}$ in $S_i$. Where $C$ is the number of showtimes per movie, this transition can be computed in $O(\log C)$ time.

As there are $2^N$ states and $O(N)$ transitions from each state, this yields an overall runtime of $O(2^N N \log C)$, which is barely fast enough.

If it is not fast enough, the searching step can be removed and replaced with a bit of precomputation: For all $c$, $i$, $j$: compute the latest showing of j you can watch after watching the $c$-th showing of movie. This takes $O(C N^2)$ precomputation, and yields a runtime of $O((2^N + CN) N)$. However, implementing this one requires storing not just the maximum safe time but the movie and showtime that yields it.

Below is my implementation of the $O(2^N N \log C)$ solution.

#include <cstdio> const int MAXN = 22; const int MAXC = 1010; int N, L; int D[MAXN]; // D[i]: length of movie i int S[MAXN][MAXC]; // S[i]: showtimes of movie i int C[MAXN]; // C[i]: length of list ar[i] int dp[1 << MAXN]; // dp[ {x} ]: max safe time watching movies from {x} // where {x} is a subset of [0,N), and is represented by a bitmask int find(int val, int *ar, int len) { // bin search for greatest x s.t. ar[x] <= val int lo = -1, hi = len - 1; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (ar[mid] <= val) { lo = mid; } else { hi = mid - 1; } } return lo; } int popcount(int x) { // returns number of bits of x set to 1 if (x) return 1 + popcount(x & (x - 1)); else return 0; } int main() { if (fopen("movie.in", "r")) { freopen("movie.in", "r", stdin); freopen("movie.out", "w", stdout); } scanf("%d %d", &N, &L); for(int i = 0; i < N; ++i) { scanf("%d %d", D + i, C + i); for(int j = 0; j < C[i]; ++j) { scanf("%d", S[i] + j); } } for(int msk = 1; msk < (1 << N); ++msk) { dp[msk] = -1; } // dp[0] = 0 int ans = -1; for(int msk = 0; msk < (1 << N); ++msk) { int cur = dp[msk]; if (cur == -1) continue; if (cur >= L) { int cnt = popcount(msk); if (ans == -1 || cnt < ans) ans = cnt; } for(int i = 0; i < N; ++i) { if (msk & (1 << i)) continue; // try watching movie i after watching {msk} int nmsk = msk | (1 << i); int idx = find(cur, S[i], C[i]); if (idx == -1) continue; // want to watch idx-th showing of movie i (latest showing) int t = S[i][idx] + D[i]; if (t > dp[nmsk]) dp[nmsk] = t; } } printf("%d\n", ans); return 0; }