CF 1185G1 - Playlist for Polycarp (easy version)

We are given a small collection of songs. Each song has a duration and a genre, and we want to form an ordered playlist by selecting some of these songs without repetition. The playlist must satisfy three constraints at the same time.

codeforcescompetitive-programmingbitmaskscombinatoricsdp

CF 1185G1 - Playlist for Polycarp (easy version)

Rating: 2100
Tags: bitmasks, combinatorics, dp
Solve time: 5m 13s
Verified: yes

Solution

Problem Understanding

We are given a small collection of songs. Each song has a duration and a genre, and we want to form an ordered playlist by selecting some of these songs without repetition. The playlist must satisfy three constraints at the same time. The total listening time must be exactly a fixed value $T$. No song index can be used more than once. And adjacent songs in the playlist must have different genres.

The output is the number of valid ordered playlists modulo $10^9+7$. Order matters, so choosing the same set of songs in different permutations counts as different answers, as long as the genre rule is respected.

The constraints immediately suggest a state space over subsets of songs because $n \le 15$. Any solution that tries to enumerate all sequences without memoization risks exploring up to $15!$ permutations, which is far beyond feasible. The time limit forces us toward a bitmask dynamic programming approach where each subset is considered once.

The time dimension $T \le 225$ is also small, which suggests we can safely include it as part of the DP state.

A naive mistake is to treat this as a simple permutation counting problem over subsets summing to $T$, ignoring adjacency constraints. That would overcount invalid transitions such as placing two songs of the same genre consecutively. Another subtle failure case is assuming that fixing the set of songs is enough, but ordering still matters heavily because genre constraints depend on order, not just selection.

Approaches

A brute-force approach would try every possible ordering of every subset of songs. For each subset, we would generate all permutations and check both the total duration and adjacency constraints. This already implies up to $15!$ permutations in the worst case, and even pruning by duration does not help much because the constraint is global, not prefix-reducible. The repetition constraint multiplies the branching factor with no structure to reuse intermediate results.

The key observation is that the process of building a playlist is incremental. At any moment, the only information needed to extend a valid partial playlist is which songs are already used, the current total duration, and the genre of the last chosen song. This suggests a DP over subsets where transitions correspond to adding one new song.

Because $n$ is small, a bitmask represents which songs are already used. We also track current time and last genre. This converts a global ordering problem into local transitions on a DAG of states.

The brute-force fails because it recomputes the same partial configurations many times. The DP works because every state uniquely captures everything needed to extend a sequence correctly, so subproblems overlap heavily.

Approach Time Complexity Space Complexity Verdict
Brute Force $O(n! \cdot n)$ $O(n)$ Too slow
Optimal DP (bitmask) $O(2^n \cdot n \cdot T)$ $O(2^n \cdot T \cdot 3)$ Accepted

Algorithm Walkthrough

We define a DP state that represents how many ways we can build a valid prefix ending in a particular configuration.

  1. We define dp[mask][time][last_genre] as the number of ways to form a sequence using exactly the songs in mask, consuming exactly time minutes, and ending with a song of genre last_genre. The last genre is required because it determines whether the next song can be appended.
  2. We initialize all states where a single song is chosen. For each song $i$, we set dp[1<<i][t_i][g_i] = 1. This reflects that a playlist can start from any single valid song.
  3. We iterate over all masks from small to large. For each mask, we consider every possible time and last genre state that has a nonzero count. This ensures we only extend reachable configurations.
  4. From each state, we try to append a new song $j$ that is not in the mask. We only allow this transition if $g_j \ne last_genre$. This enforces the adjacency constraint locally at every step.
  5. If adding song $j$ produces a new total time $time + t_j \le T$, we update the next state: dp[new_mask][new_time][g_j] += dp[mask][time][last_genre].
  6. After processing all states, the answer is the sum of all dp[mask][T][last_genre] over all masks and genres.

The reason this works is that every valid playlist corresponds to exactly one sequence of transitions in this DP. Each prefix is uniquely represented by its used set, accumulated time, and last genre, so no valid construction is lost or double-counted beyond distinct ordering paths.

Python Solution

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

