Los_Angelos_Laycurse's blog

gym 100962 problem D Deep Purple
By Los_Angelos_Laycurse, history, 9 years ago, In English

sa +president_tree + brute_force Accepted this problem, seems it is O(n*poly(log(n)),but it needs some proof...,there is litte possibilaty it is O(n^2*poly(log(n))).

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

Comments Comments (3)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

president_tree ?? I`m missed smth definitely interesting.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    My approach is very brute_force,and it is an online algorithm:

    First build suffix array and lcp[], for each query [li,ri],lets find the nearest right rank of position (lm=li), in the position,interval [li+1,ri],we denote this positon,pos,then find lcp=lcp[li][pos], then lm=max(pos, ri-lcp+1), in order to speed up to find the first yes postion, we must deal with parttern str=AAAAAAAA+prefix(A) (this is not legal answer,but currenc lcp value is max.),A is a string,if this pattern is occur we directly get pos=max(pos,len(str)-len(A))..

    with this speed up we can get the first yes positon (pos+lcp>ri) we only jump log(n) times, but this is not the final answer, this is a lcp_max() answer but not the left most answer, so we must continue to go left, denote lm=max(lm,ri-lcp+1),rm=min(rm,sa[pos]-1), similarly there may occur str=AAAAAAA+prefix(A) (this is a legal answer), we can binary_search to find the left most legal answer (jump lenth(A) positon),and denote rm with this left most legal postion.

    this is an online algorithm and I have test for each query the maximum iteration times is not exceed 40, so maybe this is an O(q*Log(n)^log(n)) algorithm...

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      and seems editorial is an offline parralell binary search approach, this is interesting.

      → Reply