algorithms

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

problem.txt (1531B)


      1 C. Non-Descending Arrays
      2 time limit per test2 seconds
      3 memory limit per test256 megabytes
      4 You are given two integer arrays a
      5  and b
      6  both of length n
      7 .
      8 
      9 You can choose any subset of indices and swap the elements at those positions (i. e. make a swap(ai
     10 , bi
     11 ) for each i
     12  in the subset). A subset of indices is considered good if, after the swapping, both arrays are sorted in non-descending order.
     13 
     14 Your task is to calculate the number of good subsets. Since the answer can be large, print it modulo 998244353
     15 .
     16 
     17 Input
     18 The first line contains a single integer t
     19  (1≤t≤500
     20 ) — the number of test cases.
     21 
     22 The first line of each test case contains a single integer n
     23  (1≤n≤100
     24 ).
     25 
     26 The second line contains n
     27  integers a1,a2,…,an
     28  (1≤ai≤1000
     29 ).
     30 
     31 The third line contains n
     32  integers b1,b2,…,bn
     33  (1≤bi≤1000
     34 ).
     35 
     36 Additional constraint on the input: there is at least one good subset.
     37 
     38 ---
     39 
     40 - thoughts
     41     - a, b both length n
     42     - select any subset of indices and swap a_b and b_i
     43     - a subset is good if a and b are sorted non-descendingly
     44     - return number of good subsets mod 998244353
     45         - big nums
     46 
     47 --- 
     48 
     49 since big nums, use long, and we know the algo is efficient
     50 
     51 ex1:
     52 
     53 3
     54 2 1 4
     55 1 3 2
     56 
     57 option1:
     58 
     59 2 3 4
     60 
     61 1 1 2
     62 
     63 option2:
     64 
     65 1 1 2
     66 2 3 4
     67 
     68 ---
     69 
     70 1
     71 4
     72 4
     73 
     74 we can keep same or swap so 2
     75 
     76 ---
     77 
     78 5
     79 2 3 3 4 4
     80 1 1 3 5 6
     81 
     82 
     83 
     84 // idea:
     85     // try flipping an element
     86     // try not flipping an element
     87         // if current is not non-decreasing and flip is also, return 0
     88         // propogate this up
     89     // return sum