Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### awoo's blog

By awoo, history, 3 weeks ago, translation,

1895A - Treasure Chest

Idea: BledDest

Tutorial
Solution (awoo)

1895B - Points and Minimum Distance

Idea: fcspartakm

Tutorial
Solution (fcspartakm)

1895C - Torn Lucky Ticket

Idea: BledDest

Tutorial
Solution (awoo)

1895D - XOR Construction

Idea: AcidWrongGod

Tutorial
Solution (Neon)

1895E - Infinite Card Game

Idea: BledDest

Tutorial
Solution (awoo)

1895F - Fancy Arrays

Idea: Neon

Tutorial
Solution (Neon)

1895G - Two Characters, Two Colors

Idea: BledDest

Tutorial
Solution (BledDest)
• +65

 » 3 weeks ago, # |   +16 ok
 » 3 weeks ago, # |   +19 problems C and D were excellent
 » 3 weeks ago, # |   +19 For problem D it is possible to find b1 bit by bit. Calculate the amount of ones in i-th bit of all b-th if b1_i = 1 and compare with the amount of 1th for numbers from 0 to n-1. If they are different b1_i=0
•  » » 3 weeks ago, # ^ |   0 Yes, this is author's solution)
•  » » » 3 weeks ago, # ^ |   +4 Sure, but it does not require binary trie:)
•  » » » » 3 weeks ago, # ^ |   +14 I meant that author’s (my) solution also does not contain trie. Maybe trie is more educational trick, that's why it is using in editorial.
•  » » » » » 3 weeks ago, # ^ |   0 How do you prove the correctness, that if $b_1$ is chosen optimally then all the numbers are distinct ? Is it because of the property that $a_i \leq 2n$
•  » » » » » » 3 weeks ago, # ^ |   0 For a fixed array b has distinct numbers. Let's say you choose b1 to be x, then the array xor with (b1 ^ x). Since all numbers are distinct, the final array will also distinct
•  » » 3 weeks ago, # ^ |   +4 This was really nice idea. Thanks
•  » » 3 weeks ago, # ^ |   +5 I thought of the following logic but I feel it is more efficient as I do not require to calculate 1's from 0 to (n-1):The following function 'calc' return the first element b[0] of the sequence. It takes input 's', which is equivalent to 'c' in the editorial: (defined as: s[0] = 0 ; s[i] = s[i-1] ^ a[i-1] ;)The code is written in Python. BITS = 32 def calc(s): """ Logic: (Applicable for all 'n' and 'a' for which atleast one valid solution exists) NOTE: 'b' can be obtained by XORing 's' by some appropriate value. If at a bit position in 's', the count of '0' is more then, the corresponding bit position in all elements of 's' will be XORed with '0'. (Hence, effectively it is unchanged) If at a bit position in 's', the count of '1' is more then, the corresponding bit position in all elements of 's' will be XORed with '1'. (Hence, effectively it is "flipped") Otherwise, if both '0' and '1' count are equal at a bit position of 's', the bit position may be arbbitrarily chosen to be either flipped or kept unchanged for all elements. """ global BITS res = 0 for i in range(BITS): count = [0, 0] for j in range(len(s)): count[(s[j]>>i) & 1] += 1 res += (count[0]
•  » » » 3 weeks ago, # ^ |   0 You are just using the fact that amount of 1s on every position is not greater than amount of 0s — agree)
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Yes indeed I am. (So is this precomputation considered cheating?)
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 nope, but are you using it? it is trivial to prove. For any number with bits from the power = 0 (x1, x2, ... x_i, 1,...) the number (x1, x2, ... x_i, 0,...) is smaller so if there is 1 then there is also 0.
•  » » 3 weeks ago, # ^ |   0 how does your solution ensure that the largest b[i] is less than n?
•  » » » 3 weeks ago, # ^ |   0 Since there is a solution and the constructed one satisfies all an-s.
•  » » » 3 weeks ago, # ^ |   +5 Consider the possible solutions for some given 'n'. (In Binary Notation)It follows from one constraint that, if 'v' is a solution, then all solutions satisfying that constraint may be obtained by simply complementing(~) all elements of 'v' at some 0 or more bit-positions.('c' defined as : c[0] = 0 ; c[i] = c[i-1] ^ a[i-1] ; is also a solution to this constraint)Now, as per the other constraint 'v' must also be a permutation of {0, ..., n-1}Let us try to find a path to reach this solution that satisfies both, starting from 'c'.Properties of the goal that we are trying to reach:As our goal is a permutation of {0, ..., n-1}, properties of permutations of {0, ..., n-1} apply to our goalThe i'th bit position will have as many 1's as present in the i'th bit from 0 to n-1.The i'th bit position will always have equal or more 0's than 1's (shown by mcclane57)Now, it turns out that satisfaction of these two properties suffice to reach our goal, assuming that it exists. My program simply tries to satisfy the above 2 properties.
•  » » 3 weeks ago, # ^ |   0 The above solution will only work for even length right? For odd length, you'll have to simply find b1 I guess.
•  » » » 3 weeks ago, # ^ |   0 I think that I've never used in the "proofs" that lengthh is even but indeed for the odd case I calculated b1 as 0^1^...^(n-1)^a2^a4^...^an
•  » » 3 weeks ago, # ^ |   0 231233772. Is this what u talking about.. If Yes can u explain what does the portion bit1[i] != bit2[i] mean ?
•  » » 3 weeks ago, # ^ |   0 But if when b1_i = 1 and when b1_i = 0, the amout of ones are both equal to the amout of ones for numbers from 0 to n-1, you cannot exclude one of them. So how to prove that b1_i = 0 and b1_i = 1 are both right?
•  » » » 3 weeks ago, # ^ |   0 all ones and zeros have the same multiset of tails 0-(i-1) bit so there is no difference which numbers are equal to 1 and which ones to 0)
 » 3 weeks ago, # |   0 Plz someone explain bit by bit solution for problem D. And also explain properly! (Not Editorial solution)
