Codeforces Educational Codeforces Round 151

Posted on Edited on In Disqus:

Contest link
Official editorial

I solved the first two problems and got stuck on the third.
Rating change: 1407 -> 1378

A. Forbidden Integer

Case analysis. If 1 can be chosen, then any number can definitely be formed.
If not, but 2 and 3 can be chosen, then any number except 1 can also be formed.
If only 2 can be chosen, then only even numbers can be formed.

Time complexity: O(t * n),

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
t = int(input())

for _ in range(t):
    n, k, x = map(int, input().split())

    if x == 1:
        if k == 1:
            print('NO')
            continue
        elif k == 2:
            if n % 2 == 0:
                print('YES')
                print(n//2)
                for _ in range(n//2):
                    print(2, end=' ')
                print()
            else:
                print('NO')
                continue
        else:
            print('YES')
            print(n//2)
            while n > 3:
                print(2, end=' ')
                n -= 2
            print(n)
    else:
        print('YES')
        print(n)
        for _ in range(n):
            print(1, end=' ')
        print()

B. Come Together

Case analysis. B and C are in different quadrants, so the longest shared route differs.

Time complexity: O(t),
Space complexity: O(1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
t = int(input())

for _ in range(t):
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    B[0] = B[0] - A[0]
    B[1] = B[1] - A[1]
    C[0] = C[0] - A[0]
    C[1] = C[1] - A[1]

    # if B and C are in the same quadrant
    if (B[0] * C[0] > 0 and B[1] * C[1] > 0) \
        or (B[0] * C[0] == 0 and B[1] * C[1] > 0) \
        or (B[0] * C[0] > 0 and B[1] * C[1] == 0):
        print(min(abs(B[0]), abs(C[0])) + 1 + min(abs(B[1]), abs(C[1])) + 1 - 1)
    elif B[0] * C[0] <= 0 and B[1] * C[1] > 0: # the same side but different quadrant
        print(min(abs(B[1]), abs(C[1])) + 1)
    elif B[0] * C[0] > 0 and B[1] * C[1] <= 0: # the same side but different quadrant
        print(min(abs(B[0]), abs(C[0])) + 1)
    else: # opposite quadrant
        print(1)

C. Strong Password

The brute-force method is simple: backtrack to enumerate all passwords satisfying the l and r constraints, then check whether each is a subsequence of s.
However, the time complexity of the backtracking step is already exponential.

The correct solution is greedy. For each position, choose the digit that appears as far to the right as possible in s.
Time complexity: O(m*D + n), n = s.length, D = r_i - l_i = 10