Rohit and his brother

Practice

2.9 (10 votes)

Algorithms

Dynamic programming

Introduction to dynamic programming 1

Problem

42% Success 1300 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Rohit and his brother Rohan have two old wooden chests, \(A\) and \(B\), consisting of \(N\) integers. They also got an old rusted trunk with lots of diamonds inside it. However, the rusted trunk has a lock that can only be opened if they know the number of combinations possible such that the following conditions are satisfied. Assume they choose a set of numbers {\({S_1,S_2,S_3...S_K}\)} consisting of integers from \(1\) to \(N\). Let \(A_{max}\) denote the maximum element of the numbers, {\( A[S_1], A[S_2]...A[S_K]\)} and \(B_{sum}\) denote the sum of the elements {\(B[S_1], B[S_2]...B[S_K]\)}. Then, \(A_{max}\) must be greater than or equal to \(B_{sum}\). Since the answer could be large, compute it modulo \(10^9+7\). Input Format : The first line contains a single integer \(T\) representing the number of test cases. Then each test case follows. The first line of each test case contains an integer \(N\) denoting the number of integers in the wooden trunks \(A\) and \(B\). The second line of every test case contains \(N\) integers denoting the integers contained in the wooden chest \(A\). The third line of every test case contains \(N\) integers denoting the integers contained in the wooden chest \(B\). Output Format : For each test case, print an integer denoting the number of subsets or combinations satisfying the conditions given in the statement modulo \(10^9+7\). Constraints : \(1 \leq T \leq 5\) \(1 \leq N \leq 1000\) \(1 \leq A_i \leq 1000\) \(1 \leq B_i \leq 1000\)

Sample Input

Sample Output

3
0

Explanation

In the first test case, the answer should be 3 because subsets {1}, {2} and {3} satisfy the above conditions. For the subset {1}, Assume 1-based indexing, \(A_{max}\) = max(A[1]) = 1 and \(B_{sum}\) = {A[1]} = 1, and hence, \(A_{max}\) >= \(B_{sum}\). For the subset {2}, Assume 1-based indexing, \(A_{max}\) = max(A[2]) = 1 and \(B_{sum}\) = {A[2]} = 1, and hence, \(A_{max}\)>= \(B_{sum}\). For the subset {3}, Assume 1-based indexing, \(A_{max}\) = max(A[3]) = 1 and \(B_{sum}\) = {A[3]} = 1, and hence, \(A_{max}\) >= \(B_{sum}\). In the second test case, the answer should be 0 because no subset or combination satisfies the conditions described in the problem statement.

Code Editor

You need to be logged in to access the code editor

Please wait while we load the editor

Submissions

Please login to view your submissions

You need to be logged in to access the code editor

Please wait while we load the editor