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

Автор deltixlab, 3 года назад, перевод, По-русски
Tutorial is loading...

Prepared by Vladik.
Solution: 137274527

Tutorial is loading...

Prepared by AleXman111.
Solution: 137274647

Tutorial is loading...

Prepared by AleXman111.
Solution: 137274769

Tutorial is loading...

Prepared by 4llower.
Solution with $$$O(n \cdot log(n))$$$: 137274837

Tutorial is loading...

Prepared by AleXman111.
Solution: 137274954

Tutorial is loading...

1609G - Прогулка по матрице

Давайте попробуй решить задачу без изменений. Заметим, что в матрице построенной таким образом для перехода из (i, j) всегда выгодно переходить в клетку с наименьшим числом. Более наглядно это можно увидеть на матрице первого тестового примера:

Это позволяет решать задачу за $$$O(n + m)$$$ простым обходом, но для полного решения этого не достаточно. Давайте введем два новых массива разницы соседних элементов массивов $$$da_i = a_{i + 1} - a_i$$$ и $$$db_i = b_{i + 1} - b_i$$$.

Обратим внимание, что наше жадное решение поворачивает направо из клетки $$$(i, j)$$$, когда $$$da_i > db_j$$$. Для наглядности ниже приведена иллюстрация поворотов:

Каждый раз такой поворот направо в клетке $$$(i, j)$$$ уменьшает нашу общую сумму на $$$(da_i - db_j) + (da_{i + 1} - db_j) + \dots + (da_{n - 1} - db_j) = (\sum_{t=i}^{n - 1} da_t) - db_j \cdot (n - i)$$$. Что на самом деле эквивалентно сумме $$$da_i - db_j$$$ для всех $$$da_i > db_j$$$.

Такую сумму можно считать узнавая для каждого $$$i$$$ бинарным поиском последнее $$$db_j$$$ для которого выражение $$$da_i > db_j$$$ верно. Что позволяет нам решать задачу за $$$O(n \cdot log(m))$$$ используя префиксные суммы массива $$$db$$$.

Теперь вернемся к запросам изменения. Т.к. размер массива $$$da$$$ достаточно маленький, то мы можем производить изменение значений его элементов простым обходом. Для хранения массива $$$db$$$ необходимо будет использовать дерево отрезков поддежривающее следующие операции:
- Прибавление числа на суффиксе массива (т.к. мы работаем с массивом $$$db$$$, а не $$$b$$$, то все элементы будут изменяться на одно число равное шагу арифметической прогрессии).
- Сумма чисел массива на префиксе массива пока $$$element_i < X$$$. (в качестве $$$X$$$ будет выступать очередной $$$da_i$$$).

Итоговая сложность: $$$O(q \cdot n \cdot log(m))$$$.

Tutorial is loading...

Prepared by budalnik.

  • Проголосовать: нравится
  • +69
  • Проголосовать: не нравится

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

If possible do link codes with solution .

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

I solved F by reducing it to a geometry problem. But I only fixed my TLE 5 minutes after the contest ended :rage:

First, for each index, we want to know the largest range on which it's the minimum element, and the largest range on which it's the maximum element. We can precompute all these ranges in linear time with a monotonic stack idea, for example. Let's say the range where $$$a_i$$$ the minimum element is $$$[l_1(i), r_1(i)]$$$ and the range where it's the maximum element is $$$[l_2(i), r_2(i)]$$$. If there's a tie for the minimum (maximum) element in a range, we always pick the first occurrence to be the minimum (maximum).

Now, for each index $$$i$$$, let's consider the set of intervals $$$[l, r]$$$ on which $$$a_i$$$ is the minimum element. We simply require it to be a subinterval containing index $$$i$$$. So the only constraints are $$$l_1(i) \le l \le i$$$ and $$$i \le r \le r_1(i)$$$. If we visualize this in the plane where one axis is $$$l$$$ and the other is $$$r$$$, we simply are describing a rectangle. Similarly, we have a rectangle for the maximum case.

Let's say that a rectangle is red if it came from the minimum case, and blue if it came from the maximum case. First, notice that no two rectangles of the same color intersect, because a range has a unique minimum and maximum by our tie-breaking rule. Our task is to calculate how many lattice points are the intersection of a red and blue rectangle, and both of them have the same "group number", namely the popcount of their corresponding $$$a_i$$$ values.

