FCTRE - Editorial

editorial
, , , , , ,
38

Without Blocks, you can get AC using Hilbert curve to sort the queries.

1 Like
39

I guess using pointer might be the issue,pointers are pretty slow,also you will still get tle,you need block optimization or better sorting order.

1 Like
40

SELF PROMOTION 100

41

I have used gilbert Order to sort queries but it was not enough to pass all testcases.
None of the solution passed all subtask in python3 and pypy3 so was the timelimit correct for python codes?
My solution link:-CodeChef: Practical coding for everyone

42

@taran_1407 or anyone who understands java please just look my code and can u tell why its
giving RE in Subtask1 and Subtask 2. I have commented the code and it will be easier to understand.

https://www.codechef.com/viewsolution/31860645

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