Problem A statement

[greedy, bit manipulation]

https://codeforces.com/contest/1625/problem/A

Solution

For each bit we need to choose the most frequent one.

Complexity

Time complexity is O(n log k), space is O(log k), where k is number of bits in numbers

Code

T = int(input())
for _ in range(T):
    n, l = [int(i) for i in input().split()]
    arr = [int(i) for i in input().split()]
    ans = 0
    for i in range(l):
        cands = [x >> i & 1 for x in arr]
        if cands.count(1) >= cands.count(0):
            ans += (1 << i)
 
    print(ans)

Problem B statement

[greedy]

https://codeforces.com/contest/1625/problem/B

Solution

What we need to do is for each letter check all places and then choose the smallest distance between equal places.

Complexity

Time complexity is O(n), space as well

Code

from collections import defaultdict
 
T = int(input())
for _ in range(T):
    n = int(input())
    d = defaultdict(list)
    arr = [int(i) for i in input().split()]
    for i, x in enumerate(arr):
        d[x] += [i]
 
    ans = - 1
    for val in d:
        for x, y in zip(d[val], d[val][1:]):
            ans = max(ans, n - y + x)
 
    print(ans)

Problem C statement

[dp]

https://codeforces.com/contest/1625/problem/C

Solution

The most difficult part for me was to get AC, because we need to use some prunning. Let dp[i, k1, sp] mean that we reached place i with speed sp and we still have k1 attempts to remove some speed limits. Then we can have two options: either we do not remove speed limit, then we continue with new speed. Or we remove speed limit, then we continue with the same speed. important to make it AC, we only consider this option if new speed is bigger than previous, that is if t > sp.

Complexity

Time complexity is O(n*k^2), space complexity is O(nk).

Code

from collections import defaultdict
 
n, l, k = [int(i) for i in input().split()]
arr_d = [int(i) for i in input().split()] + [l]
arr_a = [int(i) for i in input().split()] + [0]
diff = [x - y for x, y in zip(arr_d[1:], arr_d)]
 
dp = {(k, arr_a[0]): 0}
 
for i in range(1, n + 1):
    dp2 = defaultdict(lambda: float("inf"))
    for (k1, sp), val in dp.items():
        t, s = arr_a[i - 1], diff[i - 1]
        dp2[k1, t] = min(dp2[k1, t], val + t * s)
        if k1 >= 1 and t > sp: dp2[k1 - 1, sp] = min(dp2[k1 - 1, sp], val + sp * s)
    dp = dp2
 
print(min(dp.values()))

Problem D statement

[bitmask, divide and conquer, trie, bit manipulation, digit build]

https://codeforces.com/contest/1625/problem/D

Solution

First idea is that if we have say k = 1011101, we want to separate numbers into groups, with bits before most left bit of k, say 1011010111 going to to group 101. Then we can not have more than 2 elements taken from each group. Because if we take 3, then we have either 1010 start twice or 1011 start twice, so when we apply XOR, we will have 0000 start, which is smaller than k. How we can decide if we can take 2 elements in each group or only 1. For this we will use Leetcode 421. Maximum XOR of Two Numbers in an Array: evaluate maximum XOR in each group and if it is >= k, then we take 2 elements, in other case take only one. Also we need to deal with case k = 0, in this case we can take all numbers if we have >= 2 of them.

Complexity

It is O(n log k) for time and O(n) for space.

Code

from collections import defaultdict

def max_XOR(nums):
    ans, mask = 0, 0
    for i in range(31, -1, -1):
        mask |= 1 << i
        found = set([num & mask for num in nums])

        start = ans | 1 << i
        for pref in found:
            if start ^ pref in found:
                ans = start
                break

    return ans

def found_pair(arr_set, x):
    for t in arr_set:
        if x ^ t in arr_set:
            return(t, x^t)

n, k = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
t = k.bit_length()
prefs = defaultdict(list)
for num in arr:
    prefs[num >> t] += [num]
    
corr = {x: i+1 for i, x in enumerate(arr)}
ans = []

for p in prefs:
    pr = prefs[p]
    pr_set = set(prefs[p])
    max_xor = max_XOR(pr)
    if max_xor < k:
        ans += [pr[0]]
    else:
        a, b = found_pair(pr_set, max_xor)
        ans += [a, b]

if len(ans) < 2:
    print(-1)
elif k == 0:
    print(len(arr))
    print(" ".join((str(x)) for x in range(1, n+1)))
elif len(ans) >= 2:
    print(len(ans))
    print(" ".join((str(corr[x])) for x in ans))