Codeforces contest 1635

Problem A statement

[bit manipulation]

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

Solution

What we need to do here is just calculate OR of all numbers.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
import io, os, sys
 
T = int(input())
for _ in range(T):
    n = int(input())
    arr = I()
    t = arr[0]
    for i in range(1, n):
        t |= arr[i]
    print(t)

Problem B statement

[greedy, array]

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

Solution

Let us first find all places to_fix, which we need to fix, imagine it is 3, 5, 7, 10, 12. Then if we change index 4, we can fix two local maximums at once. So, what we need to do is try to do pairs if possible.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
import io, os, sys
 
T = int(input())
for _ in range(T):
    n = int(input())
    arr = I()
    ans = 0
    to_fix = []
    for i in range(1, n - 1):
        if arr[i] > arr[i-1] and arr[i] > arr[i + 1]:
            to_fix += [i]
 
    to_fix_set = set(to_fix)
    for i in to_fix:
        if i in to_fix_set and i + 2 in to_fix_set:
            arr[i+1] = max(arr[i], arr[i+2])
            to_fix_set.remove(i)
            to_fix_set.remove(i + 2)
            ans += 1
        elif i in to_fix_set:
            arr[i+1] = arr[i]
            to_fix_set.remove(i)
            ans += 1
 
    print(ans)
    print(" ".join(str(x) for x in arr))

Problem C statement

[sort, constructive]

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

Solution

If last element is negative and numbers are not sorted, there is no way to sort them, because if we look at a[-3], then we can only change it to make it positive, so a[-3], a[-2], a[-1] must be sorted. Now, if we look at a[-4] using the same logic it is also sorted. If last element is >= 0, then previous element must be bigger, because it can not be changed. All other element can be made arr[-2] - arr[-1] in n - 2 steps.

Complexity

It is O(n) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
import io, os, sys
 
T = int(input())
for _ in range(T):
    n = int(input())
    arr = I()
    if arr[-1] < 0:
        if arr != sorted(arr):
            print(-1)
        else:
            print(0)
    else:
        if arr[-2] > arr[-1]:
            print(-1)
        else:
            print(n - 2)
            for i in range(n - 2):
                print(i + 1, n - 1, n)

Problem D statement

[dp, math]

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

Solution

First of all we can remove all useless numbers, like if we have 11 and 5, we can delete 11. How we do it? We sort numbers and then while possible decrese number 11 -> 5 -> 2 -> stop. If we meet some another number from set, we delete it. Now, define by dp[i] number of values in range [2^i, 2^{i+1}). Then when we have x -> 2x + 1, it will add all values from dp[i] to dp[i + 1], because interval will be inside. Similar is for x -> 4*x, it will be embedding of dp[i] into dp[i + 2]. Also we need to deal with number of new values in the interval, which we calculate by counter X.

Complexity

It is O(p + n log C + n log n) for time and O(n + p) for space.

Code

I = lambda: [int(i) for i in input().split()]
from collections import Counter
 
(n, p), arr = I(), I()
M = 10**9 + 7
 
C = set(arr)
for num in sorted(arr):
    x = num
    while x % 4 != 2 and x > 0:
        x //= 2 if x % 2 else 4
        if x in C and x != num: C.remove(num)
 
X = Counter()
for num in C:
    X[num.bit_length()] += 1
 
dp = [0] * (p + 3)
for i in range(p + 1):
    dp[i] = (dp[i-1] + dp[i-2] + X[i]) % M
 
print(sum(dp) % M)

Codeforces contest 1635

Problem A statement

Solution

Complexity

Code

Problem B statement

Solution

Complexity

Code

Problem C statement

Solution

Complexity

Code

Problem D statement

Solution

Complexity

Code

Problem E statement

Solution

Complexity

Code

Problem F statement

Solution

Complexity

Code