Code Invicta Discussion

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

@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

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

XORSEQ
anyone plz help me why my solution getting runtime error for a subtask.I got 20 marks for the solution and it is absolutely fine with the sample case.please help me to remove it
https://www.codechef.com/viewsolution/30746067

you are getting TLE as your soln runs in O(NQ) but the intended soln is O(Qlog(N))

The editorials have been posted for all the problems. Do give them a read and feel free to discuss below them your approaches and ask queries.

Keep coding and stay safe !

2 Likes

Help please, FTALES01
why i am getting TLE for last 2 cases CodeChef: Practical coding for everyone

I think your logic is : If two nodes are part of a cycle then there will be a different part other than the edge path.

The DFS part is a slight modification of printing all the cycles in graph algorithm.

Consider a fully connected graph with N nodes. Then cycles will be formed if we pick any number of nodes between [3 - n].
So total number of nodes that will contibute in cycle will be : 3 * nC3 + 4 * nC4 …+ n* nCn ~= n2^n … so the worst case complexity will be n2^n.

I also used the same code from GFG article in contest seeing its complexity O(n+m) and got TLE. I think the complexity is mentioned wrong there.

Better use the Atriculation points and bridges technique to see if removing the edge makes the two nodes unreachable from each others and increment ans accordingly.

Please correct me If I’m wrong.

2 Likes

My logic is exactly what you said and i think you are right. Thanks for the help and this complexity is a big mistake at GFG have you confirmed this from somewhere else also ?

NO!!!
But if you find any mistake in the wrost-case I gave please let me know.