### procoderpro's blog

By procoderpro, history, 3 months ago, ,

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 ?

•
• -8
•

 » 3 months ago, # |   -23 Iterate over all subarrays and when you find one that has at most k odd 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 in O(N4), which should be good enough if you run it on a 64-core computer running at 8 Ghz.
•  » » 3 months ago, # ^ |   0 How is that good enough? Here N = 1000. So, your N^4 solution will take only 10^12 operations.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   -17 Well, you have two options then.1) Run the above solution in a good computer.2) Make an O(N2) with rolling hashes modulo two different primes to minimize the risk of collision.
•  » » » » 3 months ago, # ^ |   +3 The first option is very good.
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   -9 You're forgetting that he needs to count only different subarrays.
•  » » » 3 months ago, # ^ |   0 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).
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 No, it doesn't. Hash can be implemented in linear time with a two-dimensional array for N ≤ 103. Also, you can use Mintwhirl's hash function, that runs in O(NlogZ), where Z is Kornky's value for the array.
•  » » » » » 3 months ago, # ^ |   0 Hash of a subarray can be calculated in O(1) complexity if I am computing every subarray.
•  » » » » » » 3 months ago, # ^ |   0 Query is O(1), but precalculation is O(N2). The other option is to query in O(logN but preprocess in O(N).
•  » » » » » » » 3 months ago, # ^ |   0 That precalculation won't affect my solution.
•  » » » » » » » » 3 months ago, # ^ |   0 I still don't understand why you said it adds an extra (logN) factor to the complexity. If precalculation is O(N2) and each query is O(1), then hashing does not affect complexity of the solution at all.
•  » » » » » » » » » 3 months ago, # ^ |   0 You have to check the hash value with previous ones. That would cost an extra logN.
•  » » » » » » » » » 3 months ago, # ^ |   0 Ahhhhhh, yes, you're right about that. That was very stupid of me.
 » 3 months ago, # |   -8 Alternatively, you can use Nashtarovya's tree to solve the problem.
 » 3 months ago, # | ← Rev. 2 →   0 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.
•  » » 3 months ago, # ^ |   -8 Indeed, I think he multiplied one more time when calculating the complexity.
 » 3 months ago, # | ← Rev. 2 →   0 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.
•  » » 3 months ago, # ^ |   0 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 = 3for l=0 we can have following subarrays as problem says atmost k odd numbers11 21 2 31 2 3 41 2 3 4 5 pls correct me if i am wrong
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 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.
 » 3 months ago, # |   +5 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.