•  » » 3 weeks ago, # ^ |   +1 Sure. The same as in editorial we want to understand the value of b1, then b2 = b1^a1, b3 = b2^a2 and so on. Since XOR is a bitwise operation we can solve this problem bit by bit. For i-th bit of b1 there are two possible cases b1_i = 0 or b1_i = 1. By calculating explicitly b2_i, b3_i ... bn_i we can count the amount of 1 among these values. If the bit is set correctly for b1 then the amount will be equal to amount of numbers from 0 to n-1 with nonzero i-th bit (if amount of 1th equal to amount of 0th then any value of this bit will lead to the solution). The complexity is O(32n) while using bitset<32> to go from int to bits and reverse.
•  » » » 3 weeks ago, # ^ |   0 Why no of 1 and no of 0s matter?
•  » » » » 3 weeks ago, # ^ |   +1 since it is a bitwise operation other bits does not affect the i-th bit of the final numbers and the fact that solution exists. 1 — If the number of 1s differs then it is not a solution. 2 — If the number of 1s = number of 0s then nothing change from swapping between 1 and 0 since the multisets of prefixes "0-(I-1)" bit for 0s and 1s are the same (corollary from the equality of number of 1s and 0s).
 » 3 weeks ago, # |   0 Problem 1895C - Torn Lucky Ticket is a fantastic Problem!! Thank you for this problem..
 » 3 weeks ago, # |   0 It is sad that I was almost 1 hour solving problem D with operator OR (always have a problem where I failed to "read" the problem) and had no time for problem E but C-E are nice problems for educational.
 » 3 weeks ago, # |   0 Plz explain me problem C why suml — sumr>0 made Lucky Ticket,thanks.
