fork download
copy 
  1. /*
  2.     Problem: Number of Valid Removal Orders for Compatible Adjacent Pairs
  3.     Company Tag: Rubrik OA
  4.  
  5.     Problem Statement:
  6.         We have 2 * N drives placed in a row.
  7.  
  8.         Some pairs of drives are compatible.
  9.         In one move, we can remove two adjacent drives only if that pair is compatible.
  10.  
  11.         After removing them, the remaining drives shift together.
  12.  
  13.         We need to remove all drives using exactly N moves.
  14.  
  15.         Two ways are different if at some move, the removed pair is different.
  16.  
  17.         Return the number of valid removal orders modulo 998244353.
  18.  
  19.     Constraints:
  20.         1 <= N <= 200
  21.         0 <= M <= N * (2N - 1)
  22.         1 <= A[i], B[i] <= 2 * N
  23.         All compatible pairs are distinct.
  24.  
  25.     Simple Brute Force:
  26.         Try every possible adjacent compatible pair at every step.
  27.  
  28.     Why Brute Force Fails:
  29.         The number of removal orders can grow very fast.
  30.         Since N can be 200, brute force is not possible.
  31.  
  32.     Better Idea:
  33.         Use interval DP.
  34.  
  35.         dp[l][r] = number of ways to completely remove drives from index l to r.
  36.  
  37.         For an interval [l, r], try pairing l with some position p.
  38.         If l and p are compatible:
  39.             - remove everything inside [l + 1, p - 1]
  40.             - then remove pair (l, p)
  41.             - remove everything on the right [p + 1, r]
  42.  
  43.         The inside operations and right-side operations can be interleaved,
  44.         so we also use combinations.
  45.  
  46.     Dry Run:
  47.         N = 2
  48.         Compatible pairs:
  49.             (1, 4)
  50.             (2, 3)
  51.  
  52.         Row:
  53.             1 2 3 4
  54.  
  55.         First remove (2, 3).
  56.         Then row becomes:
  57.             1 4
  58.  
  59.         Now remove (1, 4).
  60.  
  61.         Answer = 1
  62.  
  63.     Time Complexity:
  64.         O((2N)^3)
  65.  
  66.     Space Complexity:
  67.         O((2N)^2)
  68. */
  69.  
  70. #include <bits/stdc++.h>
  71. using namespace std;
  72.  
  73. const long long MOD = 998244353;
  74.  
  75. int main() {
  76.     int N, M;
  77.     cin >> N >> M;
  78.  
  79.     int total = 2 * N;
  80.  
  81.     // compatible[a][b] tells whether drives a and b can be removed together.
  82.     vector<vector<int>> compatible(total + 2, vector<int>(total + 2, 0));
  83.  
  84.     for (int i = 0; i < M; i++) {
  85.         int a, b;
  86.         cin >> a >> b;
  87.  
  88.         compatible[a][b] = 1;
  89.         compatible[b][a] = 1;
  90.     }
  91.  
  92.     /*
  93.         comb[n][r] stores nCr modulo MOD.
  94.  
  95.         We need this because operations from two independent parts
  96.         can be mixed in different orders.
  97.     */
  98.     vector<vector<long long>> comb(N + 2, vector<long long>(N + 2, 0));
  99.  
  100.     for (int i = 0; i <= N; i++) {
  101.         comb[i][0] = 1;
  102.         comb[i][i] = 1;
  103.  
  104.         for (int j = 1; j < i; j++) {
  105.             comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
  106.         }
  107.     }
  108.  
  109.     vector<vector<long long>> dp(total + 3, vector<long long>(total + 3, 0));
  110.  
  111.     // Only even length intervals can be fully removed.
  112.     for (int len = 2; len <= total; len += 2) {
  113.         for (int l = 1; l + len - 1 <= total; l++) {
  114.             int r = l + len - 1;
  115.  
  116.             // Try pairing the first drive of this interval with p.
  117.             for (int p = l + 1; p <= r; p += 2) {
  118.                 if (!compatible[l][p]) {
  119.                     continue;
  120.                 }
  121.  
  122.                 long long insideWays = 1;
  123.                 if (l + 1 <= p - 1) {
  124.                     insideWays = dp[l + 1][p - 1];
  125.                 }
  126.  
  127.                 long long rightWays = 1;
  128.                 if (p + 1 <= r) {
  129.                     rightWays = dp[p + 1][r];
  130.                 }
  131.  
  132.                 int insidePairs = (p - l - 1) / 2;
  133.                 int rightPairs = (r - p) / 2;
  134.  
  135.                 /*
  136.                     The inside part must finish before we can remove (l, p).
  137.                     So insidePairs operations plus removing (l, p) act like one group.
  138.  
  139.                     The right side operations can be mixed with this group.
  140.                 */
  141.                 int firstGroupOperations = insidePairs + 1;
  142.                 int totalOperations = insidePairs + rightPairs + 1;
  143.  
  144.                 long long orderWays = comb[totalOperations][firstGroupOperations];
  145.  
  146.                 long long ways = insideWays;
  147.                 ways = (ways * rightWays) % MOD;
  148.                 ways = (ways * orderWays) % MOD;
  149.  
  150.                 dp[l][r] = (dp[l][r] + ways) % MOD;
  151.             }
  152.         }
  153.     }
  154.  
  155.     cout << dp[1][total] << endl;
  156.  
  157.     return 0;
  158. }
Runtime error #stdin #stdout #stderr 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/iKhbEa
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!