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
Auto comment: topic has been updated by -grace- (previous revision, new revision, compare).
I thought of merge sort trees first for the 1st problem, but it gave TLE as expected. So I used prefix sums and it worked. I couldn't complete the second one in time because I wasted too much time on the first problem.
I think 1st problem can be solved using a segment tree with complexity of N*logN for building the tree. queries are of logN time tho.
How can it be solved using seg trees? What will each node represent in that?
It will be an array of size 26 to store frequency of characters but in this problem, there is no update so we can do prefix sum
Yes, storing frequency is a better way to go.
Can you share your code for the 1st problem?
I don't have the code with me. We had to code on the testing platform itself.
See Aman_j1's comment. My approach was same.
Here is my code. I calculated the prefix array of frequency for every 26 characters.
For the first problem, we can maintain just prefix sums for each character, i.e pre[i][c]. Then for each query, we can just iterate over all characters from 'a' to 'z' and have total characters till now and when it becomes >= K, we got our answer for the query as the current character. Time complexity: O(Q*26).
Do we have to sort the strings first before calculating prefix sum ?
count of characters will be the same for the string irrespective of sorting.
and we can binary search to process each query in log(26).
complexity — O(n * 26) + O(Q * log(26)).
For the second problem, my approach is something like this: 1. Clean all dirty cells which have cells with food on both its sides, as you would not be able to group together those foods otherwise. 2. Fix the food which is the median of all the food cells and collect all the food around it. For example, if we have configuration FEEEFEFFEEF, then as there are 5 cells with food, the third food is the median. So, the final optimal configuration would be EEEEFFFFFEE.
Was this on-campus?
For problem A, for each character from 'a' to 'z', we can quickly find the count of the each character. For instance from 1 to 5, we might have 2 — 'a', 0 — 'b', 1 — 'c' etc. After this we can binary search the first alphabet such that, the number of alphabets before this is greater than or equal to k.
I think in the second one we have to bring all the foods on the median irrespective of the values x and y have. .
Problem 2 : Find the first and last occurrence of 'F', let them be l and r. We don't care about anything before l and after r. Let cnt = total number of F. Make all the D's in between l and r to E using y coins for each. Now the problem is same as : https://codeforces.com/contest/1520/problem/E I did that using prefix sums, that is grouping all F from (i to i + cnt — 1) for all i from l to r.
Why are there such complicated solutions like merge-sort trees mentioned in the comments for the first problem? XD
I think for the 2nd problem, since no F's will actually cross each other, we can iterate on each position and lets suppose we bring all Fs together at this position.
So all Fs to the left will come here one-by-one, and all rights similarly. We would have to maintain the number of dirty cells between the F's initial position and final position.
I'm not completely sure, but I think that can be implemented using some pref and suff sums.
Correct approach acc. to me. Only challenge will be to check for Dirty Cells.
For the 2nd problem we can consider the fact that whenever such kind of merging of items are required in a line the we always merge on the median of elements(middle value in set of elements), in this case we can count the no. of food items find the middle elements and calculate the no. of steps required to do it. Let the no. of steps required to do it be S. Then we can calculate the dirty elements between the last and the first food item and remove them all(to merge food items we would always require to remove all these dirty items in between). Let the no. of dirty elements in between 1st and Last food be L. Then the answer for each query can be just X*S + L*Y in O(1) time.
2nd question 1520E - Arranging The Sheep For each point consider the number of steps requires to move prefix of food to that position +suffix of food to that position i.e $$$min(pref[i-1]+suf[i],pref[i]+suf[i+1])$$$ , precalculate these $$$pref$$$ and $$$suf$$$ arrays.
The values of X and Y are different for queries. We cannot calculate pref and suf arrays for each query separately I think. Or maybe.........I am not understanding your approach. Not sure.
You can find it in terms of x and y and put values for each query.
Say the number of shift operations for the ith index is ai and clean operations is bi, the total cost would be ai*X + bi*Y. This is in terms of X and Y
How would you minimise this over all n indices?
See, all dirty marked cells in between first and last F must be cleaned to bring all of them together. So we have the cost due to dirty cells (which will be constant for each query). Now dirty cells are removed, now we have to bring all F marked cells to the median and for that median cell, we will store the value in terms of x and y. So, now each query can be answered in O(1).
Both the questions were interesting and implementation based. I really enjoyed solving the questions. I am attaching the links of source code for both the questions and if someones find any bug or any corner cases that are missing in my implementation, then please do comment for the same.
In the previous version, problem 1 is more prone to TLE as I was building the entire string for each query.
problem 1 : https://ideone.com/yC3l2N [updated]
problem 2 : https://ideone.com/thBN2d
There is no need of building the string in the first problem, will give TLE. As consider 1e5 queries each being (1,n) then you will you building the complete string again and again, so that will be O(n* n). For each query, just maintain total characters till now, as soon as it becomes >=k you found your character.
Sweet Simple elegant solution for Problem 1. TC — O(total_char_count_array), SC — O(26*n) n->size of array
NO SEGMENT TREE, NO FANCY DATA STRUCTURE. JUST USING PREFIX SUM!!
https://ideone.com/bX7nbD
Well Commented Solution for Problem 2. TC — O(n + q) SC — O(1), Process each Query O(1)
TL;DR -> get leftmost-rightmostF O(N)
D-> no. of dirty cells in between O(N)
F->minimum operations to club all 'F' together(remains constant) O(N) (*check my code for explanation)
For each {x,y} ans-> x*F + y*D O(1)
https://ideone.com/RVSDZp