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 :slight_smile:

5 Likes

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

Code:https://www.codechef.com/viewsolution/25910002

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

Refer this. Unofficial Editorial TSEQ August Long Challenge

Explained in slightly more detail :stuck_out_tongue:

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 :slight_smile:

I solved 4 problems compared to my previous 1 I hope to get to 3 stars next contest :slight_smile:

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.