semi_rated's blog

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

»
3 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
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks so much mr. Shinadul

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      He is Shahidul, not Shinadul lmao
      How ignorant you are, if you can't even copy the name correctly

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        hush relaxxx it is just a name

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        do not take it to an argument, it's just a mistake, not smth that crushes the world. Take it easy!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A quite simple one: 816B — Karen and coffe

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

  • »
    »
    8 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
»
8 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for the difficulty order

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is another easy one.
    CF 363B — Fence

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

    How can I solve "Vika and Squares" using prefix sum? I solved this problem using a constructive algorithm — 90242000

    But want to solve it using prefix sum in order to learn it. Thank you.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      me too wants to know how "vika and square" can be done with prefix sum?