This is the hard version of this problem. The only difference is that you need to also…
- User
This is the hard version of this problem. The only difference is that you need to also output the number of optimal sequences in this version. You must solve both versions to be able to hack.
You're given an array a of length n , and an array b of length m (bi>bi+1 for all 1≤i<m ). Initially, the value of k is 1 . Your aim is to make the array a empty by performing one of these two operations repeatedly:
Type 1 — If the value of k is less than m and the array a is not empty, you can increase the value of k by 1 . This does not incur any cost. Type 2 — You remove a non-empty prefix of array a , such that its sum does not exceed bk . This incurs a cost of m−k . You need to minimize the total cost of the operations to make array a empty. If it's impossible to do this through any sequence of operations, output −1 . Otherwise, output the minimum total cost of the operations, and the number of sequences of operations which yield this minimum cost modulo 109+7 .
Two sequences of operations are considered different if you choose a different type of operation at any step, or the size of the removed prefix is different at any step.
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1000 ). The description of the test cases follows.
The first line of each test case contains two integers n and m (1≤n,m≤3⋅105 , 1≤n⋅m≤3⋅105 ).
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109 ).
The third line of each test case contains m integers b1,b2,…,bm (1≤bi≤109 ).
It is also guaranteed that bi>bi+1 for all 1≤i<m .
It is guaranteed that the sum of n⋅m over all test cases does not exceed 3⋅105 .
Output For each test case, if it's possible to make a empty, then output two integers. The first should be the minimum total cost of the operations, and the second should be the number of sequences of operations which achieve this minimum cost, modulo 109+7 .
If there is no possible sequence of operations which makes a empty, then output a single integer −1 .
Example InputCopy 5 4 2 9 3 4 3 11 7 1 2 20 19 18 10 2 2 5 2 1 10 3 2 9 9 6 17 9 10 11 2 2 2 2 2 2 2 2 2 2 20 18 16 14 12 10 8 6 4 2 1 1 6 10 32 16 8 4 2 1 OutputCopy 1 3 -1 2 11 10 42 4 1 Note In the first test case, there are 3 optimal sequences of operations which yield a total cost of 1 :
All 3 sequences begin with a type 2 operation, removing the prefix [9] to make a=[3,4,3] , incurring a cost of 1 . Then, we perform a type 1 operation to increase the value of k by 1 . All subsequent operations now incur a cost of 0 . One sequence continues by removing the prefixes [3,4] then [3] . Another sequence continues by removing the prefixes [3] then [4,3] . Another sequence continues by removing the prefixes [3] then [4] then [3] . In the second test case, it's impossible to remove any prefix of the array since a1>b1 , so array a cannot be made empty by any sequence of operations.
type code in c++
- Assistant
To solve this problem, we need to efficiently determine the minimum total cost required to make the array
aempty by performing a series of operations, and also calculate the number of distinct sequences that achieve this minimum cost. Here's the step-by-step reasoning to approach this problem:Problem Breakdown
-
Operation Types:
- Type 1: Increment
kby 1 ifk < m. This operation is free. - Type 2: Remove a prefix of the array
asuch that the sum of the prefix does not exceedb[k]. This incurs a cost ofm - k.
- Type 1: Increment
-
Goal:
- Minimize the total cost to make array
aempty. - Count the number of distinct sequences of operations that achieve this minimum cost.
- Minimize the total cost to make array
-
Approach:
- We'll use dynamic programming (DP) to keep track of both the minimum cost and the number of ways to achieve that cost up to each position in array
a. - We use a segment tree to efficiently query the minimum cost in a range and count the number of ways to achieve that cost within that range.
- We'll use dynamic programming (DP) to keep track of both the minimum cost and the number of ways to achieve that cost up to each position in array
Step-by-Step Solution
-
Preprocessing:
- For each test case, compute the prefix sums of the array
ato easily calculate the sum of any subarray. - Check if any element in
ais greater thanb[1](the largest value inb). If so, it's impossible to empty the array using the given operations, and we output-1.
- For each test case, compute the prefix sums of the array
-
Dynamic Programming Setup:
- Define
dp[i]as the minimum cost to make the firstielements ofaempty. - Define
cnt[i]as the number of ways to achievedp[i]. - Initialize
dp[0] = 0(no cost for an empty array) andcnt[0] = 1(one way to achieve zero cost).
- Define
-
Using a Segment Tree:
- A segment tree helps efficiently find the minimum
dp[j]for a range of indices. - For each position
iina:- Use binary search to find the largest possible
ksuch that removing a prefix ending atiwith sum ≤b[k]is possible. - Once the optimal
kis found, determine the range of indicesjwhere such a removal is possible. - Query the segment tree for the minimum
dp[j]in this range and updatedp[i]andcnt[i]accordingly.
- Use binary search to find the largest possible
- A segment tree helps efficiently find the minimum
-
Final Result:
- After processing all elements,
dp[n]will hold the minimum total cost to make the array empty. cnt[n]will hold the number of distinct sequences to achieve this cost.- If
dp[n]is still infinity (i.e., the array cannot be emptied), output-1.
- After processing all elements,
Implementation in C++
Below is the C++ implementation based on the above reasoning. This implementation uses a segment tree to efficiently calculate the minimum cost and count the number of ways to achieve that cost for each position in the array.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9+7; const ll INF = 4e18; struct Node { ll min_val; ll cnt; } tree_node; struct SegTree { int size; vector<Node> tree; SegTree(int n){ size = 1; while(size < n) size <<=1; tree.assign(2*size, Node{INF, 0}); } void update_set(int pos, ll val, ll cnt_val){ pos += size; if(val < tree[pos].min_val){ tree[pos].min_val = val; tree[pos].cnt = cnt_val; } else if(val == tree[pos].min_val){ tree[pos].cnt = (tree[pos].cnt + cnt_val) % MOD; } // else do nothing pos /=2; while(pos >=1){ ll left = tree[2*pos].min_val; ll right = tree[2*pos+1].min_val; if(left < right){ if(left != tree[pos].min_val){ tree[pos].min_val = left; tree[pos].cnt = tree[2*pos].cnt; } } else if(right < left){ if(right != tree[pos].min_val){ tree[pos].min_val = right; tree[pos].cnt = tree[2*pos+1].cnt; } } else{ if(left != tree[pos].min_val){ tree[pos].min_val = left; tree[pos].cnt = (tree[2*pos].cnt + tree[2*pos+1].cnt) % MOD; } else{ tree[pos].cnt = (tree[2*pos].cnt + tree[2*pos+1].cnt) % MOD; } } pos /=2; } } pair<ll, ll> query_min_cnt(int l, int r){ ll res = INF; ll res_cnt =0; l += size; r += size; while(l <=r){ if(l%2 ==1){ if(tree[l].min_val < res){ res = tree[l].min_val; res_cnt = tree[l].cnt; } else if(tree[l].min_val == res){ res_cnt = (res_cnt + tree[l].cnt) % MOD; } l++; } if(r%2 ==0){ if(tree[r].min_val < res){ res = tree[r].min_val; res_cnt = tree[r].cnt; } else if(tree[r].min_val == res){ res_cnt = (res_cnt + tree[r].cnt) % MOD; } r--; } l /=2; r /=2; } return {res, res_cnt}; } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--){ int n, m; cin >> n >> m; vector<ll> a(n); for(auto &x: a) cin >> x; vector<ll> b(m); for(auto &x: b) cin >> x; // Check if any a[i] > b[0} bool impossible = false; for(auto &x: a){ if(x > b[0]){ impossible = true; break; } } if(impossible){ cout << "-1\n"; continue; } // Compute prefix sums vector<ll> s(n+1, 0); for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i-1]; // Initialize dp and cnt // Initialize segment tree SegTree st(n+1); // dp[0} =0, cnt[0} =1 // Update position 0 st.update_set(0, 0, 1); // dp and cnt arrays vector<ll> dp(n+1, INF); vector<ll> cnt_dp(n+1, 0); dp[0] =0; cnt_dp[0] =1; for(int i=1;i<=n;i++){ // Binary search on k from1 to m to find maximum k int low=1, high=m, answer=-1; while(low <=high){ int mid = low + (high -low)/2; ll target = s[i] - b[mid-1]; // Find j_min where s[j} >= target // j can be from0 to i-1 int j_min = lower_bound(s.begin(), s.begin()+i, target) - s.begin(); if(j_min <=i-1){ answer = mid; low = mid +1; } else{ high = mid -1; } } if(answer == -1){ dp[i] = INF; cnt_dp[i] =0; continue; } // Now, k=answer ll k = answer; ll target = s[i] - b[k-1]; // Find j_min where s[j} >= target int j_min = lower_bound(s.begin(), s.begin()+i, target) - s.begin(); // Query the segment tree for [j_min, i-1} pair<ll, ll> res = st.query_min_cnt(j_min, i-1); if(res.first == INF){ dp[i] = INF; cnt_dp[i] =0; } else{ dp[i] = res.first + (m -k); cnt_dp[i] = res.cnt; } // Update the segment tree with dp[i} and cnt_dp[i} if(dp[i] < INF){ st.update_set(i, dp[i], cnt_dp[i]); } } if(dp[n] == INF){ cout << "-1\n"; } else{ cout << dp[n] << " " << cnt_dp[n] << "\n"; } } }Explanation of the Code
-
Segment Tree Implementation:
- The segment tree
SegTreemaintains the minimumdp[j]and counts of how many times this minimum is achieved in a specific range. - The
update_setfunction sets or updates the value at a specific position and appropriately updates the tree. - The
query_min_cntfunction queries a range[l, r]and returns the minimum value in that range along with the count of how many times this minimum appears.
- The segment tree
-
Main Logic:
- For each test case, compute the prefix sums.
- Initialize
dp[0] = 0andcnt_dp[0] = 1. - Iterate through each position
iin arraya:- Perform a binary search to find the maximum
ksuch that a prefix removal is possible. - Once
kis determined, find the minimumjsuch that removing the segment[j+1, i]satisfies the sum constraint. - Query the segment tree to find the minimum
dp[j]within the valid range and updatedp[i]andcnt_dp[i]accordingly.
- Perform a binary search to find the maximum
- After processing all positions, output the result for the test case.
-
Handling Multiple Test Cases:
- The program efficiently handles multiple test cases by resetting the segment tree for each new test case.
Conclusion
This approach effectively minimizes the total cost while efficiently counting the number of sequences that achieve this cost using dynamic programming and a segment tree for optimal range queries. The solution ensures accuracy and efficiency within the given constraints.
-