semi_rated's blog

By semi_rated, 2 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

»
2 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
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A quite simple one: 816B — Karen and coffe

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it
This might help you while implementing
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it
»
2 months ago, # |
  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

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Constraints too large to use Prefix sum

    Constraint for Ai
»
2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it