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.