Problem Link
Prerequisites:
binary search,permutation with repetition
There is no need to use square root decomposition like official editorial.I solved this problem(100) with binary search.Method in which even a beginner can understand
1.maintain a dictionary s with s[i] an array with indexes of elements in A which are equal to i.
Example A=[1,2,3,3,1] then s={1:[1,5],2:[2],3:[3,4]}
remove all the keys from s if length of s[key] is 1
2.maintain an array fact with c[i] =factorial(i)
eg fact=[1,2,6,24,120…]
Start Iterating in the queries now
for l,r in queries:
Let answer first be fact[r-l+1]
iterate over keys in s:
let ind_1 be number of elements in s[key] less then l.Find it using
binary search
let ind_2 be number of elements in s[key] less then or equal to
r.Find using binary search again.
set answer to answer/fact[ind_2-ind_1]
print(answer)
done!!Wait not so fast you won’t get 100 with this
Now time for some Optimizations in the code.
When you iterate over keys in s add 2 conditions in the beginning.
if s[key][0]>r:
continue
if s[key][-1]<l:
continue
As factorial can be huge number don’t forget modulo arithmetic
Done 100 points!!
solution link:
CodeChef: Practical coding for everyone(only solution of python which got 100)
Time Complexity:
let complexity=0
for i in s:
complexity=complexity+log2(|s[i]|)
or
n
complexity is ÎŁlog(|s[s.keys()[i]]|)
i=1
so after summation complexity will be around log2(n) per query
Hope You liked the editorial!!!My first one.
