2015 Jan Gold Problem 2 Moovie Mooving

Problem Statement

Farmer John's cows are having a movie night, and they are trying to decide which movies to watch. They have N movies (1 <= N <= 20) to choose from, each with a different duration in minutes. The cows want to watch as many movies as possible, and they have a total of L minutes (1 <= L <= 1000) to watch movies before they need to go to sleep.

Each movie has a "moo" factor, which is a positive integer representing the cows' enjoyment. The cows want to maximize the total "moo" factor of the movies they watch. However, they can only watch each movie once, and they cannot pause and continue movies later. If they start watching a movie, they have to finish it.

Help the cows decide which movies to watch to maximize their total "moo" factor without exceeding the available time.

Input

   Line 1: Two space-separated integers, N and L.
   Lines 2..N+1: Line i+1 contains two space-separated integers: the duration and the "moo" factor of movie i.

Output

   Line 1: A single integer representing the maximum total "moo" factor the cows can achieve.

Solution

We can solve this problem using dynamic programming. Let's create a table dp[i][j], where i represents the bitmask of watched movies and j represents the number of minutes remaining. The value at dp[i][j] is the maximum "moo" factor that can be achieved by watching the movies represented by bitmask i with j minutes remaining.

We start by initializing the table to all zeros. Then, for each movie, we iterate over all possible bitmasks and update the table accordingly:

for movie in range(N):
    duration, moo_factor = movie_info[movie]
    for bitmask in range(1 << N):
        if bitmask & (1 << movie) == 0: # If the movie is not watched yet
            for time_left in range(L + 1 - duration):
                new_bitmask = bitmask | (1 << movie)
                new_time_left = time_left + duration
                dp[new_bitmask][new_time_left] = max(dp[new_bitmask][new_time_left], dp[bitmask][time_left] + moo_factor)

Finally, we find the maximum "moo" factor achieved:

max_moo_factor = 0
for bitmask in range(1 << N):
    for time_left in range(L + 1):
        max_moo_factor = max(max_moo_factor, dp[bitmask][time_left])

The time complexity of this solution is O(N * L * 2^N). Since N is at most 20 and L is at most 1000, this solution is efficient enough to solve the problem within the given constraints.

Code

C++

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 22;
const int MAXC = 1010;

int N, L;
int D[MAXN];
std::vector<int> S[MAXN];
int C[MAXN];
int dp[1 << MAXN];

int popcount(int x) {
    return __builtin_popcount(x);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> L;
    for (int i = 0; i < N; ++i) {
        std::cin >> D[i] >> C[i];
        S[i].resize(C[i]);
        for (int j = 0; j < C[i]; ++j) {
            std::cin >> S[i][j];
        }
    }

    std::fill(dp + 1, dp + (1 << N), -1);

    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;

            int nmsk = msk | (1 << i);
            auto idx = std::upper_bound(S[i].begin(), S[i].end(), cur) - 1;
            if (idx == S[i].begin() - 1) continue;

            int t = *idx + D[i];
            if (t > dp[nmsk]) dp[nmsk] = t;
        }
    }

    std::cout << ans << '\n';
    return 0;
}

Java

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

public class Main {
    static final int MAXN = 22;
    static final int MAXC = 1010;

    static int N, L;
    static int[] D = new int[MAXN];
    static ArrayList<Integer>[] S = new ArrayList[MAXN];
    static int[] C = new int[MAXN];
    static int[] dp = new int[1 << MAXN];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        N = in.nextInt();
        L = in.nextInt();
        for (int i = 0; i < N; ++i) {
            D[i] = in.nextInt();
            C[i] = in.nextInt();
            S[i] = new ArrayList<>();
            for (int j = 0; j < C[i]; ++j) {
                S[i].add(in.nextInt());
            }
        }

        Arrays.fill(dp, 1, 1 << N, -1);

        int ans = -1;
        for (int msk = 0; msk < (1 << N); ++msk) {
            int cur = dp[msk];
            if (cur == -1) continue;

            if (cur >= L) {
                int cnt = Integer.bitCount(msk);
                if (ans == -1 || cnt < ans) ans = cnt;
            }

            for (int i = 0; i < N; ++i) {
                if ((msk & (1 << i)) != 0) continue;

                int nmsk = msk | (1 << i);
                int idx = Collections.binarySearch(S[i], cur);
                if (idx < 0) idx = -idx - 2;
                if (idx == -1) continue;

                int t = S[i].get(idx) + D[i];
                if (t > dp[nmsk]) dp[nmsk] = t;
            }
        }

        System.out.println(ans);
    }
}

Python

import sys
from bisect import bisect_right

MAXN = 22
MAXC = 1010

def popcount(x):
    return bin(x).count('1')

def main():
    N, L = map(int, input().split())
    D = [0] * MAXN
    S = [[] for _ in range(MAXN)]
    C = [0] * MAXN
    dp = [-1] * (1 << MAXN)

    for i in range(N):
        D[i], C[i], *showtimes = map(int, input().split())
        S[i] = showtimes

    dp[0] = 0

    ans = -1
    for msk in range(1 << N):
        cur = dp[msk]
        if cur == -1:
            continue

        if cur >= L:
            cnt = popcount(msk)
            if ans == -1 or cnt < ans:
                ans = cnt

        for i in range(N):
            if msk & (1 << i):
                continue

            nmsk = msk | (1 << i)
            idx = bisect_right(S[i], cur) - 1
            if idx == -1:
                continue

            t = S[i][idx] + D[i]
            if t > dp[nmsk]:
                dp[nmsk] = t

    print(ans)

if __name__ == "__main__":
    main()