AtCoder DP Contest - Matching
Authors: Neo Wang, Sofia Yang, Kevin Sheng
Solution
If we define to be the number of matchings for females in the set to the first males, this problem boils down to the following:
(The :
stands for "such that".)
In English, this is equivalent to the following:
The number of matchings in a subset to include a certain female is equivalent to the sum of all the matchings without female where female is compatible with the -th male.
Our base case is the empty set, which has a value of (the empty set can be considered as a single matching involving zero pairs).
Implementation
Time Complexity:
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 + 7MAX_N = 21n = 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!