Best algo you have(mine is O(Q^2*N))
Posted by
Elias 25 Feb 2016 12:33
Hello! Can somebody tell me if there is a faster algo than O(Q^2*N)? My algo works pretty fast, but I wondered if there is a better way to do it.
Re: Best algo you have(mine is O(Q^2*N))
Posted by
Arseniy 11 Mar 2016 21:49
My solution Q*N, lol
Or no
I'm not sure
Edited by author 11.03.2016 21:50
Edited by author 11.03.2016 21:50
My algo is O(N^3) and I got AC 0.001s!
Posted by
c_pp 25 Dec 2016 17:35
My algo is fills dp[vertex][presaved edges] array (result is dp[1][Q]), where total loops N^3/6 < 2*10^5.
There maximum presaved edges = Q, but more vertexes have less edges than Q.
Let edges[v] - number of edges of v vertex.
So there O( N * sum( edges[ v ] * ( edges[ v ] + 1 ) / 2 ) ) = O( N^3 / 6 ).
