Code Invicta Discussion

divide n=2 and m=6 equally between them

gurudev ye bhi bta do …

literally I do not understand how you are talking about division between n = 2 and m = 6
can you please tell briefly. I don’t know why I am not getting it

I passed CHRIST02 with a sketchy sqrt-decomp that probably shouldn’t have passed.

First, optimize the naive O(NQ) with LCA (specifically binary lifting), making it so you only traverse exactly the vertices on the path. Then the solution looks roughly like:

while (u != lca) {
  if (l <= arr[u] && arr[u] <= r) ++ans;
  u = par[u];
# do the same for v

Then fix some power of 2, call it C. For each node with depth >= C, store its first C ancestors in a sorted array. For a query, if the node is at least C depth below the LCA, binary search on how many values are between L and R for the query in the sorted values. Then use the jump-pointer from the binary lifting to advance C ancestors of the current node. This becomes O(Q\log(N)(C + \frac{N}{C})) overall, which passed in 1.9s with C = 256.

Submission (code is quite ugly though)

Seems like other people used persistent segment trees or heavy-light decomposition.

I don’t know how to do CHRIST01.

what time it takes to printing all 6 digit numbers in python?

@better_sleep Can u tell Me what i am doing wrong?I implemented same as u

Isn’t it O(n \sqrt{n \log(n)}) with optimal C?

Oh true, that does become slightly better.

Well, I think my solution is quite short and simple to understand. CodeChef: Practical coding for everyone I think it is O(nlog^3n), but I use lower_bound which is quite fast. Also, you could make this solution faster by using Fenwick tree like so: CodeChef: Practical coding for everyone HLD is based on this: Easiest HLD with subtree queries - Codeforces and this can solve almost all tree query problems.

1 Like

You declared n as integer , it should be long long .

1 Like

I still wonder why custom contests
don’t have/post editorials ( atleast outline ).

Editorials will be posted soon. @ubc_123

1 Like

What will be the approach in order to minimise the answer ?

Check the 2nd section in in the solution sketch to of Jeremy and bearimy problem

My approach was similar to yours can you see why i am getting WA?
nxt[h] stores the next house having zero

Can you please explain how you solve the " Bring Positivity " Question !

Please share a tag for " Bring Positivity ". Thanks

You can check out the editorial : CHRIST01 - Editorial

1 Like