semi_rated's blog

Prefix sum (aka cumulative sum) related problems
By semi_rated, 6 years ago, In English

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

Thanks in advance.

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

Comments Comments (13)
| Write comment?
»
6 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it
  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
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A quite simple one: 816B — Karen and coffe

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it
This might help you while implementing
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

296C Greg and Array

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

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

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

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

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

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

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

This is def the easiest prefix sum problem ever

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

try to solve from csesfi

there are some problems to learn it finely.

→ Reply