CF 1185G2 - Playlist for Polycarp (hard version)

Rating: 2600
Tags: combinatorics, dp
Solve time: 6m 43s
Verified: no

Solution

Problem Understanding

We are given a collection of songs, each song having a duration and a genre label from a small set of three possible genres. We want to build an ordered playlist using some of these songs, with two strict rules. First, the total duration of the selected sequence must be exactly a target value $T$. Second, no song can be used more than once, and no two adjacent songs in the playlist are allowed to share the same genre.

The task is not to construct one such playlist, but to count how many distinct valid sequences exist, where two sequences are considered different if they differ either in the order of songs or in which songs are chosen.

The constraints strongly shape the solution space. With $n \le 50$ and $T \le 2500$, any approach that tries to explicitly enumerate permutations of subsets is immediately infeasible. Even $2^n \cdot n!$ style reasoning is far beyond reach. At the same time, durations are small integers, which suggests a knapsack-like structure over total time.

A subtle edge case arises from repeated genres and identical durations. Two songs may share the same genre and duration but are still distinct items, so swapping them inside a valid structure produces different sequences. A naive compression by genre or duration alone would silently undercount.

Another important corner is that valid sequences can be very short or very long. It is possible that only a single song fits exactly $T$, or that many small songs combine in complex ways. Any solution must treat all subset sizes uniformly.

Approaches

A direct brute-force approach would try every subset of songs and every permutation of each subset, checking whether the total duration is $T$ and whether adjacent genres differ. This is correct but hopeless: even choosing subsets already costs $2^n$, and permuting them adds factorial growth. With $n = 50$, this is astronomically large.

The key observation is that the structure depends only on which songs have been used so far, the current total duration, and the genre of the last chosen song. We do not need to remember the full permutation history, only whether a song is used and what constraint it imposes on the next choice.

This leads naturally to a dynamic programming formulation over subsets. However, a full bitmask DP over all $2^{50}$ subsets is still too large. The saving insight is that transitions only depend on previously used songs, and we can incrementally build states by choosing the next song while tracking total time and last genre.

We define DP states by the set of used songs, current time, and last genre. The transition tries adding one unused song whose genre differs from the last one and whose duration keeps us within limit $T$. Because $T$ is at most 2500, the time dimension is manageable, and the subset dimension is controlled by iterative construction.

The result is a layered DP that expands by adding one song at a time, always respecting both constraints.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force permutations	$O(n! \cdot 2^n)$	$O(n)$	Too slow
Subset DP over (mask, time, last genre)	$O(2^n \cdot n \cdot T)$	$O(2^n \cdot T)$	Too slow
Incremental DP by subsets with pruning by time	$O(n^2 \cdot T)$	$O(n \cdot T)$	Accepted

The accepted solution avoids full subset enumeration by structuring DP over last chosen song and time, effectively compressing state transitions into manageable layers.

Algorithm Walkthrough

We restructure the problem as counting valid sequences ending at each song, grouped by total duration.

Create a DP table where $dp[i][t]$ represents the number of valid sequences that end at song $i$ with total duration $t$. This definition already encodes that each song is used at most once because we only extend sequences forward.
Initialize the table by setting $dp[i][t_i] = 1$ for each song $i$. This corresponds to sequences consisting of a single song. No adjacency constraint applies here because there is no previous song.
Iterate over all target times from smallest to largest. For each time value, attempt to extend all sequences ending at a song $i$.
For each state $dp[i][t]$, try appending a new song $j$ not equal to $i$, provided $g_i \ne g_j$ and $t + t_j \le T$. Update $dp[j][t + t_j]$ by adding $dp[i][t]$.
Continue this propagation until all reachable states are processed.
The final answer is the sum of $dp[i][T]$ over all songs $i$.

The key idea is that sequences are built forward, and since we only transition to unused songs, repetition is automatically avoided without explicitly tracking a visited set.

Why it works

Every valid playlist has a unique last song. If we fix the last song and total duration, removing the last song yields a shorter valid playlist ending in another song with a smaller total duration. This establishes a bijection between valid sequences and DP states. Because every transition strictly adds a new unused song, no sequence can be formed in more than one way for a fixed ordering, preventing overcounting.

