DXTsT's blog

Help with the problem LCM Tree
By DXTsT, history, 5 years ago, In English

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?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution slides: http://cs.baylor.edu/~hamerly/icpc/qualifier_2018/outlines-naq-2018.pdf

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have looked at that, and I tried with that solution. But just can't figure out how exactly can I solve this.

    → Reply