I recently came across with this question

Here distinct subarray means :- 7 8 9 0 7 8 9 0

Subarray index 0 to 3 and 4 to 8 are same

Constraints are Number of elements NumElements<=1000

a[i]<=200

My solution :- Build the trie of all subarrays and count if distinct leaf has at most k odd numbers in its path

however the memory requirements of Trie is O(ALPHABET_SIZE * key_length * N) where N is number of keys in Trie.

which in this case is O(200*NumElements*NumElements*Numelements)

So i am stuck with that ?

Iterate over all subarrays and when you find one that has at most

kodd elements, run a second iteration over all subarrays different from the one you're processing and compare them. If you find another one with all equal elements, you know you shouldn't count it. This solution runs inO(N^{4}), which should be good enough if you run it on a 64-core computer running at 8 Ghz.How is that good enough? Here N = 1000. So, your N^4 solution will take only 10^12 operations.

Well, you have two options then.

1) Run the above solution in a good computer.

2) Make an

O(N^{2}) with rolling hashes modulo two different primes to minimize the risk of collision.The first option is very good.

You can check all the subarrays of the given array. Now, for counting how many odd numbers are in that subarray, you can make another array in which the (i) th index will hold how many odd numbers are in the array from 1 to i. You can preprocess this array at the beginning. After that, if you are are looking for how many odd numbers are in the subarray A[l...r], you can call the preprocessed array(pre), odd_count = pre[r] — pre[l — 1] The complexity of this solution is O(n^2). There is also a O(n * log(n)) solution. I think you can do it.

You're forgetting that he needs to count only

differentsubarrays.Sorry. I didn't notice that. But it can be solved with a simple hash. And it also adds an extra logN complexity. So, the total complexity of this solution should be O(N^2 * log N).

No, it doesn't. Hash can be implemented in linear time with a two-dimensional array for

N≤ 10^{3}. Also, you can use Mintwhirl's hash function, that runs inO(N_{log}Z), whereZis Kornky's value for the array.Hash of a subarray can be calculated in O(1) complexity if I am computing every subarray.

Query is

O(1), but precalculation isO(N^{2}). The other option is to query inO(_{log}Nbut preprocess inO(N).That precalculation won't affect my solution.

I still don't understand why you said it adds an extra (

_{log}N) factor to the complexity. If precalculation isO(N^{2}) and each query isO(1), then hashing does not affect complexity of the solution at all.You have to check the hash value with previous ones. That would cost an extra logN.

Ahhhhhh, yes, you're right about that. That was very stupid of me.

Alternatively, you can use Nashtarovya's tree to solve the problem.

Sorry I did not understand your difficulties. Do you think that the trie size can be too large? Then you can use SuffixAutomation instead with maximum number of nodes as

`2*NumElements`

and the problem complexity`O(NumElements^2)`

in the worst case.Indeed, I think he multiplied one more time when calculating the complexity.

I think you calculate the memory complexity wrong. I think it should be O(200 * N^2). Let me try to explain it. Let say we already have all sub array with at most k odd elements. We denote it as array of N integer arr where arr[l] = r that is we have a valid sub array from l to r.

Now we are going to insert each of them to Trie. We are going to loop for l = 1 to N, insert all element arr[i] for i = l to r. Inserting each sub array takes O(N) node (depth N). We have N sub array, so we are going to insert O(N^2) node with each node having 200 edge. So in total it is O(200 * N^2).

Note that we are going to store at most N * (N-1) / 2 node * 200 should be around 10^8.

What i get from your analysis is that for each arr[l] can have only one valid subarray .here arr[l] may have multiple subarrays

eg 1 2 3 4 5 and k = 3

for l=0

we can have following subarrays as problem says atmost k odd numbers

1

1 2

1 2 3

1 2 3 4

1 2 3 4 5

pls correct me if i am wrong

That's not it. Let me modify your example a bit to be more clear. So we have N integer 1 2 3 4 5 and k = 2. We have arr[1..5] with each having value:

arr[1] = 4 (i.e. 1, 2, 3, 4)

arr[2] = 5 (i.e. 2, 3, 4, 5)

arr[3] = 5 (i.e. 3, 4, 5)

arr[4] = 5 (i.e. 4, 5)

arr[5] = 5 (i.e. 5)

We still have O(N^2) elements we need to insert to Trie, but we only need O(N) integer to represent it. It is just a matter of representation.

Seems to me that it can be done in O(N^2) by counting the amount of odd and even elements, counting hash of the correct subarrays and using unordered_map to store distinct subarrays.