To start with your answer with p1 p2 p3 should be same as p3 p2 p1
Flattening the tree and using a Persistent Segment Tree worked for me. However, the constraints were a bit harsh and I had to remove some redundant queries and replace some other queries (like queries over entire range) with pre-computed values to squash the constant time factor.
O(n*logn) solution: https://www.codechef.com/viewsolution/25913614
Mine was the exact same approach, except for I maintained a Fenwick Tree for offline processing of queries for finding number of elements less than k in a subtree in N∗logN.
AC Code : https://www.codechef.com/viewsolution/25856801
Changing from dynamic to static and doing few queries as possible gave me AC.
The biggest input ran in about ~3s in my computer just by doing a bunch of “new” memory allocation.
In my opinion, it would have been a better problem if the time limit was less strict. Persistent segment tree is also a good solution.
I solved TSEQ using super node data structure, basically kind of sqrt decomposition on trees…in NrootN
Refer this. Unofficial Editorial TSEQ August Long Challenge
Explained in slightly more detail
Editorial for KS1 is now only pending approval. You may request unapproved copies of the same if you want.
@vijj123 can you provide me the editorial of CHGORAM ?
Hey, its still WIP. I will update here as and when unapproved ones can be requested
I solved 4 problems compared to my previous 1 I hope to get to 3 stars next contest
yup, you are correct . ranking will be decided by considering all the questions from both div 1 and div 2 , as stated in the contest description …
no extra marks will be given to those ,who didn’t attempted other division questions…
The editorial of SYNBAC is done and the unapproved version can be requested by emailing me. The next editorial I am taking up is CHGORAM.
Please release it soon now . cookoff bhi hogya abto XD.
The editorial for CHGORAM is ready and pending approval. Finally I figured out a way to explain things satisfactorily. The unapproved one can be requested by emailing to me.
Next one in the line is TSEQ.
I dont know what to make out of this comment. Its not like I am not trying to write the editorial. If you think you can do better then you are most welcome to apply for next long editorialist
What abt cook-off ratings ?
I can ask @admin if you want but thats all. I am not involved in the decision making in any manner.
No Sir, I am big fan of your editorials, The way you make us understand and efforts you put in your editorials is unmatchable. I thought might be you forgot about it till now. Sorry if the way is bit odd.
I won’t forget it dear
It’d be ironical if someone whose fighting to improve the editorial system forgets about it himself
TSEQ editorial is done and unofficial version can be requested.
The last editorial left is CSTREE.