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.

# | User | Rating |
---|---|---|

1 | tourist | 3686 |

2 | mnbvmar | 3509 |

3 | Benq | 3339 |

4 | LHiC | 3330 |

5 | wxhtxdy | 3329 |

6 | sunset | 3279 |

7 | Petr | 3275 |

7 | V--o_o--V | 3275 |

9 | yutaka1999 | 3190 |

10 | ecnerwala | 3153 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | Radewoosh | 189 |

3 | rng_58 | 165 |

4 | PikMike | 160 |

5 | Vovuh | 158 |

6 | Petr | 155 |

7 | 300iq | 154 |

8 | majk | 149 |

9 | Um_nik | 148 |

10 | Swistakk | 144 |

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.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2019 07:15:03 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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:

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.

That was beautiful explanation! Thank you, Geothermal.

Thanks Geothermal

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

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.

Thanks. I got it now

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.

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.

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.

XD I forgot to print it in reverse

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

It's unrated.

why, I didn't see any official posts about it.

how can it be unrated , it was written in mail that it will be rated upto 1999 rng_58

use Google Translate to convert it into English

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.

good one saikat : )