ASCII4's blog

By ASCII4, 8 months 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.

Read more »

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