Rohit and his brother

★★★★★

2.9

10 votes

Algorithms, Dynamic Programming, Introduction to Dynamic Programming 1

Details

Submissions

Discussion

Editorial

Problem

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$

Time Limit: 1

Memory Limit: 256

Source Limit:

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.