You have an array of integers π1,π2,β¦,ππ of length π. On the π-th of the next πβ¦
- User
You have an array of integers π1,π2,β¦,ππ of length π. On the π-th of the next π days you are going to do exactly one of the following two actions:
Add 1 to each of the first ππ elements of the array π (i.e., set ππ:=ππ+1 for each 1β€πβ€ππ). Count the elements which are equal to their position (i.e., the ππ=π). Denote the number of such elements as π. Then, you add π to your score, and reset the entire array π to a 0-array of length π (i.e., set [π1,π2,β¦,ππ]:=[0,0,β¦,0]). Your score is equal to 0 in the beginning. Note that on each day you should perform exactly one of the actions above: you cannot skip a day or perform both actions on the same day.
What is the maximum score you can achieve at the end?
Since π can be quite large, the sequence π is given to you in the compressed format:
You are given a sequence of integers π£1,π£2,β¦,π£π. The sequence π is a concatenation of infinitely many copies of π£: π=[π£1,π£2,β¦,π£π,π£1,π£2,β¦,π£π,β¦]. Input The first line contains a single integer π‘ (1β€π‘β€103) β the number of test cases.
The first line of each test case contains three integers π, π and π (1β€πβ€2000, 1β€πβ€105, πβ€πβ€109) β the length of the array π, the length of the sequence π£ and the number of days you are going to perform operations on.
The second line of each test case contains π integers π1,π2,β¦,ππ (0β€ππβ€π) β the array π.
The third line of each test case contains π integers π£1,π£2,β¦,π£π (1β€π£πβ€π) β the sequence π£.
It is guaranteed that the sum of π over all test cases doesn't exceed 2000 and the sum of π over all test cases doesn't exceed 105.
Output For each test case, output one integer: the maximum score you can achieve at the end of the π-th day.
- Assistant
To solve this problem, we must maximize the total score by strategically performing operations over
ddays on an arrayaof lengthn. Each day, we have two choices:- Add Operation: Add 1 to the first
b_ielements of the arraya. - Count and Reset Operation: Count the number of elements in the array that are equal to their indices, add this number to the score, and reset the array to all zeros.
The sequence
bis provided in a repeating pattern, defined by a sequencevof lengthk. The goal is to determine the optimal schedule of these operations to maximize the score afterddays.Detailed Approach:
-
Preprocessing:
- For each value of
jfrom1ton, compute the number of daysc_jin the sequencevwherev_i >= j. - Also, for each
j, create a listdays_jthat contains the days whenv_i >= j.
- For each value of
-
Identifying Valid Segments:
- For each
j, determine the number of operation dayssrequired such that aftersoperation days, thej-thelement of the arrayaequalsj. - This involves solving for
sin the equationt * c_j + count_j(r) = j, wheretis the number of full periods insdays, andris the remainder days after complete periods. - For each valid
s, count how manyjsatisfy the condition.
- For each
-
Maximizing the Score:
- Use a
Counterto track how manyjvalues are satisfied for each possibles. - Identify the
sthat maximizes the number of satisfiedjvalues (i.e.,c(s), the number of elements wherea_j == j). - Calculate the number of complete blocks
mof operations (each block consisting ofsoperation days plus one count/reset operation day) that fit withinddays. - The total score is then
m * c(s).
- Use a
-
Edge Cases:
- Handle scenarios where no valid operations can be performed within the given days.
- Ensure that
sdoes not exceeddwhen calculating the number of blocks.
Implementation:
The implementation uses efficient data structures and algorithms to handle the constraints, especially considering the large possible values of
d(up to10^9). Here's the Python solution encapsulating the above approach:import sys import threading import bisect from collections import defaultdict, Counter def main(): import sys t = int(sys.stdin.readline()) for _ in range(t): n, k, d = map(int, sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) v = list(map(int, sys.stdin.readline().split())) # Precompute for each j, list_days_j[j] and c_j[j] list_days_j = [[] for _ in range(n +1)] # 1-based for idx, val in enumerate(v,1): for j in range(1, val +1): if j <=n: list_days_j[j].append(idx) c_j = [0]*(n +1) for j in range(1, n +1): c_j[j] = len(list_days_j[j]) list_s = [] for j in range(1, n +1): if c_j[j] >0: t_max = j // c_j[j] for t in range(t_max +1): r = j - t *c_j[j] if 0 <=r <k: # count_j[r] = number of days <=r where v_i >=j # list_days_j[j] is sorted count_jr = bisect.bisect_right(list_days_j[j], r) if count_jr == r: s = t *k + r list_s.append(s) counter = Counter(list_s) if not counter: max_count =0 best_s =1 # arbitrary, since no s gives any c(s) else: max_count = max(counter.values()) # Find the smallest s with max_count best_s = min(s for s, cnt in counter.items() if cnt ==max_count) if max_count ==0: print(0) continue m = d // (best_s +1) total_score = m *max_count print(total_score) threading.Thread(target=main,).start()This code efficiently handles multiple test cases by preprocessing the necessary counts and selecting the optimal number of operation segments to maximize the score. The use of
bisectfor binary search operations ensures that the solution remains performant even for large inputs. - Add Operation: Add 1 to the first