[contest:521852]↵
↵
### [A. XOR Mixup](https://codeforces.com/gym/521852/problem/A) ↵
original question [link](https://codeforces.com/contest/1698/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
Any element of the array works. Why?↵
↵
Given an array having numbers a1, a2, a3, a4, ..., aj we need to find a number in the array such that the xor of the rest of the elements equals this number. The array's overall xor is zero. So, any element from the array can be selected as the answer since the xor of a number with itself is zero. Therefore, a1, a2, a3, a4, ... or aj can be chosen as the answer.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
def solve():↵
length = int(input())↵
arr = list(map(int, input().split()))↵
↵
return arr[0]↵
↵
↵
def main():↵
t = int(input())↵
↵
for _ in range(t):↵
print(solve())↵
↵
main()↵
~~~~~↵
</spoiler>↵
↵
### [B. Special Numbers](https://codeforces.com/gym/521852/problem/B) ↵
original question [link](https://codeforces.com/contest/1594/problem/B)↵
↵
<spoiler summary="Solution">↵
↵
We can use the fact that any number in base n can be written as a sum of powers of n. So, we can convert k to binary and use the bits of the binary representation of k to determine which powers of n to use. For example, if k = 13 and n = 3, we can convert k to binary to get 1101. Then, we can use the 1's in the binary representation to determine which powers of 3 to use. In this case, we have 1101, which means we can use the powers of 3 corresponding to 3, 2, and 0 (since these are the positions of the 1's in the binary representation). So, the k-th special number for n = 3 is 3^3 + 3^2 + 3^0 = 37.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
MOD = 1000000007↵
t = int(input())↵
↵
for _ in range(t):↵
n, k = map(int, input().split())↵
↵
ans = 0↵
product = 1↵
↵
for i in range(32):↵
if k & (1 << i):↵
ans = (ans + product) % MOD↵
product *= n↵
product %= MOD↵
↵
print(ans)↵
~~~~~↵
</spoiler>↵
↵
### [C. Rock and Lever](https://codeforces.com/gym/521852/problem/C) ↵
original question [link](https://codeforces.com/contest/1420/problem/B)↵
↵
<spoiler summary="Solution">↵
↵
In order for the given condition "ai & aj >= ai ^ aj" to hold true, it is necessary for the most significant bits of both ai and aj to be set. This is because if we have both the k-th bits of ai and aj as 1, then the result of their "AND" logical operation would also be 1 and the result of their "XOR" logical operation would be 0. Additionally, since the most significant bit holds the highest value in the binary representation, if the most significant bit of ai & aj is greater than the most significant bit of ai^aj, then ai & aj would be greater than ai ^ aj.↵
↵
In order to solve this problem, we need to iterate through the array and for each number, check if there is another element in the array that has the same most significant bit. If we are able to find such a pair, then we can conclude that the condition of "ai & aj >= ai ^ aj" holds true for those two numbers.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from collections import defaultdict↵
def most_significant_bit(num):↵
msb = 0↵
↵
while num != 0:↵
num >>= 1↵
msb += 1↵
↵
return msb↵
↵
def solve():↵
msb_dict = defaultdict(int)↵
count = 0↵
↵
n = int(input())↵
nums = list(map(int, input().split()))↵
↵
for num in nums:↵
msb = most_significant_bit(num)↵
count += msb_dict[msb]↵
msb_dict[msb] += 1↵
↵
return count↵
↵
def main():↵
t = int(input())↵
↵
for _ in range(num_tests):↵
print(solve())↵
↵
main()↵
~~~~~↵
</spoiler>↵
↵
### [D. Powers Of Two](https://codeforces.com/gym/521852/problem/D) ↵
original question [link](https://codeforces.com/contest/1095/problem/C)↵
↵
<spoiler summary="Solution">↵
↵
To calculate the minimum number of powers of two needed to obtain, we can use the binary representation of n. Each bit in the binary representation corresponds to a power of two, which becomes a summand in the answer. If the number of summands required is greater than k , then it is impossible to obtain the sum using only powers of two. If we have fewer summands than k, we can repeatedly choose a summand from the set and split it into two summands of equal value until we have exactly k summands. This can be done by maintaining a data structure (e.g., stack, array, queue, ...) and choosing an arbitrary summand to split. This process terminates when we have exactly k summands, since we will always be able to choose a summand to split until all summands are equal to 1.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
def solve():↵
n, k = map(int, input().split())↵
if k > n:↵
print("NO")↵
return↵
↵
ans = []↵
for i in range(32):↵
if n & (1 << i):↵
ans.append(1 << i)↵
↵
if len(ans) > k:↵
print("NO")↵
return↵
↵
print("YES")↵
i = 0↵
while len(ans) < k:↵
while ans[i] == 1:↵
i += 1↵
ans[i] //= 2↵
ans.append(ans[i])↵
print(*sorted(ans))↵
↵
↵
solve()↵
~~~~~↵
</spoiler>↵
↵
### [E. Little Girl and Maximum XOR](https://codeforces.com/gym/521852/problem/E) ↵
original question [link](https://codeforces.com/contest/276/problem/D)↵
↵
<spoiler summary="Solution">↵
↵
consider the binary representation of start and end. Let p be the position of the leftmost set bit in start, and Let q be the position of the leftmost set bit in end.↵
↵
Then, all pairs of integers a and b between start and end, inclusive, have the same leftmost p bits and the same leftmost q bits. The remaining bits in a and b can take any value between 0 and 2^k — 1, inclusive, where k is the position of the leftmost set bit in the XOR of start and end. Therefore, the maximum value of a xor b for all pairs of integers a and b between start and end, inclusive, is 2^k — 1.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from collections import defaultdict↵
def most_significant_bit(num):↵
msb = 0↵
↵
while num != 0:↵
num >>= 1↵
msb += 1↵
↵
return msb↵
↵
def main():↵
start, end = map(int, input().split())↵
xor = start ^ end↵
msb = most_significant_bit(xor)↵
max_xor = (1 << msb) - 1↵
print(max_xor)↵
↵
main()↵
~~~~~↵
</spoiler>↵
↵
↵
### [A. XOR Mixup](https://codeforces.com/gym/521852/problem/A) ↵
original question [link](https://codeforces.com/contest/1698/problem/A)↵
↵
<spoiler summary="Solution">↵
↵
Any element of the array works. Why?↵
↵
Given an array having numbers a1, a2, a3, a4, ..., aj we need to find a number in the array such that the xor of the rest of the elements equals this number. The array's overall xor is zero. So, any element from the array can be selected as the answer since the xor of a number with itself is zero. Therefore, a1, a2, a3, a4, ... or aj can be chosen as the answer.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
def solve():↵
length = int(input())↵
arr = list(map(int, input().split()))↵
↵
return arr[0]↵
↵
↵
def main():↵
t = int(input())↵
↵
for _ in range(t):↵
print(solve())↵
↵
main()↵
~~~~~↵
</spoiler>↵
↵
### [B. Special Numbers](https://codeforces.com/gym/521852/problem/B) ↵
original question [link](https://codeforces.com/contest/1594/problem/B)↵
↵
<spoiler summary="Solution">↵
↵
We can use the fact that any number in base n can be written as a sum of powers of n. So, we can convert k to binary and use the bits of the binary representation of k to determine which powers of n to use. For example, if k = 13 and n = 3, we can convert k to binary to get 1101. Then, we can use the 1's in the binary representation to determine which powers of 3 to use. In this case, we have 1101, which means we can use the powers of 3 corresponding to 3, 2, and 0 (since these are the positions of the 1's in the binary representation). So, the k-th special number for n = 3 is 3^3 + 3^2 + 3^0 = 37.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
MOD = 1000000007↵
t = int(input())↵
↵
for _ in range(t):↵
n, k = map(int, input().split())↵
↵
ans = 0↵
product = 1↵
↵
for i in range(32):↵
if k & (1 << i):↵
ans = (ans + product) % MOD↵
product *= n↵
product %= MOD↵
↵
print(ans)↵
~~~~~↵
</spoiler>↵
↵
### [C. Rock and Lever](https://codeforces.com/gym/521852/problem/C) ↵
original question [link](https://codeforces.com/contest/1420/problem/B)↵
↵
<spoiler summary="Solution">↵
↵
In order for the given condition "ai & aj >= ai ^ aj" to hold true, it is necessary for the most significant bits of both ai and aj to be set. This is because if we have both the k-th bits of ai and aj as 1, then the result of their "AND" logical operation would also be 1 and the result of their "XOR" logical operation would be 0. Additionally, since the most significant bit holds the highest value in the binary representation, if the most significant bit of ai & aj is greater than the most significant bit of ai^aj, then ai & aj would be greater than ai ^ aj.↵
↵
In order to solve this problem, we need to iterate through the array and for each number, check if there is another element in the array that has the same most significant bit. If we are able to find such a pair, then we can conclude that the condition of "ai & aj >= ai ^ aj" holds true for those two numbers.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from collections import defaultdict↵
def most_significant_bit(num):↵
msb = 0↵
↵
while num != 0:↵
num >>= 1↵
msb += 1↵
↵
return msb↵
↵
def solve():↵
msb_dict = defaultdict(int)↵
count = 0↵
↵
n = int(input())↵
nums = list(map(int, input().split()))↵
↵
for num in nums:↵
msb = most_significant_bit(num)↵
count += msb_dict[msb]↵
msb_dict[msb] += 1↵
↵
return count↵
↵
def main():↵
t = int(input())↵
↵
for _ in range(num_tests):↵
print(solve())↵
↵
main()↵
~~~~~↵
</spoiler>↵
↵
### [D. Powers Of Two](https://codeforces.com/gym/521852/problem/D) ↵
original question [link](https://codeforces.com/contest/1095/problem/C)↵
↵
<spoiler summary="Solution">↵
↵
To calculate the minimum number of powers of two needed to obtain, we can use the binary representation of n. Each bit in the binary representation corresponds to a power of two, which becomes a summand in the answer. If the number of summands required is greater than k , then it is impossible to obtain the sum using only powers of two. If we have fewer summands than k, we can repeatedly choose a summand from the set and split it into two summands of equal value until we have exactly k summands. This can be done by maintaining a data structure (e.g., stack, array, queue, ...) and choosing an arbitrary summand to split. This process terminates when we have exactly k summands, since we will always be able to choose a summand to split until all summands are equal to 1.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
def solve():↵
n, k = map(int, input().split())↵
if k > n:↵
print("NO")↵
return↵
↵
ans = []↵
for i in range(32):↵
if n & (1 << i):↵
ans.append(1 << i)↵
↵
if len(ans) > k:↵
print("NO")↵
return↵
↵
print("YES")↵
i = 0↵
while len(ans) < k:↵
while ans[i] == 1:↵
i += 1↵
ans[i] //= 2↵
ans.append(ans[i])↵
print(*sorted(ans))↵
↵
↵
solve()↵
~~~~~↵
</spoiler>↵
↵
### [E. Little Girl and Maximum XOR](https://codeforces.com/gym/521852/problem/E) ↵
original question [link](https://codeforces.com/contest/276/problem/D)↵
↵
<spoiler summary="Solution">↵
↵
consider the binary representation of start and end. Let p be the position of the leftmost set bit in start, and Let q be the position of the leftmost set bit in end.↵
↵
Then, all pairs of integers a and b between start and end, inclusive, have the same leftmost p bits and the same leftmost q bits. The remaining bits in a and b can take any value between 0 and 2^k — 1, inclusive, where k is the position of the leftmost set bit in the XOR of start and end. Therefore, the maximum value of a xor b for all pairs of integers a and b between start and end, inclusive, is 2^k — 1.↵
</spoiler>↵
↵
<spoiler summary="Code">↵
~~~~~↵
from collections import defaultdict↵
def most_significant_bit(num):↵
msb = 0↵
↵
while num != 0:↵
num >>= 1↵
msb += 1↵
↵
return msb↵
↵
def main():↵
start, end = map(int, input().split())↵
xor = start ^ end↵
msb = most_significant_bit(xor)↵
max_xor = (1 << msb) - 1↵
print(max_xor)↵
↵
main()↵
~~~~~↵
</spoiler>↵
↵
