Invitation to CodeChef August Long Challenge 2019

general
,
39

thanx :slight_smile:

4 Likes
40

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

Code:CodeChef: Practical coding for everyone

1 Like
41

I used sum query segtree after sorting queries.
Numbsubarrayer of elements less than or equal to a given number in a given - GeeksforGeeks
Along with euler tour and logic
Passes : CodeChef: Practical coding for everyone

2 Likes
42

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!!

43

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

1 Like
44

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: CodeChef: Practical coding for everyone

3 Likes
45

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 NlogN.
AC Code : CodeChef: Practical coding for everyone

1 Like
46

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
47

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

3 Likes
48

Refer this. Unofficial Editorial TSEQ August Long Challenge

Explained in slightly more detail :stuck_out_tongue:

49

Editorial for KS1 is now only pending approval. You may request unapproved copies of the same if you want.

50

@vijj123 can you provide me the editorial of CHGORAM ?

51

Hey, its still WIP. I will update here as and when unapproved ones can be requested :slight_smile:

52

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

1 Like
53

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…

54

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.

55

Please release it soon now . cookoff bhi hogya abto XD.

56

Hi,

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.

Regards
vijju123

1 Like
57

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

1 Like
58

What abt cook-off ratings ?