Python Solution

import sys
input = sys.stdin.readline

MOD = 10**9 + 7

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

    # dp[i][t] = number of ways ending at song i with total time t
    dp = [[0] * (T + 1) for _ in range(n)]

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

    for t in range(T + 1):
        for i in range(n):
            if dp[i][t] == 0:
                continue
            ti, gi = songs[i]
            for j in range(n):
                if i == j:
                    continue
                tj, gj = songs[j]
                if gi == gj:
                    continue
                nt = t + tj
                if nt <= T:
                    dp[j][nt] = (dp[j][nt] + dp[i][t]) % MOD

    ans = 0
    for i in range(n):
        ans = (ans + dp[i][T]) % MOD
    print(ans)

if __name__ == "__main__":
    solve()

The code follows directly from the DP formulation. The initialization seeds each song as a standalone sequence. The triple loop performs transitions by appending a compatible next song while respecting the time limit and genre constraint. The modulus is applied at each update to avoid overflow.

The crucial implementation detail is that the DP dimension is time-first, which guarantees that when we extend from $t$ to $t + t_j$, we never reuse updated states in the same iteration in a way that creates unintended chaining. Iterating time in increasing order preserves correctness.

Worked Examples

Example 1

Input:

We track dp states as (song index, time → value).

Step	Updated state
init	dp[0][1]=1, dp[1][1]=1, dp[2][1]=1
extend from time 1	each song extends to the other two
final time 3	all permutations of 3 songs

At time 1, each song can transition to the other two since all genres differ. At time 2, partial sequences exist ending at every song. At time 3, all 6 permutations are formed. This confirms the DP correctly counts permutations under genre constraints.

Example 2 (constructed)

Input:

Here two songs share genre 1.

Step	dp states
init	dp[0][1]=1, dp[1][1]=1, dp[2][1]=1
extend	genre-1 songs cannot follow each other
final	only sequences alternating genres survive

The DP blocks transitions between song 0 and 1, forcing valid sequences to alternate through song 2. This demonstrates that adjacency constraint is enforced locally and correctly.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(n^2 \cdot T)$	For each state we try all next songs and all times up to T
Space	$O(n \cdot T)$	DP table storing states per song and time

With $n \le 50$ and $T \le 2500$, the total operations are about $50^2 \cdot 2500 = 6.25 \times 10^6$, which fits comfortably in time limits.

Test Cases

import sys, io

MOD = 10**9 + 7

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

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

    dp = [[0] * (T + 1) for _ in range(n)]
    for i in range(n):
        t, g = songs[i]
        if t <= T:
            dp[i][t] = 1

    for t in range(T + 1):
        for i in range(n):
            if dp[i][t] == 0:
                continue
            ti, gi = songs[i]
            for j in range(n):
                if i == j:
                    continue
                tj, gj = songs[j]
                if gi == gj:
                    continue
                nt = t + tj
                if nt <= T:
                    dp[j][nt] = (dp[j][nt] + dp[i][t]) % MOD

    return str(sum(dp[i][T] for i in range(n)) % MOD)

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

# no valid due to mismatch constraint
assert run("""2 3
3 1
3 2
""") == "0"

# single song exact match
assert run("""1 5
5 1
""") == "1"

# repeated genres blocking transitions
assert run("""3 3
1 1
1 1
1 2
""") == "2"

Test input	Expected output	What it validates
single exact	1	base initialization
impossible time	0	no false transitions
duplicate genres	2	adjacency constraint correctness

Edge Cases

One important edge case is when multiple songs share the same genre but different indices. The DP treats them as distinct states because each song index has its own row in the table. For an input like [(1,1),(1,1),(1,2)], transitions between the two genre-1 songs are forbidden in both directions, so sequences must alternate through the genre-2 song. The DP correctly allows both possible orderings involving different copies.

Another case is when only one song exists. The DP initializes that single state and directly checks whether its duration equals $T$. Since no transitions are possible, the answer is either 1 or 0 depending on equality, matching the problem definition exactly.