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

Prefix sum (aka cumulative sum) related problems
Автор semi_rated, 6 лет назад, По-английски

Please give some online judge problems in which prefix sum( also known as cumulative sum) technique is useful.

Thanks in advance.

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

»
6 лет назад, # |
← Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится
  1. SPOJ CSUMQ (straight forward)
  2. Codechef SNAKEEAT (Here I wrote a tutorial how this problem can be solved using prefix sum)
    Edit:
  3. UVa 108
  4. UVa 983
  5. UVa 11951
    Edit 2:
  6. UVa 10533 (I have learnt the prefix sum technique by myself solving this problem)
  7. Hackerrank KJ and street light
→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

A quite simple one: 816B — Karen and coffe

→ Ответить
»
4 года назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится
This might help you while implementing
→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

296C Greg and Array

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Some DP + prefix sum : 479E - Riding in a Lift

PS : Sorry , but wasn't knowing that it's very old blog

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

Problems sorted by difficulty.

Kuriyama Mirai's Stones

Vika and Squares

Balanced Tunnel

Karen and Coffee

Greg and Array

Valid Sets

Star Sky

Train Hard, Win Easy

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

I got one: https://judge.yosupo.jp/problem/static_range_sum

This is def the easiest prefix sum problem ever

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

try to solve from csesfi

there are some problems to learn it finely.

→ Ответить