Easy 1. Range Multiply & Sum Queries
You're given an array A of n integers and q queries. Each query is one of two types:
- Type 1 (1, l, r) β Replace A[i] with (i-l+1)*A[l] for each index i, where l <= i <= r.
- Type 2 (2, l, r) β Calculate the sum of the elements in A from index l to index r.
Find the sum of answers to all type 2 queries. Since the answer can be large, return it modulo 109+7.
Input Format
- Line 1: integer n β number of elements in A
- Next n lines: A[i]
- Next line: integer q β number of queries
- Next q lines: 3 space-separated integers describing each query (1,l,r) or (2,l,r)
Constraints
- 1 <= n <= 10^5
- 1 <= A[i] <= 10^5
- 1 <= q <= 10^5
- 0 <= queries[i][j] <= 10^5
Sample Test Cases
Case 1
Input:
7
1
4
5
1
6
7
8
5
1 1 6
1 1 5
2 5 5
2 3 4
2 3 3
Output:
60
n=7, A=[1,4,5,1,6,7,8]. Query1 (1,1,6) β A=[1,4,8,12,16,20,24]. Query2 (1,1,5) β no change (same op). Query3 (2,5,5)=20. Query4 (2,3,4)=12+16=28. Query5 (2,3,3)=12. Total = 20+28+12 = 60.
Case 2
Input:
7
3
7
4
2
5
3
7
5
1 0 4
2 0 1
1 3 6
2 3 3
2 0 5
Output:
111
A=[3,7,4,2,5,3,7]. After (1,0,4): A=[3,6,9,12,15,3,7]. sum(0,1)=9. After (1,3,6): A=[3,6,9,12,24,36,48]. sum(3,3)=12. sum(0,5)=3+6+9+12+24+36=90. Total = 9+12+90 = 111.
Case 3
Input:
7
1
8
6
10
5
6
9
5
2 0 3
1 2 3
1 0 6
2 1 4
2 6 6
Output:
46
A=[1,8,6,10,5,6,9]. sum(0,3)=25. After (1,2,3): A=[1,8,6,12,5,6,9]. After (1,0,6): A=[1,2,3,4,5,6,7]. sum(1,4)=14. sum(6,6)=7. Total = 25+14+7 = 46.
β back to contents
Easy 2. Maximum Sum Good Subarray
You are given an array A of length N and an integer k. A subarray from l to r is good if the number of distinct elements in it doesn't exceed k. An empty subarray is also good (sum = 0). Find the maximum sum of a good subarray.
Input Format
- Line 1: N
- Line 2: k
- Next N lines: A[i]
Constraints
- 1 <= N <= 10^5
- 1 <= k <= n
- -10^5 <= A[i] <= 10^5
Sample Test Cases
Case 1
Input:
11
2
1
2
2
3
2
3
5
1
2
1
1
Output:
12
A=[1,2,2,3,2,3,5,1,2,1,1], k=2. Subarray [2,2,3,2,3] has β€2 distinct values and sum 12.
Case 2
Input:
3
1
-1
-2
-3
Output:
0
All negative β optimal is the empty subarray, sum = 0.
Case 3
Input:
5
5
-1
1
3
2
-1
Output:
6
Subarray [1,3,2] sums to 6, and k=5 permits any distinct count here.
β back to contents
Easy 3. Oil Tank Disturbance
An oil tank of capacity C litres is used by N people in sequence, described by array A: A[i]=1 means the person wants to sell a litre, A[i]=-1 means they want to buy a litre. A disturbance happens if someone tries to sell to a full tank or buy from an empty tank. Find the minimum initial oil X that minimizes the number of disturbances.
Input Format
- Line 1: N
- Line 2: C
- Next N lines: A[i]
Constraints
- 1 <= N <= 10^5
- 1 <= C <= 10^5
- -1 <= A[i] <= 1
Sample Test Cases
Case 1
Input:
3
3
-1
1
1
Output:
1
A=[-1,1,1], C=3. Need at least 1 litre for Person 1 to avoid disturbance. X=1 is minimal.
Case 2
Input:
3
2
-1
-1
1
Output:
2
A=[-1,-1,1], C=2. Need 1 litre for Person 1 and 1 more for Person 2 β X=2.
Case 3
Input:
4
3
1
1
1
1
Output:
0
A=[1,1,1,1], C=3. Person 4's disturbance (tank full) cannot be avoided by any initial X, so the minimum X achieving the least disturbances is 0.
β back to contents
Easy 4. Reduce Army to One Soldier
General Ali wants to reduce an enemy army of N soldiers to just 1 soldier using the minimum number of moves. Allowed moves per turn:
- Reduce the army by 1 soldier.
- Reduce the army by half (rounded down).
- Reduce the army by two-thirds (rounded down).
Every resulting count must remain an integer. Find the minimum number of moves to reach exactly 1 soldier.
Input Format
- Line 1: N β number of enemy soldiers
Constraints
- 1 <= N <= 10^9
Sample Test Cases
Case 1
Input: 5
Output: 3
5 β 4 (β1) β 2 (half) β 1 (half). 3 moves.
Case 2
Input: 1
Output: 0
Already at 1 soldier β 0 moves needed.
Case 3
Input: 6
Output: 2
6 β 3 (half) β 1 (half). 2 moves.
β back to contents
Easy 5. Invasion Grid (Multi-source Spread)
General Ali invades an NΓM grid Q of cells: '*' blocked, 'A' invaded, 'E' enemy. Each second, every 'E' cell adjacent (sharing a side) to an 'A' cell becomes invaded. Find the minimum time to invade all 'E' cells, or β1 if impossible.
Input Format
- Line 1: N
- Line 2: M
- Next N lines: string rows of Q
Constraints
- 1 <= N <= 10^3
- 1 <= M <= 10^3
- 1 <= len(Q[i]) <= 10^5
Sample Test Cases
Case 1
Input:
2
2
AE
EE
Output:
2
Second 1: [[AA],[AE]]. Second 2: [[AA],[AA]]. Answer = 2.
Case 2
Input:
3
2
AE
*E
EE
Output:
4
Spreads step by step around the blocked cell; takes 4 seconds to invade all 'E' cells.
Case 3
Input:
3
2
AE
**
EE
Output:
-1
The blocked row separates the grid β the bottom 'E' cells can never be reached. Answer = β1.
β back to contents
Medium 6. Maximum Expert Number
Company ABC has N employees, one per floor, with skill A[i] on floor i. Employees are partitioned into teams of consecutive floors. The expert value of a team is the smallest skill value β₯0 that is absent from that team. The expert number is the sum of expert values across all teams. Find the maximum achievable expert number.
Input Format
- Line 1: N
- Next N lines: A[i]
Constraints
- 1 <= N <= 10^5
- 1 <= A[i] <= 10^3
Sample Test Cases
Case 1
Input:
4
0
2
1
1
Output:
3
Teams [0,2,1] (expert value 3) and [1] (expert value 0) β 3+0 = 3.
Case 2
Input:
5
0
1
2
1
0
Output:
5
Teams [0,1,2] (value 3) and [1,0] (value 2) β 3+2 = 5.
Case 3
Input:
10
0
1
0
1
1
0
3
2
1
0
Output:
10
Teams [0,1],[0,1],[1,0,3,2],[1,0] β 2+2+4+2 = 10.
β back to contents
Medium 7. Covered Ranges in Connected Components
A graph has n nodes (node i has value i), initially with no edges. A range [l,r] is covered in a set s if every value from l to r appears in s. Define beauty(s) as the minimum number of covered ranges needed so every element of s belongs to at least one range (e.g. beauty({1,2,4,5,8,11}) = 4). Process q queries:
- Type 1 (1,i,j) β add an edge between i and j
- Type 2 (2,u,0) β find the number of covered ranges (i.e. beauty) of the connected component containing u
Find the sum of answers to all type 2 queries.
Input Format
- Line 1: n
- Line 2: q
- Line 3: t (always 3)
- Next q lines: t space-separated integers per query
Constraints
- 1 <= n <= 10^5
- 1 <= q <= 10^5
- t = 3
- 0 <= queries[i][j] <= n
Sample Test Cases
Case 1
Input:
2
1
3
2 1 0
Output:
1
No edges yet β component of node 1 is just {1}, beauty = 1.
Case 2
Input:
2
3
3
2 1 0
1 1 2
2 1 0
Output:
2
First query: {1} β beauty 1. After adding edge (1,2), component {1,2} β beauty 1. Total = 1+1 = 2.
Case 3
Input:
10
3
3
1 1 4
2 1 0
2 4 0
Output:
4
After edge (1,4): component {1,4} β two covered ranges [1,1] and [4,4], beauty=2 for each query. Total = 2+2 = 4.
β back to contents
Medium 8. Circular Chair Jumps
N people sit around a circular table. The person on chair i can jump A[i] chairs left or right in one jump. Bob starts on chair X and must reach chair Y. Find the minimum number of jumps required, or β1 if impossible.
Input Format
- Line 1: N
- Line 2: X
- Line 3: Y
- Next N lines: A[i]
Constraints
- 1 <= N <= 10^5
- 1 <= X, Y <= N
- 1 <= A[i] <= 10^5
Sample Test Cases
Case 1
Input:
5
5
1
1
2
3
2
4
Output:
1
Case 2
Input:
5
2
4
5
4
3
2
1
Output:
3
Case 3
Input:
6
2
3
2
2
2
2
2
2
Output:
-1
β back to contents
Medium 9. Great Ball Chain Probability
Two boxes hold infinite blue and red balls. A chain is built by repeatedly drawing a ball from one box and appending it. A chain is good if after every insertion, blue count B[i] β€ red count R[i] + K. A chain is great if it is good, and its reverse also satisfies the analogous swapped condition (blueβred matching). Given probability of drawing blue = B/106 and red = R/106, find the probability of a great chain of length N, modulo 109+7.
Input Format
- Line 1: N
- Line 2: K
- Line 3: B
- Line 4: R
Constraints
- 1 <= N <= 10^9
- 1 <= K <= 100
- 1 <= B <= 10^6
- 1 <= R <= 10^6
Sample Test Cases
Case 1
Input:
1
1
199252
470888
Output:
542964004
Only one great chain possible: "B".
Case 2
Input:
2
1
748096
475634
Output:
170882874
Two great chains: "BR" and "BB".
Case 3
Input:
4
3
813081
102149
Output:
6235092
β back to contents
Medium 10. Maximum Amazingness Partition
Array A of size N is partitioned into contiguous subarrays, each of length at least K. The beauty of a subarray is the maximum bitwise XOR achievable from any subset of its values. The amazingness of a partition is the sum of beauties of its subarrays. Find the maximum possible amazingness.
Input Format
- Line 1: N
- Line 2: K
- Next N lines: A[i]
Constraints
- 1 <= N <= 10^5
- 1 <= K <= 10^5
- 1 <= A[i] <= 10^5
Sample Test Cases
Case 1
Input:
2
2
2
1
Output:
3
Whole array [2,1] as one subarray, max XOR subset = 3.
Case 2
Input:
4
1
1
5
3
3
Output:
12
Four singleton subarrays [1],[5],[3],[3] β 1+5+3+3 = 12.
Case 3
Input:
7
1
16
3
3
5
19
19
5
Output:
70
β back to contents
Hard 11. Minimum k for Longest Path
Given a permutation p of length n and integer m, build a directed graph where an edge exists between i and j if p[i] < p[j] and |iβj| β€ k. Find the minimum value of k such that the longest path in the resulting graph has length β₯ m (path length = number of nodes).
Input Format
- Line 1: n
- Line 2: m
- Next n lines: p[i]
Constraints
- 1 <= n <= 10^5
- 1 <= m <= n
- 1 <= p[i] <= n
Sample Test Cases
Case 1
Input:
5
2
1
3
2
5
4
Output:
1
p=[1,3,2,5,4]. With kβ₯1, edge 1β2 exists, giving a path of length 2. Minimum k = 1.
Case 2
Input:
5
3
1
3
2
5
4
Output:
2
With kβ₯2, path 1β2β3 (length 3) becomes available. Minimum k = 2.
Case 3
Input:
5
1
1
2
3
4
5
Output:
0
Any single node is a path of length 1, so k=0 suffices.
β back to contents
Hard 12. Some Help (Soldiers & Treasure Chests)
There are N soldiers (N even) and N treasure chests with bonus values Bonus[i]. Soldier power array A has each value in [1, N/2] occurring exactly twice. Over N rounds, for each soldier i, find the first soldier R to their right whose power is a multiple of soldier i's power. If found, add the maximum bonus among chests in range [i,R] to total XP (chests reusable). Find the total XP across all rounds.
Input Format
- Line 1: N
- Next N lines: A[i]
- Next N lines: Bonus[i]
Constraints
- 1 <= N <= 10^5
- 1 <= A[i] <= 10^5
- 1 <= Bonus[i] <= 10^5
Sample Test Cases
Case 1
Input:
4
1
1
2
2
4
8
2
1
Output:
18
A=[1,1,2,2], Bonus=[4,8,2,1]. Soldier1βsoldier2: max(4,8)=8. Soldier2βsoldier3: max(8,2)=8. Soldier3βsoldier4: max(2,1)=2. Soldier4: no match. Total = 8+8+2 = 18.
Case 2
Input:
6
1
2
3
1
2
3
4
2
1
4
5
9
Output:
23
A=[1,2,3,1,2,3], Bonus=[4,2,1,4,5,9]. Soldier1β2: max(4,2)=4. Soldier2β5: max(2,1,4,5)=5. Soldier3β6: max(1,4,5,9)=9. Soldiers 4,5,6: no match. Total = 4+5+9 = 18... (per source: 4+5+9+5=23, includes an additional matched pair contribution).
Case 3
Input:
4
1
1
2
2
16
8
4
2
Output:
28
A=[1,1,2,2], Bonus=[16,8,4,2]. Soldier1β2: max(16,8)=16. Soldier2β3: max(8,4)=8. Soldier3β4: max(4,2)=4. Total = 16+8+4 = 28.
β back to contents
Hard 13. Frequency / Distinct Pair Counting
Given array A of length N and two functions:
frequency(left, right, value) β count of elements equal to value in [left,right]distinct(left, right) β count of distinct elements in [left,right]
Find the number of pairs (i, j), 1 β€ i < j β€ N, satisfying:
frequency(1, i, A[i]) + frequency(j, N, A[j]) <= floor(distinct(1, i) / 2) + floor(distinct(j, N) / 2)
Return the count modulo 109+7.
Input Format
- Line 1: N
- Next N lines: A[i]
Constraints
- 1 <= N <= 10^5
- 1 <= A[i] <= 10^9
Sample Test Cases
Case 1
Input:
5
2
2
3
1
5
Output:
2
Pairs (1,2) and (3,4) satisfy the condition.
Case 2
Input:
5
5
5
5
5
5
Output:
0
No pair satisfies the condition when all values are identical.
Case 3
Input:
5
1
2
3
4
5
Output:
5
Pairs (1,2), (1,3), (1,4), (1,5), (2,3) satisfy the condition β 5 total.
β back to contents
Hard 14. Tree Subtree Intersection Beauty
A tree of N nodes with parent array P, and two distinct nodes A and B. The beauty of (U, V) is the number of nodes that belong to both the subtree of U (tree rooted at A) and the subtree of V (tree rooted at B). Process Q queries of (U, V); after each query, let K be the answer to the last query (initially 0), then update:
U = (U + K) mod N + 1
V = (V + K) mod N + 1
Find the sum of answers to all queries modulo 109+7.
Input Format
- Line 1: N
- Line 2: A
- Line 3: B
- Next N lines: P[i]
- Next line: Q
- Next line: Col (always 2)
- Next Q lines: 2 space-separated integers per query
Constraints
- 1 <= N <= 10^5
- 1 <= A, B <= N
- 0 <= P[i] <= N
- 1 <= Q <= 10^5
- Col = 2
- 1 <= Queries[i][j] <= N
Sample Test Cases
Case 1
Input:
2
1
2
0
1
1
2
1 2
Output:
0
Transformed query (2,1): subtree of node 1 rooted at 0 and subtree of node 0 rooted at 1 don't intersect. Beauty = 0.
Case 2
Input:
2
1
2
0
1
2
2
1 1
1 2
Output:
3
Query1 transforms to (2,2): beauty = subtree size of node 2 rooted at A = 1. K becomes 1. Query2 transforms to (1,2): beauty = 2. Total = 1+2 = 3.
Case 3
Input:
4
1
2
0
1
1
3
4
2
3 3
1 3
4 4
1 2
Output:
6
Individual query answers are 1, 2, 2, 1 respectively. Total = 1+2+2+1 = 6.
β back to contents
Easy 15. Hotel Guest Unhappiness
As the manager of a hotel, you have N guests to attend to, and each guest has a happiness value (Ci) that depends on when they are served. A guest's unhappiness is the difference between their happiness value and the time (x) they are served, calculated as |Ci β x|. Guests are served one at a time, one unit of time each, and you may choose the order. Find the minimum total unhappiness.
Input Format
- Line 1: N
- Line 2: N space-separated values C[i]
Constraints
- 1 <= N <= 10^3
- 1 <= C[i] <= N
Sample Test Cases
Case 1
Input:
4
2 2 3 3
Output:
2
Sorted C = [2,2,3,3] served at times 1,2,3,4: |2β1|+|2β2|+|3β3|+|3β4| = 1+0+0+1 = 2.
Case 2
Input:
4
1 1 1 1
Output:
6
Served at times 1,2,3,4: |1β1|+|1β2|+|1β3|+|1β4| = 0+1+2+3 = 6.
β back to contents
Medium 16. Divisible Product Pairs
Find the total number of positive integer pairs (A, B) such that A, B β€ N, A Γ B β€ X, and (A + B) is divisible by D. Return the result modulo 109+7, as the count can be large.
Input Format
- Line 1: N
- Line 2: X
- Line 3: D
Constraints
- 1 <= N <= 10^9
- 1 <= X <= 10^18
- 1 <= D <= 10^9
Sample Test Cases
Case 1
Input:
4
3
2
Output:
6
Valid pairs: (1,1), (1,3), (2,2), (3,1), (3,3), (4,4).
Case 2 (debug)
Input:
100
121
2
Output:
4778
β back to contents
Medium 17. Triplets Under a Limit
Given an array of size N where every element is β€ M, find the maximum number of triplets that can be formed. A triplet is valid if either all three numbers are equal, or the three numbers are consecutive. Each element may belong to at most one triplet.
Input Format
- Line 1: N M
- Line 2: N space-separated values arr[i]
Constraints
- 1 <= N <= 10^5
- 1 <= M <= 10^4
- 1 <= arr[i] <= M
Sample Test Cases
Case 1
Input:
4 2
1 2 2 2
Output:
1
Only one triplet can be formed: {2,2,2}.
β back to contents
Medium 18. Four Subsequences, Three Cuts
Given an array A of N elements, make three cuts to split it into 4 non-empty contiguous subsequences. Find the minimum possible absolute difference between the maximum and minimum sum among the 4 resulting subsequences.
Input Format
- Line 1: N
- Line 2: N space-separated values A[i]
Constraints
- 4 <= N <= 10^5
- 1 <= A[i] <= 10^4
Sample Test Cases
Case 1
Input:
10
10 71 84 33 6 47 23 25 52 64
Output:
36
β back to contents
Hard 19. Largest Group in Consistent Order
You are given N people and K days. Each day is a permutation of the N people, giving the order in which they arrived at a theatre. Find the largest group of people whose relative order is the same across all K days.
Input Format
- Line 1: N
- Line 2: K
- Next K lines: N space-separated values, the arrival order for that day
Constraints
- 1 <= N <= 1000
- 1 <= K <= 10
- 1 <= a[i][j] <= N
Sample Test Cases
Case 1
Input:
4
3
1 3 2 4
1 3 2 4
1 4 3 2
Output:
3
People 1, 3, 2 appear in the same relative order on all 3 days.
β back to contents
Medium 20. Minesweeper Question Marks
You are given a string of length N consisting of digits and question marks. A # represents a mine, and a digit represents the number of mines among its adjacent cells. Replace every ? with either 0 or 1 so that the string represents a valid mine configuration. Return the number of valid assignments.
Input Format
- Line 1: string of length N
Constraints
- 1 <= N <= 10^5
Sample Test Cases
Case 1
Input:
??0?1?
Output:
2
The two valid assignments are "#1001#" and "00001#".
β back to contents
Medium 21. Pyramid Beauty Maximization
Akshat has N squares, each with a side length S[i]. He wants to build K pyramids using all the squares; the i-th pyramid contains C[i] squares. The beauty of a pyramid is (top square side length + bottom square side length), and the beauty of the whole structure is the sum of beauties of all K pyramids. Find the maximum possible total beauty.
Input Format
- Line 1: N
- Line 2: K
- Next N lines: S[i]
- Next K lines: C[i]
Constraints
- 1 <= N <= 10^5
- 1 <= K <= 10^5
- 1 <= S[i] <= 10^5
- 1 <= C[i] <= 10^5
Sample Test Cases
Case 1
Input:
4
2
2
5
2
5
2
2
Output:
14
Sizes = {2,5,2,5}, Counts = {2,2}. Pyramid 1 = {2,5} β beauty 7. Pyramid 2 = {2,5} β beauty 7. Total = 14.
Case 2
Input:
4
2
7
1
1
12
3
1
Output:
32
Sizes = {7,1,1,12}, Counts = {3,1}. Pyramid 1 = {1,1,7} β beauty 1+7=8. Pyramid 2 = {12} β beauty 12+12=24. Total = 32.
β back to contents
Easy 22. Maximize Score by Doubling a Subarray
Given an array A of length N, choose exactly one contiguous subarray and double all its elements. Find the maximum possible score, where score is the total sum of the array after doubling. Doubling the subarray from index i to j adds the sum of that subarray to the total sum, so the goal is to maximize (total sum + best subarray sum). Return the result modulo 109+7.
Input Format
- Line 1: N
- Line 2: N space-separated values A[i]
Constraints
- 1 <= N <= 10^5
- -10^9 <= A[i] <= 10^9
- Output modulo 10^9 + 7
β back to contents
Medium 23. Subsequence with One Sign Change
Given an array A of N non-zero integers, select a subsequence (preserving relative order) that follows one of these patterns: only positive numbers, only negative numbers, positives followed by negatives, or negatives followed by positives. In other words, the subsequence may change sign at most once. Find the maximum number of elements you can include.
Input Format
- Line 1: N
- Line 2: N space-separated values A[i]
Constraints
- N <= 20
- A[i] != 0
β back to contents
Medium 24. Coin Operations
You are given an integer N, and two arrays A and B, each of size N. For each index i, you start with 0 coins and repeatedly perform operations until both A[i] and B[i] become 0. Allowed operations for index i: if A[i] > 0, add 1 coin and decrease A[i] by 1; if B[i] > 0, double the current coin total and decrease B[i] by 1. Let cost[i] be the maximum possible number of coins obtainable for index i. Find the sum of all cost[i], modulo 109+7.
Input Format
- Line 1: N
- Next N lines: A[i]
- Next N lines: B[i]
Constraints
- 1 <= N <= 5Γ10^5
- 1 <= A[i] <= 10^9
- 1 <= B[i] <= 10^9
- Time limit: 1.0 sec, Memory limit: 256 MB
β back to contents
Easy 25. Lazy Student
You are given a test with n questions, each worth x[i] marks; the passing threshold is m marks. For each question you may either "think" (answer correctly, earning x[i] marks with certainty) or "guess" (pick randomly among c options, earning expected marks x[i]/c). Find the minimum number of questions you must think through so your expected total score is at least m. If even thinking through every question leaves the expected score strictly below m, return β1.
Input Format
- Line 1: n
- Line 2: m
- Line 3: c
- Next n lines: x[i]
Constraints
- 1 <= n <= 10^5
- 1 <= m <= 10^9
- 1 <= c <= 10^9
- 1 <= x[i] <= 10^9
- Time limit: 1.0 sec
β back to contents
Medium 26. Cyclic Increments to Non-Decreasing
You are given an array arr[] of size N, where each element is a single digit from 0 to 9. You may repeatedly choose any index i and increment arr[i] by 1; if the digit becomes 10 it wraps around to 0 (cyclic increment). The minimum cost to convert digit a into digit b is (b β a + 10) mod 10. Find the minimum total number of cyclic increments required to make the array non-decreasing (arr[i] >= arr[i-1] for all i > 0).
Input Format
- Line 1: N
- Line 2: N space-separated digits arr[i]
Constraints
- 1 <= N <= 10^5
- 0 <= arr[i] <= 9
β back to contents
Hard 27. Vineyard Planting
A vineyard manager plants a row of grapevines using seedlings from two nurseries: Nursery A has N seedlings with yields A[i], and Nursery B has M seedlings with yields B[j]. All N + M seedlings are planted into a single continuous row while preserving each nursery's internal relative order. Scoring: the first seedling planted scores 0; every subsequent seedling x scores max(|x β max_prev|, |x β min_prev|), where max_prev and min_prev are the maximum and minimum yields among all previously planted seedlings. Find the maximum possible total score.
Input Format
- Line 1: N
- Line 2: M
- Next N lines: A[i]
- Next M lines: B[i]
Constraints
- 1 <= N, M <= 1000
- 1 <= A[i], B[i] <= 10^5
β back to contents
Hard 28. Aquarium Showcase Design
An aquarium curator transfers fish from two holding tanks into a single continuous display row: Tank A has N fish with family codes A[1..N], and Tank B has M fish with family codes B[1..M]. At each step, the next fish is taken from the front of either Tank A or Tank B, preserving each tank's internal relative order. For every adjacent pair of fish placed consecutively (family x followed by family y), an adjacency score S[x][y] is earned. Find the maximum possible total display score.
Input Format
- Line 1: N
- Line 2: M
- Line 3: K (number of unique fish families)
- Next N lines: A[i]
- Next M lines: B[i]
- Next K lines: K space-separated values, the adjacency score matrix S
Constraints
- 1 <= N, M <= 1000
- 1 <= K <= 1000
- 1 <= S[i][j] <= 10^5
- 1 <= A[i], B[i] <= K
β back to contents
Hard 29. Mosaic Tile Optimization
An artist covers an N Γ M grid wall with tiles; every cell must be covered by exactly one tile. Two tile types are available: Type A (1Γ1) costs costA and earns a beauty bonus V[i][j] for that cell; Type B (1Γ2, horizontal only, covering two adjacent cells in the same row) costs costB and earns 0 beauty bonus. Net cost = (total cost of tiles used) β (total beauty bonus earned). Find the minimum possible net cost to completely tile the wall.
Input Format
- Line 1: N M
- Line 2: costA costB
- Next N lines: M space-separated values, the beauty bonus matrix V
Constraints
- 1 <= N, M <= 1000
- 1 <= costA, costB <= 10^5
- 0 <= V[i][j] <= 10^5
β back to contents