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

Автор Nutella3001, история, 3 года назад, По-русски

Statement: We have an array A. Lets take every index i and find L[i] and R[i] — closest left and right index j such that A[j] >= A[i] respectively. Then I state that if for every i in 0..n-1 we sum min(i — L[i], R[i] — i) it will be O(N log N). It`s useful if we fix A[i] as the maximum number of segment and if the length of segments is fixed, we can naively iterate over all such segments.

Proof: Iterating over such i we also have the second end of this segment. Lets for every i calculate the maximum number of times that it can be the second end of such segment. Let index j be the first end of such segment. I will prove for j > i, because for j < i its symmetrical. Lets take maximum j > i such that j can be first end of this segment. Then A[j] > A[j — 1] and A[j] > A[j — 2] ... A[j] > A[i]. So now lets take second maximum j such than j can be first end of this segment. Lets call the maximum j j1, second maximum j2. Notice that j2 — i <= j1 — j2. Because otherwise we wouldn`t take j2 with i, consequently 2 * j2 <= j1 + i. Consequently the number of such j s is maximum log n.

Usage: The most beautiful usage of this I have recently seen in task https://mirror.codeforces.com/problemset/problem/1175/F. I was thinking about hashes, etc. , but there is a solution just fixing the maximum of permutation, let it be A[i], find L[i], R[i] and iterate all segments with length A[i] that include i, but neither L[i] nor R[i]. Notice that it`s even less that described above so we can explicitly get our candidates to be the permutations and their number is <= N log N.

You can also check this task https://mirror.codeforces.com/contest/1156/problem/E , the same idea is used there in analysis.

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

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

Your post is marked as russian so it's not visible on english version

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

Your proof is really hard to understand.

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

Try this problem: https://www.codechef.com/problems/A1016054, I think you'll like it :)

Edit: whoops linked wrong problem

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

Also, I have an easier proof:

Consider the maximum element in the entire array, let it have index $$$i$$$. The answer for index $$$i$$$ is $$$min(i-1,n-i)$$$, (assuming we pad the array with infinity at both ends).

Now recursively solve the problems for all numbers to the left of $$$i$$$, and to the right of $$$i$$$ separately. These subproblems are independent since $$$a[i]$$$ is the maximum in the entire array. So our recurrence for the array looks something like:

$$$T(l,r) = T(l,i-1) + T(i+1,r) + min(i-1, N-i)$$$, where $$$N = r - l + 1$$$.

It is well known that this recurrence is $$$T(1,N) = O(N * log(N))$$$, like you said!

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

    Hm... Okey, for me it wasn't a well-known fact about this recurrence... Could you please prove it?

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

      Think about the "small to large" merging trick that you gets you the $$$O(N * log(N))$$$ runtime on DSU and tree problems.

      We have a tree here, but it's a recursion tree! Think about the recursion in reverse, and merging the 2 child subproblems in the recursion together. If we do it "small to large" style, we do $$$O(min(i-1, N-i))$$$ work, which is what we have in the recurrence. It's the exact same thing, so it's $$$O(N * log(N))$$$ also!

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

    I understood how to prove it. It's literally easier than my proof. I will write it here in case someone needs.

    We actually have that our recurrence depends only on length of array. So actually if we have array of length N it divides into two arrays of sizes l and r, without losing of generality lets suppose that l <= r. Then actually our reccurence is F(n) = F(l) + F(r) + l where l + r = n and l <= r

    Then lets use induction. Imagine F(l) <= l log l and F(r) <= r log r. Lets prove that F(n) <= n log n. We actually have that F(n) <= l log l + r log r + l = l(log(2*l)) + r log r <= l log n + r log r <= l log n + r log n <= (l+r)log n = n log n.

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

A harder problem that requires the same technique: Tsetso Subarrays.

Include it in the blog if you liked it.