Help with the problem LCM Tree

Revision en1, by DXTsT, 2019-09-27 22:40:26

This problem is from 2018 ICPC North American Qualifier Contest. Here is the link: LCM Tree.

I tried to solve this problem using bitset DP. Each number from $$$S$$$ is a candidate for building LCM Tree, initially, only the bit of greatest element is on. Every time we append two nodes with $$$lcm{(S_j, S_k)} = S_i$$$ to the bit which is on and turn off that bit. However, if multiple numbers have the same value, my approach will fail. I'm wondering if this approach can actually work on this problem or there is a better approach?

Tags #combinatorics, #dynamic programing, tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English DXTsT 2019-09-27 22:40:26 602 Initial revision (published)