Code Invicta Discussion

divide n=2 and m=6 equally between them

gurudev ye bhi bta do …
https://www.codechef.com/viewsolution/30738993

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

https://www.codechef.com/viewsolution/30748598

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. https://www.codechef.com/viewsolution/30743229 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: https://www.codechef.com/viewsolution/30749047 HLD is based on this: https://codeforces.com/blog/entry/53170 and this can solve almost all tree query problems.

1 Like

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

1 Like

@admin
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

https://codeforces.com/blog/entry/72212

My approach was similar to yours can you see why i am getting WA?
https://www.codechef.com/viewsolution/30743684
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