I was asked to solve two problems. There are really good problems so I would like to discuss them here.
Problem 1
You are given an array of strings. You have to process Q queries of the type — "L R k". For each query, print the kth character of the string formed by merging all the strings from L to R and sorting them.
Constraints
N<=1e5 Q<=1e5
There is always a valid kth position
There is always a valid kth position
Example
Input: N = 3, strs = ["abcc", "trea", "zape"], Q= [ "2 3 5", "2 2 1"]
Output: p a
For first query, concatenated string is "treazape". After sorting, it becomes "aaeeprtz". 5th character is 'p'. For second query, concatenated string is "trea". After sorting becomes "aert". 1st character is 'a'.
Output: p a
For first query, concatenated string is "treazape". After sorting, it becomes "aaeeprtz". 5th character is 'p'. For second query, concatenated string is "trea". After sorting becomes "aert". 1st character is 'a'.
Problem 2
There is an array of length N. Some places are empty (E), some are dirty (D), and some have food on it (F). You have to group all the food into consecutive cells with the following rules-
— Moving food to adjacent cell costs 'x' amount of coins
— Cleaning a dirty cell costs 'y' coins
— After cleaning, the dirty cell becomes empty
— You can only move food to an adjacent empty cell
Now, you have to process Q queries of the type "x y". In each query, print the minimum cost required to group all foods together.
— Moving food to adjacent cell costs 'x' amount of coins
— Cleaning a dirty cell costs 'y' coins
— After cleaning, the dirty cell becomes empty
— You can only move food to an adjacent empty cell
Now, you have to process Q queries of the type "x y". In each query, print the minimum cost required to group all foods together.
Constraints
1 <= N, Q<=1e5 0 <= x, y <=1e5
Example
N = 5, Array = "FEDEF", x=1, y=2
It is optimal to first clean the dirty cell at position 3, this will cost 2 amount of coins. After cleaning the array becomes — "FEEEF". Now we can move foods in the following manner — "EFFEE". This will cost 3*1 = 3 coins. So final cost will be 3+2 = 5
It is optimal to first clean the dirty cell at position 3, this will cost 2 amount of coins. After cleaning the array becomes — "FEEEF". Now we can move foods in the following manner — "EFFEE". This will cost 3*1 = 3 coins. So final cost will be 3+2 = 5