# Invitation to CodeChef August Long Challenge 2019

@taran_1407
For Tree sequence problem. Can you please explain the idea a little bit please?

I used HLD + seg_tree. In each node I store the whether the current range is increasing or not, and if there are ā-1ā in between I stored the answer (as we know what is the max and min we can put there). So at each node we have at most two ranges for which we donāt know the answer (the left end and the right end).

I know itās very hard to find mistake in the solution. But if possible can you please look at approach and can tell whether my approach is correct or not? Please ā¦

You are on fire! Congrats again (after CF ;P)

1 Like

I had the same thing, then I removed all dynamic allocation and pointer usage by static memory and indices of that static memory and got AC!

1 Like

my solution of CHGORAM is N*logN \hspace{0mm}.

thanx

5 Likes

First I used merged sort tree(NLOGNLOGN) which timed out.Then used persistent segment tree(N*LOGN) still timed out.

1 Like

I used sum query segtree after sorting queries.
https://www.geeksforgeeks.org/number-elements-less-equal-given-number-given-subarray/
Along with euler tour and logic
Passes : http://www.codechef.com/viewsolution/25797868/

2 Likes

Can some1 plz tell where am i going wrong? i used upperbound and lowerbound
on sorted array to get elements greater and lower than P2.
my sol: https://www.codechef.com/viewsolution/25895177
Edit : Lol i misunderstood the Question. Nvm!!

To start with your answer with p1 p2 p3 should be same as p3 p2 p1

1 Like

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.

Hereās my O(n*logn) solution: https://www.codechef.com/viewsolution/25913614

3 Likes

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

1 Like

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.

1 Like

Niceā¦
I solved TSEQ using super node data structure, basically kind of sqrt decomposition on treesā¦in NrootN

2 Likes

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

1 Like

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ā¦

Hi all,

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.