semi_rated's blog

Prefix sum (aka cumulative sum) related problems
By semi_rated, 8 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 (11)
| Write comment?
»
8 years ago, hide # |
← 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
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

A quite simple one: 816B — Karen and coffe

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

296C Greg and Array

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

Also see this to practice range change in array per queries best solve through prefix sum

https://www.hackerrank.com/contests/algoholic-contest-1/challenges/street-lights/problem

→ Reply
»
6 years ago, hide # |
← 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
»
6 years ago, hide # |
 
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