FCTRE - Editorial

If you get AC then let me know what I am missing.

@taran_1407 Can this question be solved using HLD?

I tried all my best on that approach but couldn’t get further 40 points

1 Like

I do not know of any HLD solution, nor do i expect. Maybe.

I don’t know what people are talking about using blocks of size 400 to 600. There is no need to use blocks. You can use an block of size 168 then use an array of size 1000 to store at index p where the pth prime number is stored in the array of size 168 this leaves every node with just one value. So your code will run in exactly 168*N + N log N. After that Implementing MO’s algorithm on tree with each node having one value is a cakewalk. See the solution here execution time 2.01 sec CodeChef: Practical coding for everyone .

2 Likes

Isn’t HLD the first choice for questions related to queries on a tree?

Can you please suggest some problems which deal with querying on the path from node u to node v in a tree.

Thanks

thanks,got AC with Gilbert curve and got to know a cool topic.

Can anyone tell me what am I missing in solution please
Getting WA
Link

why 20*N only?

20 ~ log(A_i) is chosen as each number may have up to 20 to contribute to the exponent. Say all values in array are 2^{19} and linear tree, you are gonna need inverse of 19*N

Can anyone help me to understand why I am getting TLE for Subtask 3?
Here is the link of the solution - CodeChef: Practical coding for everyone
cc: @taran_1407 @dvyn01

"While sorting intervals in MO’s algorithm, Sorting intervals in the first block in increasing order of endpoints, in the second block by decreasing order of endpoints and so on. "

@admin: Can you explain in detail why it reduces time for right pointer? I am not able to understand from the explanation from cp-algo page.

Can Somone tell why my solution getting tle in last 2 test cases(I have tried every block size)…
@taran_1407
solution link: CodeChef: Practical coding for everyone

@admin @taran_1407 Could you please reply to the queries? It is not appreciated. It seems not good idea to ignore messages after the contest is over. Lot of people like me facing problem for this problem but no body cares to look into that. It demotivates the coder.

@dvyn01

Try to visualize the movement of right pointer. Assume for now that intervals in second block are in sorted order (r_i < r_j). Now for the queries in the first block, the right pointer can go up to N. If the intervals in the second block are also in sorted order, then for the first query in the second block, the right pointer has to move again to the beginning (ie, the smallest possible right pointer for the second block), and again process queries up to N in the worst case.
But instead, we can do better if we sort the intervals in the second block in decreasing order of right pointers. In this case, the right pointer doesn’t have to go all the way to the leftmost interval and come back up to the rightmost one. This time as the intervals are reverse-sorted, so we start processing the queries in reverse order and travel to the leftmost interval, but we don’t have to return back to the rightmost point as the queries are already processes (which we were doing in the previous case).
For the third block, the queries are again in sorted order, and we were at the leftmost point of the second block, and so again the right pointer has to travel comparatively less distance.
Hope it helps.

4 Likes

Thanks. Its clear now.

@dvyn01 Can you help me to find the problem in above solution? I get TLE for subtask 3. What I am doing wrong?

Nice explanation !

Here’s one which uses a similar idea, Count on a tree.