-grace-'s blog

By -grace-, history, 2 months ago, In English

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

Problem 1

Problem 2

 
 
 
 
  • Vote: I like it
  • +46
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by -grace- (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can it be solved using seg trees? What will each node represent in that?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        array of string Seg[4*n];

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        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, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Yes, storing frequency is a better way to go.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you share your code for the 1st problem?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Here is my code. I calculated the prefix array of frequency for every 26 characters.

      Spoiler
»
2 months ago, # |
  Vote: I like it +38 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do we have to sort the strings first before calculating prefix sum ?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      count of characters will be the same for the string irrespective of sorting.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    and we can binary search to process each query in log(26).

    complexity — O(n * 26) + O(Q * log(26)).

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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   Vote: I like it +12 Vote: I do not like it

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, # |
  Vote: I like it +1 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

here is my segment tree solution for the first question.

»
2 months ago, # |
Rev. 2   Vote: I like it +26 Vote: I do not like it

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, # |
  Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Correct approach acc. to me. Only challenge will be to check for Dirty Cells.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it +8 Vote: I do not like it

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, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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, # ^ |
        Vote: I like it +4 Vote: I do not like it

      You can find it in terms of x and y and put values for each query.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, brother! for pointing out. I got your point

»
2 months ago, # |
Rev. 8   Vote: I like it +1 Vote: I do not like it

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