codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.")