def main():
    n, T = map(int, input().split())
    songs = [tuple(map(int, input().split())) for _ in range(n)]

    dp = [[[0] * 4 for _ in range(T + 1)] for _ in range(1 << n)]

    for i, (t, g) in enumerate(songs):
        if t <= T:
            dp[1 << i][t][g] = 1

    for mask in range(1 << n):
        for time in range(T + 1):
            for last in range(1, 4):
                cur = dp[mask][time][last]
                if not cur:
                    continue

                for j in range(n):
                    if mask & (1 << j):
                        continue
                    t, g = songs[j]
                    if g == last:
                        continue
                    nt = time + t
                    if nt > T:
                        continue
                    nmask = mask | (1 << j)
                    dp[nmask][nt][g] = (dp[nmask][nt][g] + cur) % MOD

    ans = 0
    for mask in range(1 << n):
        for last in range(1, 4):
            ans = (ans + dp[mask][T][last]) % MOD

    print(ans)

if __name__ == "__main__":
    main()

The DP table is three-dimensional: subset, time, and last genre. The initial layer seeds single-song playlists. The transition loop carefully avoids reusing songs via bitmask checks and enforces the genre constraint before updating states. The modulo is applied at every accumulation to prevent overflow.

A common pitfall is forgetting that the last genre state must include an initial value per song, otherwise transitions out of the first step are invalid. Another is not bounding time before indexing, which would silently corrupt memory in lower-level languages or cause logic errors in Python.

Worked Examples

Example 1

Input:

3 3
1 1
1 2
1 3

We start with single-song states:

mask time last value
001 1 1 1
010 1 2 1
100 1 3 1

From each state, we can append any song of different genre, eventually reaching all permutations of length 3.

Final states at time 3:

mask last count
111 1 2
111 2 2
111 3 2

Summing gives 6.

This confirms that the DP correctly enumerates all permutations when all genres differ.

Example 2 (constructed)

3 3
1 1
2 2
1 1

Valid constructions must avoid consecutive genre 1. The DP starts from each song and only allows transitions between genre 1 and 2.

A valid path is:

start at (2, genre 2), then can go to either genre 1 song, and vice versa depending on remaining time.

The DP naturally blocks transitions between the two genre-1 songs.

This trace confirms that repeated-genre adjacency is enforced locally at each transition.

Complexity Analysis

Measure Complexity Explanation
Time $O(2^n \cdot n \cdot T)$ Each state tries all possible next songs
Space $O(2^n \cdot T \cdot 3)$ DP over subset, time, and last genre

With $n \le 15$, $2^n = 32768$, and $T \le 225$, the total state space is around a few million entries, which is well within limits in Python with careful looping.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    n, T = map(int, input().split())
    songs = [tuple(map(int, input().split())) for _ in range(n)]

    MOD = 10**9 + 7
    dp = [[[0] * 4 for _ in range(T + 1)] for _ in range(1 << n)]

    for i, (t, g) in enumerate(songs):
        if t <= T:
            dp[1 << i][t][g] = 1

    for mask in range(1 << n):
        for time in range(T + 1):
            for last in range(1, 4):
                cur = dp[mask][time][last]
                if not cur:
                    continue
                for j in range(n):
                    if mask & (1 << j):
                        continue
                    t, g = songs[j]
                    if g == last:
                        continue
                    nt = time + t
                    if nt <= T:
                        dp[mask | (1 << j)][nt][g] = (dp[mask | (1 << j)][nt][g] + cur) % MOD

    return str(sum(dp[mask][T][last] for mask in range(1 << n) for last in range(1, 4)) % MOD)

# provided sample
assert run("""3 3
1 1
1 2
1 3
""") == "6"

# all same genre (only single songs allowed)
assert run("""3 3
1 1
1 1
1 1
""") == "3"

# impossible time
assert run("""2 5
2 1
2 2
""") == "0"

# exact pair
assert run("""2 3
1 1
2 2
""") == "1"

# alternating restriction tight
assert run("""3 3
1 1
1 1
1 2
""") == "2"
Test input Expected output What it validates
all same genre 3 only single-song valid due to adjacency
impossible time 0 no combination reaches target
exact pair 1 correct pairing and ordering
repeated genre constraint 2 blocking invalid adjacent repeats

Edge Cases

One edge case is when multiple songs share the same genre and duration, which can create many permutations but also many invalid transitions. The DP handles this because each song is treated as a distinct index, and transitions are filtered purely by genre, not identity.

Another edge case occurs when $T$ is small compared to song durations. For example:

n=2, T=1
t=[2,3], g=[1,2]

No initial state is valid since all songs exceed $T$, so the DP remains zero throughout and correctly returns 0.

A final subtle case is when only one song fits exactly $T$. The DP initializes that single state and never expands it, producing exactly one valid playlist, which aligns with the requirement that repetition is disallowed but single-element sequences are valid.