Codeforces contest 1644

Problem A statement

[string]

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

Solution

Just check athat r is before R, g is before G and b is before B.

Complexity

It is O(1) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
 
T = int(input())
for _ in range(T):
    s = input().rstrip()
    if s.index("r") < s.index("R") and s.index("g") < s.index("G") and s.index("b") < s.index("B"):
        print("YES")
    else:
        print("NO")

Problem B statement

[permutation, array]

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

Solution

For n = 3 find answer by hands. For n > 3 use cycle permutations of n, n-1, ..., 1.

Complexity

It is O(n^2) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
 
T = int(input())
for _ in range(T):
    n = int(input())
    if n == 3:
        print("3 2 1")
        print("1 3 2")
        print("3 1 2")
    else:
        a = list(range(1, n + 1))[::-1]
        for i in range(n):
            print(" ".join(str(x) for x in a[i:]+a[:i]))

Problem C statement

[array, accumulate]

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

Solution

Notice that first of all we always can choose numbers we need to increase being continious range. Also, let us define by s[i] maximum sum in window of length i. Then imagine that we look for f(3), how we can calculate it? We can take s[0], s[1] + x, s[2] + 2x, s[3] + 3x, s[4] + 3x and so on. In similar way we can calculate all f(i)`.

Complexity

It is O(n^2) for time and O(n) for space. I wonder if we can solve this problem in O(n) time.

Code

I = lambda: [int(i) for i in input().split()]
from itertools import accumulate
 
T = int(input())
for _ in range(T):
    n, x = I()
    arr = I()
    acc = [0] + list(accumulate(arr))
    s = [-float("inf")]*(n + 1)
    for i in range(n):
        for j in range(i, n + 1):
            s[j - i] = max(s[j - i], acc[j] - acc[i])
 
    ans = [0] * (n + 1)
    for i in range(0, n + 1):
        p1 = max([s[j] + j*x for j in range(i)] or [0])
        p2 = max(s[j] + i*x for j in range(i, n+1))
        ans[i] = max(p1, p2)
 
    print(" ".join(str(x) for x in ans))

Problem D statement

[math, combinatorics]

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

Solution

It was quite frustrating during contest: I had linear time algorithm, but I get TLE, so after contest I need to rewrite it to make AC. So, the idea is the following: it can happen, that if we have cell (1, 1) and then we have cells (1, 3) and (4, 1), then we can say that the first cell is completely eaten by next cells. It means that from all m + n - 1 cells we colored, all of them will be recolored later. Also if cell is not completely eaten by another cell, we have k options to color it. What we need to calculate is how many not completely eaten cells we have in the end. Now, let us understand, when it can happen. We will traverse our cells from the end.

If we have (x, y) and we have (x, y1) and (x1, y) already. We will keep sx is set for seen rows and sy is set for seen columns, then it means that x and y were already seen.
It also can happen that len(sx) == n, it means that we have all rows totally covered after our cell, so cell is completely eaten. Same is for rows.

Complexity

It is O(m + n) for time and space.

Code

I = lambda: [int(i) for i in input().split()]
 
t = int(input())
for _ in range(t):
    n, m, k, q = I()
    diff = 0
    queries = [I() for _ in range(q)]
    sx, sy = set(), set()
    for x, y in reversed(queries):
        if (x in sx and y in sy) or len(sx) == n or len(sy) == m: continue
        diff += 1
        sx.add(x)
        sy.add(y)
    print(pow(k, diff, 998244353))

Codeforces contest 1644

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