Блог пользователя DXTsT

Автор DXTsT, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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