Блог пользователя -grace-

Автор -grace-, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    3 года назад, # ^ |
    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you share your code for the 1st problem?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      Spoiler
»
3 года назад, # |
  Проголосовать: нравится +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).

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
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.

»
3 года назад, # |
  Проголосовать: нравится +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. .

»
3 года назад, # |
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://mirror.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.

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится 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.

»
3 года назад, # |
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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 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).

»
3 года назад, # |
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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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.

»
3 года назад, # |
Rev. 8   Проголосовать: нравится +1 Проголосовать: не нравится

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