Amazing. Was there anyone who was able to solve it using SQRT decomposition? I wasn’t able to push it, TLE as expected, but still curious, since big O is around the same, but probably much larger constant
You should give both submission links when you say that. If you want a quick response from the
community.
I really liked then way you are writing your code. It’s really easy to understand. Variable names are quite intuitive.
Coming back to your query,
The bincoff as well as sum will overflow range of integer. Question asks to print answer modulo some value.
Use modulo to prevent overflow.
@tmwilliamlin in the query structure you used “make_pair(l/B, r)<make_pair(o.l/B, o.r)” but using “make_pair(l, r)<make_pair(o.l, o.r)” gives TLE. Please explain this as I see that the use of this operator is to just sort the queries according to {l,r}.
No, you must sort by l/B as in Mo’s algorithm.
1 Like
The key is it doesn’t sort according to {l,r} but to {l/B,r}, so all queries with the same value of l/B are sorted by r. That way the queries are partitioned on block of size B and in each block are sorted by r.
1 Like
Ok, thanks got it…
@I_returns updated it
@idgaf_99 can you or anyone else please tell why we have to check till 5800 in every query as every one is saying frequency of frequency of elements will be at most sqrt(N) and N is max 1e5 so why we use such high value ?
The number of frequencies of frequency of distinct elements cannot exceed sqrt(N).
In worst case if we have an array 1,2,2,3,3,3,…x upto N=1e5, then value of x will be sqrt(N).
So number of frequencies of frequency of distinct elements will be bounded by sqrt(N).
But my solution maintains count of frequency of distinct elements. i.e
frq2[i] = count of elements which have frequency ‘i’. This obviously in worst case can be 1e5
when an entire array is filled with same value. This value in testcase is limited upto 5800.
my code only passed subtask 1, i am not able to understand why, yeah i didn’t you mo’s algo, but except that everything else is correct, given this atleast subtask 2 must have passed, can someone explain what’s wrong?
Can someone tell me where exactly am I going wrong? Thanks in advance.https://www.codechef.com/viewsolution/30533533
Because we know a^a is 0 and ci^x^d should be 0 so d should be ci^x.
Use \n instead of endl and it’ll work ig.
Not Possible, since I haven’t even defined ncr function and I only wanted to test moving of pointers in Mo algorithm(4 while loops) therefore I removed all the functions and set the answer to 0 so that it doesn’t do any computation for each query. The solution I mentioned in the post is CodeChef: Practical coding for everyone. You can cross-verify. I think by mistake you have seen some other solution.
How is that always true when d < Ci, it’s always X xor Ci xor d = 0?
It’s not
Can anyone please explain this part??
Hi @tmwilliamlin,
Thank you for this amazing tutorial.
I have a small question about how you handle the distinct counts by a vector. Although we know that the number of distinct counts in each query cannot exceed O(\sqrt{N}), the number of elements in vector d can indeed exceed O(\sqrt{N}). So how can we guarantee a O(\sqrt{N}) complexity for each query?
Thank you.