Code Invicta Discussion

general
21

divide n=2 and m=6 equally between them

22

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

23
24

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

26

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.

27

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

28

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

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

29
30

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

31

Oh true, that does become slightly better.

32

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
33

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

1 Like
34

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

35

Editorials will be posted soon. @ubc_123

1 Like
36

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

37

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

38

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

39

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

40

Please share a tag for " Bring Positivity ". Thanks

41

You can check out the editorial : CHRIST01 - Editorial

1 Like