Let's just offset rectangles according to their group number so that rectangles of different group numbers definitely don't intersect, and rectangles of the same group are offset by the same amount.

The only thing we need to compute is the area of intersection of red rectangles and blue rectangles. It's sufficient to find the area of the union of rectangles, by inclusion-exclusion. We can find the area of the union of these rectangles in $$$O(n \log n)$$$ time with a sweepline and segment tree. Reference for rectangle union problem: https://cses.fi/problemset/task/1741

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

    You can also find the intersection by using a max query segment tree with max frequency.

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

      This is true, but union was better in my case because I can apply ctrl C ctrl V trick.

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

    Cool idea

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

    Have you tried submitting your TLE code using G++17 compiler rather than G++17(64) or G++20(64)?

    From what I have experienced, G++17(64) and G++20(64) sometimes make your code 2 times slower, compared to G++17.

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

      During the contest I tried running custom invocation on several compilers but in the end I needed to improve the idea a little further.

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

Can anyone please explain E in more detail ? I am not able to understand the solution presented in the editorial.

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

    thanks for the feedback, we will try to make it clearer.

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

    I haven't read the intended solution, but here's an explanation of mine, which I find intuitive.

    Let's say we have an interval and we don't want it to contain a subsequence $$$abc$$$. We can split the interval in half, and then there are three ways we can do this:

    1. Make the first half have no subsequence $$$a$$$ and the second half have no subsequence $$$abc$$$.
    2. Make the first half have no subsequence $$$ab$$$ and the second half have no subsequence $$$bc$$$.
    3. Make the first half have no subsequence $$$abc$$$ and the second half have no subsequence $$$c$$$.

    If we're minimizing the number of operations, we should just take the best of all three options.

    Now, this gives us a way to combine two nodes of a segment tree into one: we just need to store the answer for each substring of $$$abc$$$.

    Implementation: 137243787

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

      Thanks! This was really helpful! Also thanks for the extremely readable implementation.

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

      This solution is way simpler! Thanks a lot!

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

      Thanks, using this hints, I could solve 2400+ problem for first time during upsolve :) I was wondering can we apply similar technique to https://codeforces.me/problemset/problem/750/e also? I saw it is being referred as similar to this one in some comments, so was curious.

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

        Yes, in fact I used a similar idea to solve it. You can see the comments in my solution for more details. 123896956

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

      I can't understand why we choose these 3 cases.

      For example why we don't make first half no subsequence of $$$a$$$ and second half have no subsequence of $$$bc$$$, why $$$ab$$$ and $$$bc$$$?

      Can u explain why this answer works?

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

        The case you're describing is too restrictive, and it's already handled by my case 1.

        I hope it's easy to see why my $$$3$$$ cases all guarantee there will be no $$$abc$$$ subsequence, so I will explain why they cover everything.

        Let's say the interval is $$$[l, r]$$$ and the two halves are $$$[l, m]$$$ and $$$[m+1, r]$$$. Also let's say that we marked some characters as deleted, so that there is no subsequence $$$abc$$$. My goal is to show that this arbitrary way of deleting characters falls into one of my three cases. Since I chose the best way in all $$$3$$$ cases, it's optimal.

        Let's define $$$i$$$ to be the first non-deleted occurrence of $$$a$$$ in the interval, and $$$j\ge i$$$ to be the first non-deleted occurrence of $$$b$$$ that follows. (In case it's undefined, just say it's $$$r+1$$$). Now, we can split by cases of where the indices $$$i$$$ and $$$j$$$ fall relative to the midpoint $$$m$$$.

        1. If $$$m<i\le j$$$: The first occurrence of $$$a$$$ is in the second half, so the first half has no subsequence $$$a$$$. Of course, the second half has no subsequence $$$abc$$$.
        2. If $$$i\le m<j$$$: The first $$$b$$$ after the first $$$a$$$ falls in the second half, so the first half has no subsequence $$$ab$$$. Now, the first $$$a$$$ falls in the first half, so we know the second half has no subsequence $$$bc$$$.
        3. If $$$i\le j<m$$$: The first $$$a$$$ and the first following $$$b$$$ both fall in the first half, so we know the second half has no subsequence $$$c$$$. And of course the first half has no subsequence $$$abc$$$.

        We end up with the exact same cases I described.

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

        For me it helped looking at picture how we can create subsequence in 2 segments:

        left segment | right segment:

        case 1. nothing | abc

        case 2. a | bc

        case 3. ab | c

        case 4. abc | nothing

        OPTION 1: if we delete "a" from left segment, cases 2,3,4 cannot exist so we only delete "abc" from right segment. The reason we delete "abc" and not "bc" is because deleting "abc" <= than deleting "bc" (its because if we can delete "bc" in X moves, we can delete "abc" also in X moves (we delete all "bc" so there is no "abc"), but "abc" can also be deleted by deleting some "a"'s, which may be cheaper)

        OPTION 2: if we delete "ab" from left segment cases 3,4 cannot exist, but case 2 can, so we must delete "bc" instead of "abc" in right segment (this will also delete "abc", with the reason above)

        OPTION 3: if we delete "abc" from left segment case 4 cannot exist but case 3 can, so we must delete "c" instead of "bc" in right segment

        These are 3 options considered by 1-gon, for "ab" and "bc" is similar, just look at:

        case 1. nothing | ab

        case 2. a | b

        case 3. ab | nothing

        and do the same.

        EDIT: I just realized why we don't consider deleting "b" from left segment and "bc" from right segment: as I said above, deleting "ab" <= deleting "b" :)

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

      Thanks for your explaination

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

    Looking at the 750E and this comment helped me to understand a really interesting solution for this problem using string automata

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

      I agree, string automata is the most straightforward way to solve this problem. The automaton is very simple. A simple computation tells us that the transition monoid has 14 different states, corresponding to strings "", "a", "b", "c", "ab", "bc", "cb", "ac", "ba", "cba", "bac", "acb", "bacb", "abc". (Yeah I was also surprised to see "bacb"). So every string is equivalent to one of these 14 strings in the way it acts on the automaton. Now you can just precompute the $$$14 \times 14$$$ table of transitions, and each node of the segment tree has 14 values, the minimum cost to bring the substring to each of the 14 forms (or $$$\infty$$$ if not possible). The final solution is given by the minimum of all but the last number, corresponding to "abc".

      The resulting code is very clean: 138766217

      Thank you prof. Jelena Ignjatovic for teaching me Automata Theory, in particular the algorithm to build the transition table. I had no idea I would use it on CF one day.

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

    Here is another solution which I think is fairly intuitive as well and easier to implement than the editorial idea.

    For there not to be any subsequence $$$abc$$$, we will have to remove $$$a$$$ from some range $$$[1, i]$$$, $$$b$$$ from the range $$$[i, j]$$$ and $$$c$$$ from some range $$$[j, n]$$$. Or in other words the string will have to satisfy $$$(b|c)^*(a|c)^*(a|b)^*$$$. We will call these the three parts of the string.

    For each node of the segment tree lets just store for the minimum number of characters that need to be deleted such that this node's range starts in the $$$l$$$-th part and ends at the $$$r$$$-th part where $$$1 \leq l \leq r \leq 3$$$.

    Clearly for a single node, we only need to delete it if we're considering the exact part where it can't be placed, i.e, $$$l = r = 1$$$ for $$$a$$$, $$$l = r = 2$$$ for b, or $$$l = r = 3$$$ for c. Otherwise we can always place it somewhere in one of the parts.

    Now to construct the answer for $$$[l, r]$$$ from its child ranges we just need to take the min sum of $$$[l, split]$$$ for the left child and $$$[split, r]$$$ for the right child over all $$$l \leq split \leq r$$$.

    Implementation — 137303306. init, combine and main are the important parts. build and update are just standard segtree functions copy pasted from cp-algo.

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

      For there not to be any subsequence, we will have to remove a from some range , b from the range, and c from some range...

      Could you elaborate what is the intuition behind this? Why do we know that removed characters are not mixed in any way?

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

Problem D was more an English comprehension test for me :(

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

    Could not agree more. I had a doubt, asked for clarification and got handed with the savage reply "Read the problem statement" XD.

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

      Yes it took me around 45 minutes to decode the answer for second sample test case:(.

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

        Same. It broke the momentum and in the end I couldn't solve D and I slipped to specialist again ;_;

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

      hahaha. Agreed. I asked for "can you explain the second testcase", and got a red "No".

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

        Maybe too nervous during the contest,i unsterstood D right after the contest and thouhght it a easy problem.

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

    MoSalah and VVD4 has same rating

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

For anyone looking for video editorial, I have made for problems A to D.

Link to the video

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

What's the expected time complexity for C? I've used seive to find the primes less than 10^6 and then checked how many pairs are possible when the sequence starts from the ith term, but it's taking too long. From my understanding time complexity of seive is O(log(log(n))) that of my remaining script is O(nlog(n)). Can anyone point where I am going wrong?

My Submission

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

In D, how do we know that the way topvals are inserted in the solution above doesn't exceed logN, is it similar to the reason why find of the dsu doesn't exceel logN ?

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

In E, am I right that the model solution has the intended complexity of O(n log n * 32 * 32), which is more than what seems reasonable?

It seems that you've done some constant optimization because the number of states which make sense is a bit smaller than 2^5, I have no idea how Java users are supposed to pass this task...

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

    I have no idea why the editorial uses the word $$$mask$$$... I found it easier to define $$$dp_{node,l,r} = $$$ minimum cost to prevent $$$s[l, ..., r]$$$ from appearing as a subsequence of the interval corresponding to $$$node$$$ (and assuming that $$$s[l, ..., r - 1]$$$ has already appeared), where $$$s$$$ is the string "abc". Transitions to merge two nodes are straightforward (just three nested loops, yielding $$$20$$$ operations per merge).

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

I don't quite like the style of the editorial

But I do appreciate the attempt to include solutions with more readable code than usual. I'll give you that

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

in problem B: can someone tell me why this code fails 137283903, and this code passes 137284479 ?

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

    Expected: 1, Output: 0

    In the code that fails, when you replace a character, you correctly check if it was originally in an ABC sequence, but you fail to check if this new replacement causes a new ABC sequence.

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

Can anyone help me find the time complexity of my solution for problem C?

Submission: 137291865

I am just wondering how this got AC

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

    $$$O(N log log N), N = 1e6 + 7$$$ for initial prime sieve, see: CP Algorithms

    $$$O(n)$$$ as you loop through the array, if it is prime, traverse the pointers left and right to exhaust all $$$1$$$s. It is easy to see that each $$$1$$$ will only be read at most 3 times — once for itself, once due to the prime on its left, and once due to the prime on its right.

    AC is intended, your time complexity is good.

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

      each 1 will only be read at most 3 times — once for itself, once due to the prime on its left, and once due to the prime on its right.

      This makes sense now. Thanks!

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

        each 1 will only be read at most 3 times — once for itself, once due to the prime on its left, and once due to the prime on its right.

        Could you please explain this if you have understood

        Edit : Got it

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

I solved problem E other dp. Notice, that abc exist if and only if exist 'b' between first 'a' and last 'c'. It is beneficial for us to do this: replace the first few 'a', the last few 'c' and all the 'b' between the first remaining 'a' and the last remaining 'c'. Note also that we can assume that we are deleting the symbol, and not replacing it. Because We can replace 'a' and 'b' with 'c', and 'c' with 'a'.

Let's first reduce the task to an array task. Let's create 3 arrays a, b, c, where a[i] = 1 if s[i] = 'a', b[i] = 1 if s[i] = 'b', c[i] = 1 if c[i] = 1. Then what does our answer look like? Answer is $$$\min_{i <= j} (a_0 + ... + a_i) + (b_{i + 1} + ... + b_{j - 1}) + (c_j + ... + c_{n - 1})$$$ Here you can come up with dp, which will consider the answer as O(n), but let's come up with a quick solution right away.

Let's $$$dp[v][i][j]$$$ — answer for node v segment tree if we begin in array i and finish in array j on subsegment. Then, in order to solve the problem, it remains only to learn how to combine 2 vertices. If we recalculate through v1 and v2 $$$dp[v][i][j] = min_{k1 <= k2} \, \, ( dp[v1][i][k1] + dp[v2][k2][j] )$$$ Explicitly recalculation works in $$$O(\Sigma ^4)$$$, but this is optimized to $$$O(\Sigma ^3)$$$, where $$$\Sigma$$$ is the size of the alphabet. Then the whole solution will work for $$$O((n + q \log n) \Sigma ^3)$$$

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

It would be nice if the editorial for problem A did not just tell what we need to "notice" to solve it, but also provided some kind of a proof. Because for me the proof is not that obvious, even though I know how to prove it now.

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

I have a time limit in this submission: 137334481

However, when I checked if some elements are infinity, the solution passed: 137334234

I don't really understand why it did, do these if statements really optimize the solution to that extent, and most importantly why?

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

My solution to F only uses Divide and Conquer. I think it's quite simple, actually.

Suppose we are calculating the answer for segment $$$[l,r]$$$ that passes through $$$mid$$$ and $$$mid+1$$$. For each $$$l\in [l,mid]$$$, find the following: (with two-pointers)

  • the maximum $$$r\in [mid+1,r]$$$ such that the maximum in $$$[l,r]$$$ is in $$$[l,mid]$$$, $$$j$$$;
  • the maximum $$$r\in [mid+1,r]$$$ such that the minimum in $$$[l,r]$$$ is in $$$[l,mid]$$$, $$$k$$$.

WLOG $$$j<k$$$. Then,

  • If $$$r\le j$$$, the number of bits in the maximum and minimum of $$$[l,r]$$$ only depends on $$$l$$$. This is easy to deal with.
  • If $$$r\ge k+1$$$, the number of bits in the maximum and minimum of $$$[l,r]$$$ only depends on $$$r$$$. This is easy to deal with, with suffix sums on $$$r$$$.
  • Otherwise, what we are calcuting is like, "how many numbers in $$$b_{[l..r]}$$$ are $$$k$$$"? This can be solved offline with a sweep-line like method. We add $$$(l,k,-1),(r+1,k,-1)$$$ to the set of queries and process it when we scan from $$$mid+1$$$ to $$$r$$$, maintinging a bucket array.

Complexity is $$$O(n\log n)$$$ and independent of $$$a_i$$$.

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

Can anyone help me understand why my submission for B is getting WA on test 3. My approach is exactly same as in editorial. can't seem to find the edge case. help will be truly appreciated.137250167

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

    you are not considering the possibility that s[pos] may already be equal to c and changes nothing

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

      I believe that case is already covered internally in my code.

      if s[pos] is already c and string abc can be formed with the neighbouring characters we insert into the set which causes no change to the set since the set already contains that value.

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

Even after reading D for so long I was not able to understand the testcase 2. Now after reading the editorial one thing is clear — that I don't understand the question itself. Any help in understanding the question or testcase 2 is appreciated. Thank you.

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

    In the testcase 2, when you try to link, but they are already in the same set (For example: 1, 4), you get a new chance to link another node.(we must satisfy first 4 condition, but may not to use all 4 chance to link.) So, when our code read (1, 4), we can link 1 and 5, get the set which has five elements. The answer for each i must be calculated independently., so we can sort it and greedily choosing the larger set.

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

Can anyone tell me why am i wrong in this code ? https://codeforces.me/contest/1609/submission/137238591 Thanks you.

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

I have alternative perhaps slightly complicated solution for F. However most of the complexity comes from the stringent memory limit. We first iterate over what is maximum element. To find what subranges $$$u$$$ is maximum for, we just need to find closest left element that is larger($$$l-1$$$) and closest right element that is larger($$$r+1$$$). Now we need to find total subarrays such $$$bits(\min(a[l\ldots r])) = bits(a[u])$$$, where $$$bits$$$ is number of set bits.

Let us let the left ending of subarray be $$$l \le l' \le u$$$. Let us now find 2 other arrays as precomputation.

rhtmin[i] : This tells us the index of closest element to the right of $$$a[i]$$$ that is smaller if it exists and $$$n$$$ otherwise

rhtcnt[i] : This tells us for how many $$$i \le x \le n-1$$$ is such that $$$bits(a[i]) = bits(\min(a[i\ldots x]))$$$

Let us now find the number of $$$r'$$$ such that $$$l \le l' \le u \le r' \le r$$$ such that the the number of bits is the same as in $$$a[u]$$$. We can keep a rolling minimum while iterating $$$l'$$$ from $$$u$$$ to $$$l$$$. Lets use rhtmin on the minimum element to find till what value of $$$r'$$$ will the minimum be on the left side of the array. Using this we can check if should add these subarrays or not.

Now we need to use the next trick. We want to find when will the minimum become an element with $$$b$$$ bits. If we do that we can use rhtcnt to compute the answer. The minimum from $$$i$$$ will change at rhtmin[i]. Therefore when an element is found with $$$b$$$ bits is the same for $$$i$$$ and rhtmin[i] except when $$$b = bits(i)$$$. So if we iterate from $$$n-1$$$ to $$$0$$$ and copy the positions we find bit $$$b$$$ it will be fast enough. However as the memory limit does not allow us to make array of size $$$64n$$$ we need to do some memory optimisation.

Instead we store when the next element with $$$8k \le b \le 8k + 7$$$ bits appears for each $$$k$$$, and then for an element with $$$8k + i$$$ bits we also store where the next element with $$$8k + j$$$ bits appears. This has optimised memory usage to $$$16n$$$ instead. Now to find the next element with $$$b$$$ bits, we first find an element whose bits $$$b'$$$ satisfies $$$\lfloor b'/8\rfloor = \lfloor b/8\rfloor$$$, and then we find an element with exactly $$$b$$$ bits from the element with $$$b'$$$ bits. This finds the answer in $$$O(1)$$$ still.

Ok now we have found when the number of bits in the minimum becomes $$$b = bits(a[u])$$$. Using rhtcnt we get the answer for number of subarrays $$$l \le l' \le u \le r' \le n$$$ such that $$$bits(\min(a[l'\ldots r]) = b$$$.

To remove the extraneous arrays, we will first have to find the minimum closest to the edge of $$$r$$$. This can be done effortlessly with binary lifting on $$$i \to rhtmin[i]$$$. This used $$$20n$$$ memory which is too much for us. We optimise this by using quaternary lifting which will only use $$$10n$$$ memory at the cost of an extra $$$3/2$$$ factor in runtime.

Ok now we have the closest element to the edge($$$r_m$$$). This will remain constant until the minimum on the left side becomes less than $$$r_m$$$, in which case the minimum of all subarrays is a trivial case and is constant. Let us break $$$r_m$$$ into two cases. If it has $$$b$$$ bits we can easily subtract its rhtcnt to remove extraneous $$$r'$$$. We just add the answer for $$$r_m \le r' \le r$$$ back.

If its not, we need to find where is the next time the minimum has $$$b$$$ bits, which will be outside the array and we can simple subtract its rhtcnt to remove extraneous values. All we need to do is the earlier trick again to find the next element with $$$b$$$ bits from $$$r_m$$$ and subtract its rhtcnt to get the answer.

We can do the exact same iteration for $$$u \le r' \le r$$$.

If we do it for the smaller of the 2, we will do not more than $$$O(n\log{n})$$$ iterations. If you think of the maximum of an array splitting it into two like some sort of divide and conquer it is clear that this is the case.

And using that we can get the solution in $$$O(n\log{n})$$$.

Solution

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

I think the memory limit for problem F is too small so that In my solution can't use prefixsum but just can use persistence segment tree. Such as https://codeforces.me/contest/1609/submission/137397827 and https://codeforces.me/contest/1609/submission/137397769

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

"A little later"

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

В решении задачи E подпоследовательность ab = ba ? почему мы не рассматриваем cba ? почему это будет оптимальным ответом ?

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

why "Tutorial is not available" for problem H?

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

Edit : mistake from my part, sorry

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

I have a question in problem E. The code you added to the tutorial doesn't define the following base cases: if we are at the node that contains one character and let's say it's "a" we define seg[ver].dp[1] = 0 but we don't define the case if we replaced the character with "b" or "c". Therefore, instead of defining seg[ver].dp[2] = seg[ver].dp[4] = 1, we are defining seg[ver].dp[2] = seg[ver].dp[4] = inf. How does the solution works even with this? Note: both cases will get accepted so why it doesn't make a difference?