Can anyone tell me any order for this algorithm?

Правка en4, от Mahdi_Hajibeygi, 2019-06-23 21:00:40

Hi

We have a problem on a tree.

Imagine order of our algorithm is:

Sigma x(i) ^ 2

That if we define sz[v] as number of vertices in subtree of v, x(i) is number of different sz[u] between v's children.

It's easy to see it's O(n * sqrt(n)).

But after this submission for problem 1179D I saw it was realy fast and now I think it might be better than O(n * sqrt(n)).

Any idea?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Mahdi_Hajibeygi 2019-06-24 15:58:39 48 Tiny change: 'ht be best order we can \n\nproof for ' -> 'ht be best\n\norder we can proof for '
en5 Английский Mahdi_Hajibeygi 2019-06-24 15:47:18 578 Tiny change: 'e largest `Sigma x(i' -> 'e largest \n`Sigma x(i'
en4 Английский Mahdi_Hajibeygi 2019-06-23 21:00:40 2 Tiny change: 'ly fast ans now I thi' -> 'ly fast and now I thi'
en3 Английский Mahdi_Hajibeygi 2019-06-23 20:38:37 15
en2 Английский Mahdi_Hajibeygi 2019-06-23 20:36:50 136
en1 Английский Mahdi_Hajibeygi 2019-06-23 20:33:45 397 Initial revision (published)