I was asked to solve two problems. There are really good problems so I would like to discuss them here.↵
↵
<spoiler summary="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.↵
<spoiler summary="Constraints">↵
N<=1e5↵
Q<=1e5 <br/>↵
There is always a valid kth position↵
</spoiler>↵
<spoiler summary="Example">↵
Input:↵
N = 3, strs = ["abcc", "trea", "zape"], Q= [ "2 3 5", "2 2 1"] <br/>↵
Output: p a <br/>↵
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'. ↵
</spolier>↵
</spoiler>↵
↵
<spoiler summary="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- <br/>↵
— Moving food to adjacent cell costs 'x' amount of coins <br/>↵
— Cleaning a dirty cell costs 'y' coins <br/>↵
— After cleaning, the dirty cell becomes empty <br/>↵
— You can only move food to an adjacent empty cell <br/>↵
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.↵
<spoiler summary="Constraints">↵
1 <= N, Q<=1e5↵
0 <= x, y <=1e5↵
There is always a valid kth position↵
</spoiler>↵
<spoiler summary="Example">↵
N = 5, Array = "FEDEF", x=1, y=2 <br/>↵
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↵
</spolier>↵
</spoiler>↵
↵
↵
<spoiler summary="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.↵
<spoiler summary="Constraints">↵
N<=1e5↵
Q<=1e5 <br/>↵
There is always a valid kth position↵
</spoiler>↵
<spoiler summary="Example">↵
Input:↵
N = 3, strs = ["abcc", "trea", "zape"], Q= [ "2 3 5", "2 2 1"] <br/>↵
Output: p a <br/>↵
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'. ↵
</spolier>↵
</spoiler>↵
↵
<spoiler summary="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- <br/>↵
— Moving food to adjacent cell costs 'x' amount of coins <br/>↵
— Cleaning a dirty cell costs 'y' coins <br/>↵
— After cleaning, the dirty cell becomes empty <br/>↵
— You can only move food to an adjacent empty cell <br/>↵
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.↵
<spoiler summary="Constraints">↵
1 <= N, Q<=1e5↵
0 <= x, y <=1e5↵
<spoiler summary="Example">↵
N = 5, Array = "FEDEF", x=1, y=2 <br/>↵
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↵
</spolier>↵
</spoiler>↵
↵
