### -grace-'s blog

By -grace-, history, 2 months ago,

I was asked to solve two problems. There are really good problems so I would like to discuss them here.

Problem 1

Problem 2

• +46

 » 2 months ago, # |   0 Auto comment: topic has been updated by -grace- (previous revision, new revision, compare).
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 2 months ago, # ^ |   0 How can it be solved using seg trees? What will each node represent in that?
•  » » » » 2 months ago, # ^ |   0 array of string Seg[4*n];
•  » » » » 2 months ago, # ^ |   +29 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
•  » » » » » 2 months ago, # ^ |   +3 Yes, storing frequency is a better way to go.
•  » » 2 months ago, # ^ |   0 Can you share your code for the 1st problem?
•  » » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   +5 Here is my code. I calculated the prefix array of frequency for every 26 characters. Spoiler#include using namespace std; #define ll long long int void solve(){ int n; cin>>n; string s[n]; int f[n+1][26]; memset(f,0,sizeof(f)); for(int i=0;i>s[i]; for(int j=0;j<26;j++){ f[i+1][j]=f[i][j]; } for(int j=0;j>q; while(q--){ int l,r,k; cin>>l>>r>>k; for(int i=0;i<26;i++){ if((f[r][i]-f[l-1][i])>=k){ cout<>tc; for(ll t=0;t
 » 2 months ago, # |   +38 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).
•  » » 2 months ago, # ^ |   0 Do we have to sort the strings first before calculating prefix sum ?
•  » » » 2 months ago, # ^ |   0 count of characters will be the same for the string irrespective of sorting.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +6 and we can binary search to process each query in log(26). complexity — O(n * 26) + O(Q * log(26)).
 » 2 months ago, # |   +8 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.
 » 2 months ago, # | ← Rev. 2 →   +12 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.
 » 2 months ago, # |   +1 I think in the second one we have to bring all the foods on the median irrespective of the values x and y have. .
 » 2 months ago, # |   0 here is my segment tree solution for the first question.
 » 2 months ago, # | ← Rev. 2 →   +26 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.
 » 2 months ago, # |   +6 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.
•  » » 2 months ago, # ^ |   0 Correct approach acc. to me. Only challenge will be to check for Dirty Cells.
 » 2 months ago, # |   0 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.
 » 2 months ago, # | ← Rev. 2 →   +8 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.
•  » » 2 months ago, # ^ |   +4 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.
•  » » » 2 months ago, # ^ |   +4 You can find it in terms of x and y and put values for each query.
•  » » » » 2 months ago, # ^ |   0 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?
•  » » » » » 2 months ago, # ^ |   0 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).
 » 2 months ago, # | ← Rev. 2 →   0 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
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 Thanks, brother! for pointing out. I got your point
 » 2 months ago, # | ← Rev. 8 →   +1 Sweet Simple elegant solution for Problem 1. TC — O(total_char_count_array), SC — O(26*n) n->size of arrayNO SEGMENT TREE, NO FANCY DATA STRUCTURE. JUST USING PREFIX SUM!!https://ideone.com/bX7nbDWell 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