Can anyone please explain how to solve COOLCHEF with sqrt decomposition.
I have written my initial unoptimised solution on the top of my ( badly written ) submission. Complexity O(N\sqrt Q\log N) ( The weird complexity is because the block size is \frac{N}{\sqrt Q} ). Although I think the intended complexity is O ( (N+Q) \sqrt N ).
Main optimisations I did to the initial solution:
- Instead of a trie, I used something similar to this
- Only calculated the denominator in the query and multiplied it by (r-l+1)! afterwards.
Precompute all subarrays having range as follows:
[ i*\sqrt{n} , j*\sqrt{n}-1 ]
For all i \lt j
Which will be O({\sqrt{n}}^3) = O(n*\sqrt{n})
(Basically use MO’s algorithm (similar to it) for doing this)
PS : this can be helpful in many online query questions where people generally can’t use MOs algorithm.
Then use those precomputed segments in query part.
In each query you will have to add at most 2*\sqrt{n} new numbers to a precomputed segment.
Adding a number can be done in O(\log_2{n})
(Adding number requires finding frequency of a particular element in range l,r (hint : binary search on some other array))
So over all complexity for each query is
O(\sqrt{n}*\log_2{n}) in worst case.
My solution takes
O(n*\sqrt{n}+q*\sqrt{n}*\log_2{n}) in worst case and it passes for 100 points as well 
I think we can still try to remove \log_2{n)} part if needed.
www.codechef.com/viewsolution/24731818
5 Likes
While writing LaTeX you can put a \ in front of sqrt and log to make them print like \sqrt{} and \log unless, of course you prefer it this way.
1 Like
Okay thanks…
…
Thanks.
It helped a lot.
1 Like
I used the same approach described by @l_returns except for the logn factor. We want the know the frequency of new number only between two particular blocks so we can maintain a precomputed array of size sqrt(n)*n which will store the frequency of all numbers starting from every block. Now for getting frequency of any arr[i] between any two blocks(a,b) we just need to find the difference cnt[a][arr[i]] - cnt[b+1][arr[i]].
Overall complexity - O(n * sqrt(n) + q * sqrt(n))
3 Likes
What exactly are you precomputing in the blocks.And can you explain how are you combining the answers for two blocks because you need to know the actual frequency distribution of the range for answer.
I will explain it with the help of example.
Consider the array -[3, 4, 1, 2, 4, 3, 1, 4,8]
block size = 3, starting indexes: 0,3,6
count - 2d array to stores frequency of all elements starting from particular block.
cnt[0] :- [0,2,1,2,3,0,0,0,1,0,0…]
cnt[1] :- [0,1,1,1,2,0,0,0,1,0,0…]
cnt[2] :- [0,1,0,0,1,0,0,0,1,0,0…]
pre- 2d array to store answer starting from one block to end of another block
pre[0][0] = 1!*1!*1! = 1,pre[0][1] = 1!*1!*2!*2! = 4, pre[0][2] = 2!*1!*2!*3!*1! = 24
pre[1][1] = 1!*1!*1! = 1, pre[1][2] = 1!*1!*1!*2!*1! = 2
pre[2][2] = 1!*1!*1!= 1
temp[n] - initially set to 0, used later to answer each query.
Let’s say the query is 1-6.
next block to index 1 = 2
prev block to index 6 = 2
Already calculated answer = pre[1][1] = 1.
New elements to process 4,1,1.
4 :- temp[4] = 0, so get count from temp[4] =cnt[1][4] - cnt[2][4] = 1.
Increment count of 4 in temp and multiply it with the old answer, new_answer = 1* 2 = 2.
1:- temp[1] = 0, so get count from temp[1] =cnt[1][1] - cnt[2][1] = 0.
Increment count of 1 in temp and multiply it with the old answer, new_answer = 2 * 1 = 2.
1 :- temp[1] = 1, so no need to use cnt array.
Increment count of 1 in temp and multiply it with the old answer, new_answer = 2 * 2 = 4.
Final answer = (6+1-1)!/4 = 180
Make temp[1] = temp[4] = 0 to process next query.
3 Likes
You know you can edit posts by clicking the ‘pencil’ icon right?
2 Likes
I am precomputing multiplication of factorial of frequencies of all the elements in that range
So there no need of merging anything.
We need adding single element which can be done by removing it and adding it again from answer
I did not understand the solution till now . if the range l , r completely engulfs a block and a few more elements we have to compute for those elements and there is a map for every block . Correct me if I am wrong .
Are you asking me ???
You can even solve it using binary search.
Yes , I did not understand the solution. Help me out.
For my solution, NO.
We have different PBDS of index for each distinct element.
We require to add few elements which are beyond whole pre computed segments.
Suppose we have pre computed answer for range
(4,8) and query is (2,9)
Then we add numbers in order 3,2 and 9
First we calculate freq of a[3] in (4,8) and add it.
Then we calculate freq of a[2] in (3,8) and add it.
Then we calculate freq of a[9] in (2,8) and add it.
We can remove \log_2(n) ( i.e. for finding frequency) by pre computing for each sqrt(n) size block as suggested by @blake_786
1 Like