ASCII4's blog

Sparse Table and some problems
By ASCII4, 5 years ago, In English

Hello:)

Now I'll say what is Sparse Table and I'll show you some problems that I found.

Sparse Table is a data structure, that allows answering range queries. It can answer range minimum queries (or equivalent range maximum queries) in O(1) time, and another queries in O(log n).

You can read how to use it here: GeeksForGeeks, CP-Algorithms

Problems:

Codeforces:

872B - Максимум максимума из минимумов //difficulty 1200 but with sparse table harder

5C - Наибольшая правильная скобочная подстрока //difficulty 1900

475D - CGCDSSQ //difficulty 2000

863E - Выключение телевизора //difficulty 2000

514D - R2-D2 и армия дроидов //difficulty 2100

675E - Электрички и статистика //difficulty 2500

15D - Карта //difficulty 2500

873E - Награждение победителей //difficulty 2500

713D - Зверята и пазл //difficulty 2700

SPOJ:

SPOJ — RMQSQ //easy

SPOJ — THRBL

SPOJ — Miraculous

SPOJ — Postering

SPOJ — Negative Score

SPOJ — A Famous City

SPOJ — Diferencija

Everything you can solve by sparse table.

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

Comments Comments (11)
| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey, Can you tell how can sparse table be used to solve "5C — Longest Regular Bracket Sequence"?Thanks.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Link

    This is a video Explained by CodeNcode

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

      Thx for early reply and helpful video (sol with dp) and blog talking about sparse table ''/

      really is a thing 3zim.

      → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

ASCII4 Can you say how to approach this problem, that you have mentioned: 5C — Longest Regular Bracket Sequence using sparse table ? Thank you.

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

    Treat '(' as +1 and ')' as -1 now build a prefix array.

    Now let's say you are at position i so you will try to find some index j having the value same as pre[i] to make substring from i + 1 to j as a regular bracket sequence. Now there is one more condition any value of prefix array between the index i + 1 to j should be greater than or equal to pre[i] so to check that in o(1) we use a sparse table. Let say you have the bracket sequence

    (())())( its prefix array will be

    ( ( ) ) ( ) ) (

    0 1 2 1 0 1 0 -1 0

    0 1 2 3 4 5 6 7 8

    So if I am on position 0 means that I am considering that my substring is starting with position 1 (1 based indexing) now I will find the index of all zeros present in front of 0 which has the value zero so these indexes are 4, 6 and 8 now if I will check all of those starting from 8 that which one is valid and the longest off course here valid means that none of the value between those indices should be smaller than pre[0] means 0 so here 8 is not valid because on position 7 there is -1 present and we can check it easily with space table that whats the minimum value between those indices which is less than 0 but 6 is the valid one and off course, the longest then for every index i have to iterate for about o(n) times which will lead to o(n^2) but if you observe carefully you see it completely monotonic because if 6 is valid then 4 is definitely valid so we can get the valid string in log(n) for each index by binary searching that which one is the valid one so overall complexity will be o(nlog(n))

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

      I tried this approach o(nlogn) but i am getting tle.. can you please guide me how should i optimize? thanks!! submission

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

        Hi, It would help if you wrote: vll &tobeSearch = f[prefix[i]]; not vll tobeSearch = f[prefix[i]];

        It passes all the test cases you can see in this submission 145175368. And the complexity of your code is n * log(n) * log(n), so it's very slow.

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

One more recent question you can try is 1547F - Стабилизируй массив (НОД-версия)

→ Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

900E — easiest sparse table problem

→ Reply