procoderpro's blog

By procoderpro, history, 3 months 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  

»
3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        The first option is very good.

»
3 months 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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

    • »
      »
      »
      3 months 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).

      • »
        »
        »
        »
        3 months 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.

        • »
          »
          »
          »
          »
          3 months 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.

          • »
            »
            »
            »
            »
            »
            3 months 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).

            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              That precalculation won't affect my solution.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 months 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.

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
3 months 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.

»
3 months 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.

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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.

»
3 months 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.