•  » » 3 weeks ago, # ^ |   0 Check my implementation, it feels a bit simpler to me with similar idea.Let's say we are checking 52349. Split it at every digit and try as left and right part of ticket:  52349 | anything with length 5, sum 23 (5,23) 5234 | 9 + (3,14) 523 | 49 + (1, 5) (1,9) + 52 | 349 (3,13) + 5 | 2349 
 » 3 weeks ago, # | ← Rev. 2 →   0 fcspartakm shouldnt the minimum be less than n numbers instead of n-1 ? as we can have a_2...a_n+1 as possible candidates for second minimum as for the first one being a_1? for second problem
 » 3 weeks ago, # |   +79 Problem D is solvable in linear time (ignoring IO) in the word RAM model.I'll show an alternate $O(n \log n)$ solution, and then show how to optimize it.Notice that among the numbers from $0$ to $n-1$, $\left \lfloor\frac{n}{2}\right\rfloor$ numbers are odd, and the rest are even.If $n$ is odd, these two counts are different, so we can use it to determine whether the first number of $b$ should be odd or even. Make it even if the count is already correct, and odd if we need to correct the count.If $n$ is even, toggling the $0$-th bit in each number is a bijection from the list onto itself, so it doesn't matter whether we set the bit in the first number of $b$.A similar argument can be made for each of the other bit positions, but the formula for the expected count is a bit more complicated. The expected number of $1$-bits in the $j$-th bit position is $n - \left \lfloor\frac{n}{2^{j+1}}\right\rfloor \cdot 2^j - \min\left(n \bmod 2^{j+1}, 2^j\right)$So now we have a way to construct the answer given the number of $1$-bits seen in each bit position. Counting this in $O(n \log n)$ time is easy, but doing it in $O(n)$ is also possible, using bitset. I learned this trick from simonlindholm's "troll" subtask in the problem ligatures.The idea is that when incrementing a counter, we very rarely need to carry. It takes $2^j$ increments before we increment the $j$-th bit, so the total number of carries when incrementing a number $n$ times starting from $0$ is $\frac{n}{1} + \frac{n}{2} + \frac{n}{4} + \dots \in O(n)$In code it looks something like this: void increment(std::span bits) { bool carry = true; for (bool &b : bits) { bool next_carry = carry & b; b ^= carry; carry = next_carry; if (!carry) break; // this early exit is what makes it amortized O(n) } } So for a single counter, we can implement the counting in linear time while operating on just $O(1)$ bits at a time. But in the word RAM model, we can operate on $\Omega(\log n)$ bits at a time. We'll use this to run several counters in parallel. For each bit-position in the counter, instead of storing a single bit, we store a bitset, and then the increment function takes a mask of which of the counters to increment: void increment(std::span> bits, std::bitset<20> carry) { for (auto &b : bits) { auto next_carry = carry & b; b ^= carry; carry = next_carry; if (carry.none()) break; } } But modifying the code like this broke the amortization argument. Different counters may need to carry at different times. The trick to fix this is to somehow synchronize the carrying by allowing different representations of the same number inside the counters. Instead of letting each digit in the binary representation be $0$ or $1$, we let it be $0$, $1$, or $2$. It's still base $2$, it's just that digits are allowed to be a little too big. It can also be seen as storing the carry bit as a lazy update. To do this, we store a pair of bitmasks for each bit position: void increment(std::span, std::bitset<20>> bits, std::bitset<20> carry) { for (auto &[lo, hi] : bits) { assert((lo & hi).none()); // invariant: we have only 0, 1, or 2 as the digit, not 3 hi |= carry & lo; lo ^= carry; if (we_dont_bother_carrying_further()) break; carry = hi; hi.reset(); } } Now if we pick an appropriate condition for not bothering to carry further, we can both maintain the digit-invariant and achieve $O(n)$ complexity. In case the $0$-th digit becomes $2$ after $2$ steps, we need to carry in the $3$-rd step. After that the $0$-th digit is either $0$ or $1$. From then on, we need to carry from the $0$-th digit every $2$-nd step. For simplicity, we can ignore the $2$ carry-less increments at the start, and just always carry from the $0$-th digit every other step. Similar arguments can show that we need to carry from the $i$-th digit every $2^i$-th step. How many steps we need to carry turns out to be the number of trailing zeros in the number of steps we have completed so far.Here's an implementation: 231387717Note that this is not the most efficient parallel bit-counter. You might get better performance by doing this trick in base $4$ instead, and with some extra care, you can let the digits go further past their usual allowed range.
 » 3 weeks ago, # |   0 Problem C and D were so cool ..
 » 3 weeks ago, # | ← Rev. 5 →   +1 In problem D, how bit by bit logic is working in below case cause even after bit flips the count of set bits at 2nd bit are unequal in b.n=6, a= 1 6 1 4 7, b= 0 1 7 6 2 5(calculated prefix xor of a if b starts with 0)output: is not in range of 0-5 but it exceeded for above test case
•  » » 3 weeks ago, # ^ |   0 It seems to me that this example does not satisfy any solution!
•  » » » 3 weeks ago, # ^ |   0 Then how how can we ensure that after flipping i-th bit, where count of set bits is unequal becomes equal to that of set bits of at i-th bit in (0-n-1). Could you please clarify in detail?
•  » » » » 3 weeks ago, # ^ |   0 if it is not true than there is no solution because the I-s bit should be either 1 or 0.
•  » » » » » 3 weeks ago, # ^ |   0 ok thank you!
 » 3 weeks ago, # |   0 Trie is a more standard way to solve D, I like it better!
 » 3 weeks ago, # | ← Rev. 2 →   0 Can someone explain the trie solution ? how the trie is constructed, and how are they finding max b_1^c_i
