MrPrince22's blog

By MrPrince22, history, 15 months ago, In English

Hello everyone This problem was one of the problems in the ECPC qualifications, and I couldn't think of an efficient way to solve it.

We are given an array a of n integer, and an integer k. Next, we will have q queries, each query has L R. We need to answer the following question for each query: How many subarrays in the range L to R (inclusive) where sum of each subarray is equal to K?

To be honset I couldn't find a good solution to this problem. So I would appreciate your help.

Input:
n = 10 k = 5
a = {2 3 0 0 0 2 3 1 1 0}
7
1 2
1 3
1 7
1 10
2 7
2 6
3 8

Output:
1
2
9
11
5
1
4

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

| Write comment?
»
15 months ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

You didn't mention some important facts about the problem. First of all, it has multiple test cases. Another crucial given is that "sum of n and sum of q over all t don't exceed 3e4" (Actually, this is a key to the problem and makes it easy) Thus it can be solved in O(t*n*q), but hints and code provided will first discuss a pure brute force approach O(t*q*n^2) to provide a clearer explanation then optimize with frequency map to store the frequency of prefix sums (Binary search tree not a hash as there might be anti-hash tests) (would add a log n factor but almost a constant)

Goal is to find the count of sub-arrays bound by L and R whose sum = k

Hint1
Hint2
Hint3
Code