do_good_'s blog

Any idea for problem f at todays abc 126 ?

By do_good_, history, 6 years ago, In English

hello, how to solve problem f of today's abc 126 ? https://atcoder.jp/contests/abc126/tasks/abc126_f . since editorial is in japanese.

i also request rng_58 to add english version of editorial , since the rating has been increased to 1999.

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

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

First, hardcode the M = 1 case. For all other M, there exists an answer if and only if K < 2^M. In these cases, we can proceed as follows:

  1. Print all numbers 1 through 2^M-1 except K.
  2. Print K.
  3. Print the same numbers in step one, but in the reverse order.
  4. Print K again.

For the non-K numbers, this works because in the interval between them, various numbers appear twice (and thus don't contribute to the xor result) and K appears once, leading to an xor of K. For K, the xor includes all the numbers in step three, meaning every number from 1 to 2^M-1 except K. Note that this is equal to the xor of all the numbers from 1 to 2^M-1 (including K) and K. We can prove that the xor of the numbers 1 to 2^M-1 is zero, so our xor is xor(0, K) = K, as desired.

The claim that xor(1, 2, ..., 2^M-1) = 0 is only true for M >= 2. This is why we must hardcode the M=1 case (the answer is 0 0 1 1 or its reverse if K=0 and -1 otherwise). M=0 works with this algorithm anyway, as with K > 0, we correctly print -1, and with K = 0, we correctly print 0 0.

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

    That was beautiful explanation! Thank you, Geothermal.

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

    That was a nice explanation. But what is the proof that if k >= 2 ^ M no solution exists.

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

      In this case, the most significant bit of K will not be set in any element of our permutation. Because each bit is independent of the others when we perform the xor operation, we cannot generate this bit without having it in some element of our permutation.

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

I have a solution, but I am not sure if it is correct because when I submitted it in the contest I forgot to leave spaces between numbers in the output, and now the verdict is too slow, so I am still waiting.

So my solution (without being sure that its correct) is this:

if K = 0, then sequence has that form: $$$0 \; 0 \; 1 \; 1 \; 2 \; 2 \; 3 \; 3 \cdots (2^M - 1) \; (2^M - 1)$$$

if K is larger than $$$2^M - 1$$$, then we can't create a xor equal to K with numbers that are in the range $$$[0, 2^M - 1]$$$. So we return -1.

In any other case (when $$$0 \leq K \leq 2^M - 1$$$), we follow this strategy. Initialize an array and add K. Now for every $$$0 \leq i \leq 2^M - 1$$$ different than K, insert i in the front and back of the current array. Finally add the second K in the end of the array.

For example for M = 2, K = 2, array/sequence is 3 1 0 2 0 1 3 2.

For every number different than K, the condition is satisfied because every term is deleted with its pair except the middle K. Now for the pair of K's, the condition is satisfied as well. This is because $$$0 \; \text{xor} \; 1 \; \text{xor} \; 2 \; \text{xor} \; \cdots \; \text{xor} \; 2^M - 1 = 0$$$, so if you remove one number, the xor of the rest equal to that number.

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

    This looks correct (and seems equivalent to my solution above). Note that you actually don't need to handle the K=0 case separately--your general strategy works for that case too.

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

      Verdict is over and solution passed. Unfortunately, I forgot to leave spaces between numbers in the output and it pissed me of !

      Yea, solutions are equivalent and case K=0 is not necessary. Actually M=1, K=0 is the necessary case as you mentioned above.

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

        XD I forgot to print it in reverse

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

Btw, the contest was rated ? Because I don't see any updates there.

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

The main idea that needs to be used in $$$F$$$ is that $$$x \oplus x = 0$$$, for any $$$x$$$.

It is not possible for us to reach any $$$x$$$, if $$$x > 2^M$$$ as every integer only has $$$M$$$ bits.

Let us leverage this. Suppose we want to reach $$$K$$$. If we print $$$K$$$ and then print the remaining numbers on one side and the same numbers on the other side in reversed order, then we will always have xor $$$= K$$$ for any pair of numbers.

The only exception is what will be the xor between $$$k$$$ and $$$k$$$ ?

To Solve this, we will simply put $$$K$$$ at one end !

Now, $$$K \oplus 1 \oplus \dots \oplus K$$$ will simply be $$$K \oplus (1 \oplus 2 \oplus \dots \oplus 2^M)$$$.

The Xor of all numbers from $$$1$$$ to $$$n$$$ is $$$0$$$ whenever $$$n$$$ is a multiple of $$$4$$$. All powers of 2 greater than $$$2$$$ are powers of $$$4$$$.

So the expression simply becomes $$$K \oplus 0 = K $$$

Here is my explanation. My solutions to the other problems are included as well.

→ Reply