•  » » 3 weeks ago, # ^ |   0 Okay so since b2 = a1 ^ b1, b3 = a1 ^ a2 ^ b1, ..., bn = a1 ^ ... ^ an-1 ^ b1. From this fact you can observe that finding b1 will automatically result in finding all the other values. So start by forming a Trie which contains pointer to a bit array of size [2] (for each bit 0\1. Now since all you need to check is that MAX(b1 ^ pref[i]) < N insert all the pref values inside the trie bit by bit. After inserting these values enumerate for each b1 in the range [0, N). Now how do you find MAX(b1^pref[i]) in LOG(N) well since XOR is only one for two non-similar bits. Start iterating for each bit and checking if the trie has a bit opposite to the set bit in the b1 you are checking, if this is true then choose that path and descend the trie else move forward. implementationhttps://codeforces.com/contest/1895/submission/231413643
•  » » » 3 weeks ago, # ^ |   0 A basic Trie that does the job. Basicstruct T { T* bits[2]; T() { bits[0]=nullptr; bits[1] = nullptr; } }; void insert(T* R, int N) { T* ND = R; for(int i=21; i>=0; i--) { if(!ND->bits[N >> i & 1]) ND->bits[N >> i & 1] = new T(); ND = ND->bits[N >> i & 1]; } } int F(T* R, int N) { T* ND = R; int mx = 0; for(int i=21; i>=0; i--) { if(ND->bits[1 ^ N >> i & 1]) { mx |= 1 << i; ND = ND->bits[1 ^ N >> i & 1]; } else ND = ND->bits[N >> i & 1]; } return mx; } 
•  » » » 3 weeks ago, # ^ |   0 thanks
 » 3 weeks ago, # | ← Rev. 3 →   0 Problem C can be solved by using a binary search. (it takes 280ms) submission
 » 3 weeks ago, # |   0 Can anyone help to understand E last test case, please? 1 10 5 1 10 5 As a result: 0 1 0 Does 0 mean, win or lose is impossible? What does 1 mean for draw? Why answer is not 0? Next move doesn't make any sense.A few more questions: - Does playing optimal mean that player 1 know exactly all cards of player 2? Or they play "greedy"? - Does "starting moves" mean some smart sequence of moves from player 1 that "trap" player 2?
 » 3 weeks ago, # |   0 In the question Tresure Chest why the y is added 2 times any concept if have can anyone tell me y+y−(x+d)
 » 3 weeks ago, # |   0 What's the issue with this code for problem C(Torn Lucky Ticket)? 232186103
•  » » 3 weeks ago, # ^ |   0 Take a look at Ticket 17140 from CF Stress for a counter example.
 » 2 weeks ago, # |   0 Problem D can be solved by just counting the number of 0 and 1 bits at each position and comparing with the expected count for the sequence $[0, \ldots, n-1]$. If at some position the count is wrong, we must flip that bit. 231908591
 » 2 weeks ago, # |   0 Problem D : !!Read first solution from the comment box. There is a proof or simple observations that if n==(2^k) then anything is possible as b1. But when n!=(2^k) then the number of open and close form of a particular bit are not same , in this case we can take decision . But some bits open and close forms number are same ,in this case first observation works.
 » 12 days ago, # |   0 what is the solution for problem 1895D - XOR Construction let n is 2 and the array a is {4} input: 2 4 outout ?
 » 12 days ago, # | ← Rev. 2 →   0 edit: nevermind, it got accepted, but while trying to prove the main idea, i was able to find an input for which it does not work. i think i have a different solution which got accepted for problem G, but i still have no proof why it works exactly.first of all, the decision is easy whenever b[i] >= r[i], so i will not discuss this case.otherwise, then i will initially consider all characters 1 being red and all characters 0 being blue. for the s[i] = 0, we keep for each of them the value v[i] = r[i] — b[i], the slack they have until its better that they become blue.for the s[i] = 1, we keep for each of them the value x[i] = r[i] — b[i] — {amount of s[j] = 0, j < i, and s[j] still red, i.e., the cost of its inversions}.now we consider what needs to be updated if we change s[i] = 1 to red. when we change s[i] to red then we can add x[i] to the answer. also, when we turn s[i] = 1 to red, all positions j < i with s[j] = 0 will have their slack values reduced by 1 and we need to update them accordingly. also, whenever their slack v[j] become 0, i.e., s[j] = 0 became blue, we have to update all s[k] = 1 with k > j by adding 1 to x[k], because this inversion does not exist anymore, so we should not count it.we dont know which s[i] = 1 are good to paint red. this is where i'm not sure why it works, but this can be done just in the order of the maximum current x[i]. we just paint it red, update everything and find the next maximum an so on. the current cost can increase or decrease, but the answer is the maximum value of these changes.to keep track of all this, we can use 2 range add segment trees, one of maximum x[i], and another with min v[i], and all the operations are O(log n) (finding maxes, finding values less or equal to zero, range adding 1s, etc.). the details are easy to figure out. maybe there is some easier way to implement.232978585
 » 12 days ago, # |   0 Great
 » 10 days ago, # |   0 For problem D, I don't understand one logic from 0 to n-1, to check its distinctness by the number of set bits. Number of unset bits>= Number of set bits it is distinct. Suppose for n=6.000 001 010 011 100 100Here, the number of set bits <= number of unset bits. But the above things aren't unique, here 4 is twice.
 » 8 days ago, # |   0 best explanation, thank you so much