### procoderpro's blog

By procoderpro, history, 4 weeks 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
•

 » 4 weeks 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.
•  » » 4 weeks ago, # ^ |   0 How is that good enough? Here N = 1000. So, your N^4 solution will take only 10^12 operations.
•  » » » 4 weeks 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.
•  » » » » 4 weeks ago, # ^ |   +3 The first option is very good.
 » 4 weeks 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.
•  » » 4 weeks ago, # ^ |   -9 You're forgetting that he needs to count only different subarrays.
•  » » » 4 weeks 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).
•  » » » » 4 weeks 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.
•  » » » » » 4 weeks ago, # ^ |   0 Hash of a subarray can be calculated in O(1) complexity if I am computing every subarray.
•  » » » » » » 4 weeks 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).
•  » » » » » » » 4 weeks ago, # ^ |   0 That precalculation won't affect my solution.
•  » » » » » » » » 4 weeks 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.
•  » » » » » » » » » 4 weeks ago, # ^ |   0 You have to check the hash value with previous ones. That would cost an extra logN.
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Ahhhhhh, yes, you're right about that. That was very stupid of me.
 » 4 weeks ago, # |   -8 Alternatively, you can use Nashtarovya's tree to solve the problem.
 » 4 weeks 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.
•  » » 4 weeks ago, # ^ |   -8 Indeed, I think he multiplied one more time when calculating the complexity.
 » 4 weeks 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.
•  » » 4 weeks 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
•  » » » 4 weeks 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.
 » 4 weeks 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.