deepkamal's blog

Help with Problem involving XOR
By deepkamal, history, 4 years ago, In English

How to solve the following problem ? Given an array of size N having integer elements A[1], A[2] , …, A[N] find the maximum value of ( (A[1] xor X) + (A[2] xor X) + (A[3] xor X)+ … + (A[N-1] xor X) + (A[N] xor X) ) for some X belonging to [L,R] . constraints- N <= 100000, 1 <= A[i], L, R <= 1000000000 . A good follow up ques to try is https://www.codechef.com/problems/CHANDF

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

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

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

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

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

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

Problem source?

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

    https://www.hackerrank.com/contests/cp-recruitment-contest-iiti/challenges/the-greatest

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

      Classic problem: fill X's bits from the most significant to the least significant, then do digit dp with the extra state of "is the current number equal to the prefix of L/R" and answer being the max answer considering the unfilled bits. When you fill a bit with 0/1, add 2^B * frequency of the 1/0 in that bit position from the array.

      Please, always link the problem source along with your question.

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

        Can you please explain the dp part more vividly, I am having a hard time understanding it .

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

          If you had solved any digit dp problem you'd know what I'm talking about. I'll explain it if you could change to [0, r] then.

          dp[i][0/1] = max answer if we're filling the i-th bit from most significant to least significant and a boolean flag that says if the prefix currently filled is equal to the prefix in r. If the flag is off, it's different so we can choose anything: dp[i][0] = max(taking 0 here + dp[i+1][0], taking 1 here + dp[i+1][0]). If it's on and the current bit is 0, we must take 0 otherwise we take a number greater than r so dp[i][1] = taking 0 here + dp[i+1][1] and if it's on and the current bit is 1, we can take 0 and make the prefix smaller or take 1 and keep the prefix equal so dp[i][1] = max(taking 0 here + dp[i+1][0], taking 1 here + dp[i+1][1]).

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

            One thing I would like to ask. I can use two flag to check if X is a prefix of r or l respectively. Can we do this with just one flag? Because I don't know how to reduce thisit in this form like $$$f(l,r)=g(f(0,r),f(0,l))$$$

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

              For this problem you can't since you want max. If you wanted the count of some property you would be able to do f(r) — f(l-1) probably but here it's different.

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

                Yes. Can you share your view on the 1st part means if you can do this with just 1 flag?

                Edit: sorry if I misunderstood. Your answer is no for both the part?

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

                  Use 2 flags. I'd make the extra state a bitmask of 2 bits.

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

Another way to look at the dp solution above is that, if you imagine fixing the value of $$$x$$$ bit-by-bit MSB to LSB (in a backtracking-like approach, or more specifically D&C, if that's more towards your style), then if at some point in the recursion you detect that you could fill the remaining bits with any values you want (e.g. you can guarantee that $$$1011?????_{(2)}$$$ would be inside $$$[L..R]$$$ for all assignations of bits to the question marks), you can essentially switch to greedy, and pick the best choice to fill them. This essentially reduces the number of interesting candidates of $$$x$$$ to $$$O(log(R))$$$ (try to prove that).

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

    Another way to think about this problem is as of splitting the segment $$$[L, R]$$$ into $$$O(\mathrm{bits})$$$ segment tree vertices, in the same way as we do with segment tree queries. Indeed, if $$$[L, R]$$$ is a vertex in the segment tree, then some prefix of bits of the number $$$x \in [L, R]$$$ is fixed, and the remaining bits can be chosen arbitrarily. Hence, in each of those $$$O(\mathrm{bits})$$$ subproblems, all bits are independent and it is easy to solve them in $$$O(\mathrm{bits})$$$ time each after some precomputation.

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

      Exactly what I wanted to point out. I think this approach might prove a lot more straightforward in a lot of scenarios where intended solution is digit dp. I guess it goes without saying that you can extend this idea to your needs (e.g. base 10, if problem requires it).

      Perhaps the biggest downside is that it would be more complicated to adapt for the case where the number of digits is up to 1 million, though.

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

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

→ Reply