October Long Challenge D-Dimensional MST

Revision en1, by sid9406, 2020-10-13 11:19:35

I couldn't solve this problem from Codechef Long Challenge https://www.codechef.com/OCT20A/problems/DDIMMST . Can someone help me in this problem. I tried reading the editorial https://discuss.codechef.com/t/ddimmst-editorial/79385 but no help . What i don't understand is how are we able to reduce the number of edges from n^2 to 2^d*n .

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English sid9406 2020-10-13 12:32:05 275
en1 English sid9406 2020-10-13 11:19:35 382 Initial revision (published)