daiict's blog

Help needed in the problem "Riding in a lift".
By daiict, history, 8 years ago, In English

Hello codeforces, I am not able to understand the solution of this problem. Problem link is [http://codeforces.net/contest/479/problem/E]. Solution is not very clear. In solution it is mentioned that dp[i][j] can be calculated in O(1) using famous technique called "partial sums". I googled it but I could not find anything. Please help me in solution and also mention about that technique. Thanks in advance.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Yes, dp[i][j] can be calculated in O(1) after some pre computation which involves calculating the partial sums.
After we calculate the partial sums, we can just subtract the values at the relevant indices and get the value of dp[i][j]. Check this solution

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +16 Vote: I do not like it

About "partial sums"

You have an array a[n] and you should answer several queries: you are given two indices l, r and you should print the sum of elements on the segment [l, r].

You can calculate an array b[n] such as b[i] = a[0] + [1] + ... + a[i — 1] + a[i]. It can be done in O(n) time. Then the answer for the query is b[r] — b[l — 1]. This works in O(1).

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This reminds me of a problem I solved on a Thai site. I think it would give you some more familiarity with the prefix sum technique.

You are given two integers n and k (n, k <= 10^4). Find the number of ways to rearrange a permutation of length n such that the number of pairs of indices (i,j) where i < j and ai > aj is equal to k.

Small Hint: time complexity is 10^4*10^4.

If you want to submit, feel free to tell me and I will assist you since the whole webpage is in Thai and I don't know how well Google Translate does the job for you :)

→ Reply