Nachia's blog

By Nachia, history, 5 months ago, In English

This is a topic on complexity analysis (for Round 975 Div. 1 E) with no special algorithm.

Problem

An integer sequence (a1,a2,,an) is hidden. We know:

  • It is non-increasing. ( akak+1 )
  • 0akn/k

Suppose we can get one value of ak in O(C) time. Find all values of a1,a2,,an .

Algorithm

Put a0=n+1 and an+1=0 and call SEARCH(1,n) . In a call of SEARCH(l,r) , do nothing if l>r . Also no more search is required if al1=ar+1 . Otherwise evaluate a(l+r)/2 and recursively call SEARCH(l,(l+r)/21) and SEARCH((l+r)/2+1,r) .

A = [0] * (n+2)
A[0] = n+1
A[n+1] = 0

def f(k) :
    # find a_k

def search(l, r) :
    if l > r
        return
    if A[l-1] == A[r+1] :
        for x in range(l, r+1) :
            A[x] = A[l-1]
        return
    m = (l + r) // 2
    A[m] = f(m)
    search(l, m-1)
    search(m+1, r)

Complexity Analysis

I saw this algorithm in physics0523's blog post (https://physics0523.hatenablog.com/entry/2023/10/11/155814) and I suggested the complexity be probably O(n+nC) . Finally noshi91 made a proof(Twitter link) which says that is.

Only O(2d/2) calls in depth d .

Since the algorithm is just a binary search, searching space [0,n+1) is splitted in 2d segments with almost same sizes before it reaches depth d . Especially the first one is [0,(n+1)/2d) .

Suppose d is odd and set d=d1 . In depth d , the group of segments without the first 2d/2 segments bounds [(n+1)/2d/2,n+1) . For n/2d/2xn we have ax2d/2 so we need to search only 3×2d/2+1 segments in depth d .

For the case with even d , we have no more calls than twice as depth-(d1) calls.


Since log2nd=02d/2 is bounded as O(n) , the processing time overall is O(n+nC) .

Bonus

We can process the Decremental Predecessor Query Problem in amortized O(1) time per query. For Round 975 Div. 1 E , we can use that instead of a general DSU to solve the entire task in O(nn) time. Submission 283309295

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

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

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

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

Sample problem for this technique: 1039D - You Are Given a Tree

»
5 months ago, # |
  Vote: I like it +20 Vote: I do not like it

O(n) is a little bit confusing, probably you can change it into "assume that we can get a value of a in f(n) time, then we can get all a in O(n+f(n)n)"?

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

    Thanks! I prefer C to f(n) , I think it's clear enough.