AtCoder DP Contest - Matching

Authors: Neo Wang, Sofia Yang, Kevin Sheng

Edit This Page

Table of Contents

SolutionImplementation

Solution

Time Complexity: O(N⋅2N)\mathcal{O}(N\cdot 2^N)

If we define dp[S]\texttt{dp}[S] to be the number of matchings for females in the set SS to the first ∣S∣|S| males, this problem boils down to the following:

dp[S]=∑dp[S\x]:compatible[∣S∣][x]\texttt{dp}[S] = \sum \texttt{dp}[S\backslash x]: \texttt{compatible}[|S|][x]

(The : stands for "such that".) In English, this is equivalent to the following:

The number of matchings in a subset SS to include a certain female xx is equivalent to the sum of all the matchings without female xx where female xx is compatible with the ∣S∣|S|-th male.

Our base case is the empty set, which has a value of 11 (the empty set can be considered as a single matching involving zero pairs).

Implementation

C++

#include <bits/stdc++.h>
using namespace std;


const int MOD = 1e9 + 7;
const int MAX_N = 21;


bool compat[MAX_N][MAX_N];
int dp[1 << MAX_N];


int main() {

Java

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


public class Main {
	public static final int MOD = (int)1e9 + 7;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		boolean[][] compat = new boolean[N][N];
		for (int m = 0; m < N; m++) {

Python

MOD = 10**9 + 7
MAX_N = 21


n = int(input())


compat = []
for _ in range(n):
	compat.append(list(map(int, input().split())))


dp = [0] * (1 << n)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum