FCTRE - Editorial

editorial
, , , , , ,
43

Thanks, I will try it.

44

I did exactly same in Python but was failing for 3 test cases of last sub-task.

45

Read the PS carefully, you might also be doing the same mistake. I kept getting TLE on the same 3 test cases.

46

I was getting SIGSEGV. There might be some other issue. I tried so much but was not able to find it. I am still trying to solve the issue.

47

I think I have learned important aspects of Mo’s algo with this problem. Thank You!

48

Help Please, Can someone please tell me why i am getting tle for all the cases. I did it with LCA technique .
CodeChef: Practical coding for everyone . i spent a lot of days in this question help please.

49

well, I just saw that none of the python coders got AC, so I’m not sure about the time limit bro. I’ll try to get AC in python.

50

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

51

@taran_1407 Can this question be solved using HLD?

52

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

1 Like
53

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

54

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
55

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

57

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

58

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

59

why 20*N only?

60

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

61

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

62

"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.

63

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