procoderpro's blog

By procoderpro, history, 4 weeks ago, In English,

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 ?

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

»
4 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How is that good enough? Here N = 1000. So, your N^4 solution will take only 10^12 operations.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it -17 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it -9 Vote: I do not like it

    You're forgetting that he needs to count only different subarrays.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hash of a subarray can be calculated in O(1) complexity if I am computing every subarray.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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, # ^ |
                Vote: I like it 0 Vote: I do not like it

              That precalculation won't affect my solution.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You have to check the hash value with previous ones. That would cost an extra logN.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it +5 Vote: I do not like it

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.