Please read the new rule regarding the restriction on the use of AI tools. ×

GOJO_GOKU_KURAMA's blog

By GOJO_GOKU_KURAMA, history, 7 months ago, In English

https://mirror.codeforces.com/contest/1945/problem/H

Hey cfers hope all are doing well can anyone please tell me how to solve this please do share your code and logic thanks.

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

»
7 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Hints for reaching the solution

1945H - НОД больше

Solution
Implementation details

I was in a hurry during the contest, so my implementation was not much neat, here is it anyway 252257639.

This was all but, if somebody have any questions, I will be happy to answer.

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    we don't need to store the cnt[bit

    True. But if you do store it, your implementation will become a lot simpler. If you have the count of zeroes at each position, then, when you remove $$$a[i]$$$ and $$$a[j]$$$ from the set, you simply decrease the count by $$$0$$$ or $$$1$$$ or $$$2$$$ (depending upon whether the outgoing element has that bit set or unset). Then, if the count is zero, the bitwise AND would contain $$$1$$$ at that position. We can repeat for each bit.

    Sample Submission

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thank you

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've added hints for H : GCD is Greater on CF Step

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I loved the editorial I performed all the 4 soln that mention including the wa3 of nlogn too made my clear concepts thnks you