2168.md (3366B)
1 Source: https://codeforces.com/blog/entry/148053 2 3 As the highest non-red, non-alt-account person in the round, I feel it is my duty to supply the community with an editorial. 4 5 ### [2168A1 - Encode and Decode (Easy Version)](/contest/2168/problem/A1 "Testing Round 20 (Unrated, Communication Problems)") 6 7 **Editorial** 8 9 Since $1 ≤ a_i ≤ 26$, we can assign each value from $1$ to $26$ to a letter `a-z`. 10 11 **Code** 12 13 [347267664](/contest/2168/submission/347267664 "Submission 347267664 by Sul_A.") 14 15 ### [2168A2 - Encode and Decode (Hard Version)](/contest/2168/problem/A2 "Testing Round 20 (Unrated, Communication Problems)") 16 17 **Editorial** 18 19 Using $7$ characters, we can encode $26^7 \approx 8 \cdot 10^9$ possibilities. For each number in the array, encode into a $7$-digit base-$26$ number. It is important to make sure each number takes up the same number of characters. 20 21 **Code** 22 23 [347268278](/contest/2168/submission/347268278 "Submission 347268278 by Sul_A.") 24 25 ### [2168B - Locate](/contest/2168/problem/B "Testing Round 20 (Unrated, Communication Problems)") 26 27 **Editorial** 28 29 Let's try to solve the problem player B has to solve. 30 31 Let the range of a subarray be $max(p_l, p_{l+1}, ..., p_r) - min(p_l, p_{l+1}, ..., p_r)$. A subarray has range $n-1$ iff it contains both $1$ and $n$. We can binary search on the shortest *prefix* with range $n-1$, this will find the latter position of $1$ or $n$. Also binary search on the shortest *suffix* with range $n-1$, this will find the former position of $1$ or $n$. Now we've found the position of $1$ and $n$, but we don't know which is which. 32 33 This is where player A comes in. If $1$ appears before $n$, he will send $0$; otherwise, he will send $1$. Now player B can figure out which is which. 34 35 **Code** 36 37 [347270351](/contest/2168/submission/347270351 "Submission 347270351 by Sul_A.") 38 39 ### [2168C - Intercepting Butterflies](/contest/2168/problem/C "Testing Round 20 (Unrated, Communication Problems)") 40 41 **Editorial** 42 43 Let's phrase the problem slightly differently. 44 45 * Player A has a binary string of length $15$, and he will send a binary string of length $20$. 46 * On the way, none or one of the bits get flipped. 47 * Given the altered string, $B$ must find the original binary string of length $15$. 48 49 The first $15$ bits ($s_{1..15}$) will be allocated for the original string, and the remaining $5$ bits will be used to reconstruct where the flip happened. 50 51 The next $4$ ($s_{15..19}$) will house the bitwise XOR of the all the positions in the original string that are `1`. The last bit ($s_{20}$) will be the number of bits in previous $4$ bits mod $2$. 52 53 Now there are $2$ cases: 54 55 #### Case 1: A flip happens in $s_{16..20}$ 56 57 We can detect this case by checking if the last bit matches what it's supposed to be. If it doesn't, a flip has happened somewhere in the last $5$ bits. In this case, the original $15$ are completely untouched. 58 59 #### Case 2: A flip doesn't happen or happens in $s_{1..15}$ 60 61 Here, we calculate the bitwise XOR of all the `1` in $s_{1..15}$. Let $x$ be this value and $y$ be the number stored in $s_{16..19}$. The cool thing is: $x \bigoplus y$ will be the position of the flipped bit, or $0$ if no flip occurred. This is because if a flip occured at position $k$, $x$ becomes $x \bigoplus k$. 62 63 **Code** 64 65 [347273446](/contest/2168/submission/347273446 "Submission 347273446 by Sul_A.")