20240809

My skin has had problems. Maybe I have a nut allergy?

slept 15 hours straight (~20240810). I may be exhausted

• Set an alarm for tomorrow

1979B. XOR Sequences

Observation: maximum matching suffix?

Codeforces Round 951 (Div. 2) Editorial

Consider two numbers v and u such that x xor v = y xor u. Then consider the numbers x xor (v + 1) and y xor (u + 1). Let's look at the last bit of v and u.

We're considering arbitrary numbers that elements from both sequences match.

Possible scenarios:

• Both bits are equal to 0 - adding one will change the bits at the same positions, therefore x xor (v + 1) = y xor (u + 1);

• Both bits are equal to 1 - adding one will change the bits at the same positions and also add one to the next bit, therefore we can similarly consider the next bit;

I guess this means x xor (v + 1) = y for (u + 1), too.

• Bits are different - adding one to the zero bit will only change one bit, while the subsequent bit of the other number will be changed. This means that x xor (v + 1) != y xor (u + 1).

It is clear that we need to maximize the number of zeros in the maximum matching suffix of u and v.

?

Obviously, this number is equal to the maximum matching suffix of x and y.

:thinking_face:

Let k be the length of the maximum matching suffic of x and y, then the answer is 2 ** k.

I think I understand the explanation 30%. I'll visit here again later to fully understand it.

"""
0 1
2 ** 0

  0
101
2 ** 0

1100
 100
2 ** 3

111001
100101
2 ** 2

10010110111100101010111010001
     110111100101010111010001
2 ** 25
"""


for _ in range(int(input())):
    x, y = map(int, input().split())

    xbin: list[str] = list(map(int, list(bin(x)[2:])))
    ybin: list[str] = list(map(int, list(bin(y)[2:])))

    # padding
    ybin = [0] * (len(xbin) - len(ybin)) + ybin
    xbin = [0] * (len(ybin) - len(xbin)) + xbin

    count: int = 0
    for i in range(len(xbin)):
        if ybin[i] != xbin[i]:
            count = 0  # I don\'t remember how I got to this solution
        else:
            count += 1

    print(2 ** count)

Ketone 5 mg/dl

Salad 40g Nuts 20g Protein shake 10g

Total carbohydrate 70 g

MUST:

• Buy bath tissue
• Codeforces Round 965 (Div. 2) (20240810)
• DL Renewal (20240812)

TODO:

• Read editorial of 1979B
• Retry 1986C

index 20240808 20240810