xoringbitset's blog

A task made by me!
By xoringbitset, 3 years ago, In English

Hello, there, I recently came up with a task and while solving it, thought the idea was elegant so just wanted to share it here, so people could enjoy it and I hopefully could see more ideas to solve it!

The task goes like this-

Given an array of integers, output distinct indices of two numbers, it they exist, such that bitwise & of both the numbers is greater than or equal to the GCD(Greatest common divisor) of both the numbers.

$$$2<=n<=10^{5}$$$

$$$1<=a_{i}<=10^{9}$$$

Hints-

Hint 1
Hint 2
Hint 3
Hint 4

I will write a solution in a while, but I think the hints must have been enough for you to solve this problem ;). Let me know if there are any other solutions which work, and your thoughts about whether you enjoyed this problem or not.

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

Comments Comments (14)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Note that gcd of two distinct numbers is <= max_of_both_numbers /2

$$$0 <= a_i <= 10^9$$$

$$$gcd(0, 10^9) = 10^9$$$

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Aaah, you are right, should have said for the given constraints!

    Edit-Fixed the element range, thanks!

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

      IMO, it's a cool problem and solution!

      It seems that condition $$$0 \le a_i$$$ could be kept as is because if $$$a_j = 0$$$, then $$$0 = a_i \; AND \; 0 = a_i \; AND \; a_j \ge gcd(a_i, a_j) = gcd(a_i, 0) = a_i$$$ could only be true if $$$0>=a_i \Leftrightarrow a_i=0$$$ so with $$$a_j = 0$$$ the only valid pair of $$$(a_i, a_j)$$$ values would be (0, 0) (of course, assuming $$$gcd(0, 0) = 0$$$ technicality) — checking if array has two zeroes is easy.

      I might have an idea of possible generalisation(s) (not sure if it could be worth to create a separate problem out of this), perhaps somebody would like to discuss this using CF private message?

      → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

Soo...guys, how did it go? Any specific concerns/feedback about the problem? If you want, I can write the solution sketch, in case the hints didn't help. Also, are there any other things which seem to work?

Edit-Thanks for the feedback, great to see that people enjoyed the problem.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    I thought about it for about 5 minutes and didn't see anything, then read the hints and got the solution. I think its a nice problem

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Very nice problem, I liked the idea very much. Thanks for sharing!!

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

    Very nice problem, thanks for sharing!

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

    I used gcd(x,y) = gcd(x, y-x) <= y-x (for y > x) and arrived at the same solution of any two numbers with same MSB since the difference is definitely less than 2^MSB.

    → Reply
»
3 years ago, # |
  Vote: I like it +54 Vote: I do not like it

I think rand() works.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +93 Vote: I do not like it

It is very good that you have shared your problem with us. But it would have been better if you had sent this problem to Codeforces/Codechef/other resource for competitive programming. This would have been a great task for some contest.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think the maximum size of an array that doesn't contain valid pairs is small.

Maybe the following idea works: Just sort the numbers in decreasing order and iterate over all pairs while execution time is less than the time limit of the problem. If we don't find any pair, we can assume that the answer doesn't exist.

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

    You have the right intuition but you have to construct an answer. Checkout the hints, since you are close!

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice!

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

that's always a cool feeling when one finds a problem idea

→ Reply