Home » 国际竞赛 » Details

USACO 2015 January Contest, Gold Problem 2. Moovie Mooving

Category: 国际竞赛, 计算机国际竞赛 Date: 2017年12月8日下午3:27

原题下载

USACO2015JAN-G2

答案

(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

${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 = m a x (s \in S i ∣ s \leq DP M) + D i

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

D P M' = m a x (D P M', t)

The slowest step is in computing t; we binary search for the insertion point of $D P_{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} + C N) 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;
}