awoo's blog

Educational Codeforces Round 157 Editorial
By awoo, history, 6 months ago, translation, In English

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)
  • Vote: I like it
  • +65
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it +16 Vote: I do not like it

ok

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

problems C and D were excellent

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

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

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

    Yes, this is author's solution)

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

      Sure, but it does not require binary trie:)

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

        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.

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

          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$$$

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

    This was really nice idea. Thanks

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

    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]<count[1])<<i
    
    return res
    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are just using the fact that amount of 1s on every position is not greater than amount of 0s — agree)

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

        Yes indeed I am. (So is this precomputation considered cheating?)

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

          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.

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

    how does your solution ensure that the largest b[i] is less than n?

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

      Since there is a solution and the constructed one satisfies all an-s.

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

      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 goal

      The 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.

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

    The above solution will only work for even length right? For odd length, you'll have to simply find b1 I guess.

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

      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

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

    231233772. Is this what u talking about.. If Yes can u explain what does the portion bit1[i] != bit2[i] mean ?

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

    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?

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

      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)

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

Plz someone explain bit by bit solution for problem D. And also explain properly! (Not Editorial solution)

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

    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.

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

      Why no of 1 and no of 0s matter?

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

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

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

Problem 1895C - Torn Lucky Ticket is a fantastic Problem!! Thank you for this problem..

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

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.

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

Plz explain me problem C why suml — sumr>0 made Lucky Ticket,thanks.

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

    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
    → Reply
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

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<bool> 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<std::bitset<20>> 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::pair<std::bitset<20>, 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: 231387717

Note 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.

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

Problem C and D were so cool ..

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

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

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

    It seems to me that this example does not satisfy any solution!

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

      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?

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

        if it is not true than there is no solution because the I-s bit should be either 1 or 0.

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

Trie is a more standard way to solve D, I like it better!

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

Can someone explain the trie solution ? how the trie is constructed, and how are they finding max b_1^c_i

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

    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.

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

      A basic Trie that does the job.

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

      thanks

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

Problem C can be solved by using a binary search. (it takes 280ms) submission

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

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?

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

In the question Tresure Chest why the y is added 2 times any concept if have can anyone tell me y+y−(x+d)

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

What's the issue with this code for problem C(Torn Lucky Ticket)?

232186103

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Could you explain what you mean by expected count for the sequence? Maybe with an example

    → Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the solution for problem 1895D - XOR Construction let n is 2 and the array a is {4} input: 2 4 outout ?

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

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

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 100

Here, the number of set bits <= number of unset bits. But the above things aren't unique, here 4 is twice.

→ Reply
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

best explanation, thank you so much

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D:this is a good question, i love it

→ Reply