algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (2111B)


      1 #include <vector>
      2 #include <iostream>
      3 #include <unordered_map>
      4 
      5 // idea:
      6     // try flipping an element
      7     // try not flipping an element
      8         // if current is not non-decreasing and flip is also, return 0
      9         // propogate this up
     10     // return sum
     11 
     12 long long subsets(std::vector<int>& a, std::vector<int>& b, int idx, std::unordered_map<int,long long>& memo) {
     13     
     14     if(memo.contains(idx)) {
     15         return memo[idx];
     16     }
     17 
     18     if(idx >= b.size()) {
     19 //        for(int i = 0; i < a.size(); ++i) {
     20 //            std::cout << a[i] << " ";
     21 //        }
     22 //        std::cout << std::endl;
     23 //        for(int i = 0; i < a.size(); ++i) {
     24 //            std::cout << b[i] << " ";
     25 //        }
     26 //        std::cout << std::endl;
     27 
     28 
     29         memo[idx] = 1;
     30         return 1; // this means we safely went to the end and know of an ordering
     31     }
     32     
     33     bool isFineNoSwap = true;
     34     if(idx != 0) {
     35         isFineNoSwap = a[idx] >= a[idx-1] && b[idx] >= b[idx-1];
     36     } 
     37 
     38     bool isFineSwap = true;
     39     if(idx != 0) {
     40         isFineSwap = a[idx] >= b[idx-1] && b[idx] >= a[idx-1];
     41     } 
     42     
     43     if(!isFineNoSwap && !isFineSwap) {
     44         memo[idx] = 0;
     45         return 0;
     46     }
     47 
     48     long long sm = 0;
     49 
     50     // since this is symmetric, we notice there's either one correct option or both are correct, regardless of if we swapped at the prior step
     51 
     52     if(isFineNoSwap) {
     53         sm += subsets(a,b,idx+1, memo);
     54     }
     55     if(isFineSwap) {
     56         sm += subsets(a,b,idx+1, memo);
     57     }
     58 
     59 
     60     memo[idx] = sm % 998244353;
     61     return sm % 998244353;
     62 }
     63 
     64 int main() {
     65     int current, lsSize, testCaseCount;
     66     std::cin >> testCaseCount;
     67     for(int z = 0; z < testCaseCount; ++z) {
     68         std::cin >> lsSize;
     69         std::vector<int> a {};
     70         std::vector<int> b {};
     71         for(int x = 0; x < lsSize; ++x) {
     72             std::cin >> current;
     73             a.push_back(current);
     74         }
     75         for(int x = 0; x < lsSize; ++x) {
     76             std::cin >> current;
     77             b.push_back(current);
     78         }
     79         std::unordered_map<int, long long> mp {};
     80         std::cout << subsets(a,b,0,mp) << std::endl;
     81     }
     82 }