CopeCope's blog

By CopeCope, history, 6 years ago, In English

Given N arrays of arbitrary length each, and M queries in form : a b. For each query output the number of arrays such that there exist Array[i] = a Array[j] = b and i < j (Basically, number of arrays such that a comes before b). Also, there can be any number of a's or b's in any array

N, M, a, b <  = 105 Consider that length of all arrays is  <  = 105

Example: Arrays
1 2 3 4
2 4
2 3 1 4

and queries are (1, 3) , (2, 4) , (1, 4) , (4, 1) answers are 1 , 3 , 2 , 0

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints?

»
6 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

Let maxN = 105.

1) Number of array which exist that pair for a,b that is number of array such there first occurrence of element a more to the left than last occurrence of element b.

2) Before requests you can precalculate number of arrays, which length is smaller than and they satisfy the condition for each pair (a,b) in map < pair < int, int > , int > . The size of this map will not be greater than .

3) Also you want to precalc for all posible value and array first and last occurrence of it.

For each request you will get appropriate value in map and consider all arrays with size not smaller than (count of this arrays not bigger than ). Using 1 and 3 its easy to consider them.

Сomplexity .

Using Hash Tables complexity will be .

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

    I missed the part with arrays of smaller length, really stupid of me... Not hard problem at all. Thank you

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

      For each array with size smaller than we will use naive algo: brute positions i < j and if pair (Array[i], Array[j]) we don't see in this array before will update info in map like m[{Array[i], Array[j]}]++.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh, I meant when I was solving problem, thank you anyway