Блог пользователя daiict

Help needed in the problem "Riding in a lift".
Автор daiict, история, 8 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

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).

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 :)

→ Ответить