abhaypatil2000's blog

Bitwise anding interesting question. Simple yet not so simple.
By abhaypatil2000, history, 3 years ago, In English

Given an array $$$A$$$ of $$$n$$$ integers, the elements are shuffled to form an array $$$B$$$.

Let the array $$$B$$$ be $$$b_0,b_1,...b_{n-1}$$$.

We define $$$f_i = b_0$$$&$$$b_1$$$&$$$... b_i$$$.

We need to find the minimum possible value of $$$\sum_{i=0}^{n-1} f_i$$$.

Constraints:
1 <= n <= 1000
0 <= $$$b_i$$$ <= 1015

Sample input: 10, 1, 21, 1

Answer: 1

Here is my solution, which just kinda solves it, but I am not satisfied

There are basically 2 processes in the solution. Each process returns an answer. Do the first process, obtain the first answer. Do the second process, and obtain another answer. And return the min of both these answers.

Process 1:
Find the min element, and swap it with the 0th element, make it the prefix_and. Now loop on i from 1 to n-1, and find the element which gives the smallest and with pref_and, and swap that element with ith element, and now make pref_and &= ith element. Return the pref_and as the answer.

Process 2:
Consider all the pairs of 2 elements in the array, and find that pair which results in the smallest and. In this pair, swap the smaller element with 0th element and the other with the 1st element. Now loop on i from 2 to n-1, and continue as in Process 1. Return the pref_and.

The thing is that I don't know why this works. I.e., I don't have a formal proof, or a convincing enough proof. I just tried Process 1, and half the cases passed, and when I changed my solution to Process 2, the other half test cases passed.

So I just merged both these solutions, and got an AC. So not sure why this works.

Note:
Sorting in decreasing won't work. Eg: 1, 1, 2 sorting -> 1, 1, 2 optimal -> 1, 2, 1

  • Vote: I like it
  • -3
  • Vote: I do not like it

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

Auto comment: topic has been updated by abhaypatil2000 (previous revision, new revision, compare).

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

Do you know how to solve it ? If yes, can you give some hint

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

Can’t we just sort A in non-decreasing order? I think that would be the optimal array

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

Can you please share a link to the problem?

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

    I don't have the link to the question. It was a question in one of the OA.

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

I dont really undersrtand your solution (which i think is understandable since you dont even understand it yourself), but i came up with my own.

[the solution wasnt right, check my comment below]

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

    I don't have the link to the question. It was a question in one of the OA.

    My solution had 2 parts. First part was same as yours. In second part, I brute forced first 2 elements, and the rest was same. Find the answer for both these parts, and return the minimum of these 2. This was the accepted answer.

    I am confused why brute forcing only first 2 elements will give the answer. If it was not working for brute forcing the first element, then why did only first 2 elements give AC. Why only 2?

    That's the main question.

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

      It turns out both our solutions are wrong.

      I made a program that generates all inputs with size n such that each number goes up to 63 and tested your solution against it. Here are the cases of size 4 that go wrong:

      Spoiler

      My solution also fails in those cases:

      Spoiler

      Im showing n = 4 because its the first one that goes wrong.

      Also, a clarification on this:

      First part was same as yours

      From what i understand in your first part you put the smallest element first, but in mine i try every first number possible.

      Ill try to fix my solution and will answer if i can do it.

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

        In my case I was taking the smallest element. If you try all the elements, then the solution will reach n*n*n

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

          It doesnt, i explain in my solution that in at most 64 steps you can stop choosing numbers, since all of the bits that couldve been erased would have done so by that point

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

I suspect this is unsolvable correctly for the given constraints.

Unless I'm missing something, if this problem was correct, there would exist a correct solution for this problem as well (since and / or are symmetric on flipping the bits, and flipping the bits reverses the sign of all inequalities). But as far as I remember the intended solution was incorrect and this problem was proven to be NP Hard.

In fact, the intended incorrect solution did exactly the same as your first idea if I recall correctly.

→ Reply