Problem A statement

[math]

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

Solution

Just evalueate sum and then subtract all powers of 2.

Complexity

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

Code

T = int(input())
for _ in range(T):
    n = int(input())
    k = n.bit_length()
    print((n*(n+1)//2) - (1<<(k+1)) + 2)

Problem B statement

[simulate, string]

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

Solution

Just similate process.

Complexity

Time complexity is O(s*m).

Code

s = [i for i in input().rstrip()]
m = int(input())
n = len(s)
for _ in range(m):
    l, r, k = [int(i) for i in input().split()]
    mid = r - (k % (r - l + 1))
    s[l-1:r] = s[mid:r] + s[l-1:mid]

print("".join(s))

Problem C statement

[geometry, sort]

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

Solution

The difficulty for this problem is that numbers are quite big, so we will have rounding error if we use atan2. So, what we need to do is to sort data first by atan2, and then for each pair of adjacent element calculate conangent of their difference. We choose cotangent, because it is monotone on [0, pi). And we need to choose the angle with biggest conangent.

Complexity

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

Code

from math import atan2

arr = []
n = int(input())
for j in range(n):
    x, y = [int(i) for i in input().split()]
    arr += [(atan2(x, y), j, x, y)]

arr = sorted(arr)

best = (-1, 0)
ans = (arr[0][1], arr[1][1])

for p1, p2 in zip(arr, arr[1:] + [arr[0]]):
    x1, y1 = p1[2], p1[3]
    x2, y2 = p2[2], p2[3]
    t = (x1 * x2 + y1 * y2, abs(x1 * y2 - x2 * y1))
    if t[0] * best[1] > t[1] * best[0]:
        best = t
        ans = (p1[1], p2[1])

print(str(ans[0] + 1) + " " + str(ans[1] + 1))

If we want to avoid floats at all, we can use function polarLess to sort points by polar coordinate.

def top(p):
    return p[1] < 0 or p[1] == 0 and p[0] < 0

def cross(p1, p2):
    return p1[0]*p2[1] - p2[0]*p1[1]

def polarLess(a, b):
    ta, tb = top(a), top(b)
    if ta != tb: return ta
    return cross(a, b) > 0

Problem D statement

[dfs, bfs, graph]

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

Solution

Just use usual dfs, where we need to be careful to avoid TLE. It is better to use stack for dfs, it works faster. Also we need to use fast IO to get AC. Idea is just traverse graph from every point and for every component (island) to count its perimeter: number of edges going from * to ..

Complexity

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

Code

from collections import Counter
import io, os, sys
#input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n, m, k = [int(i) for i in input().split()]
grid, queries, d = [], [], Counter()

for _ in range(n):
    grid += [[i for i in input()]]

for _ in range(k):
    queries += [[int(i) for i in input().split()]]

def dfs(x, y, g):
    grid[x][y] = g
    stk, cnt = [(x, y)], 0
    while stk:
        x, y = stk.pop()
        for dx, dy in (x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1):
            if grid[dx][dy] == '*':
                cnt += 1
            elif grid[dx][dy] == '.':
                grid[dx][dy] = g
                stk.append((dx, dy))
    d[g] = cnt

g = 0
for x in range(m):
    for y in range(n):
        if grid[y][x] == ".":
            dfs(y, x, g)
            g += 1

ans = [d[int(grid[x - 1][y - 1])] for x, y in queries]
sys.stdout.write(" ".join(map(str, ans)) + "\n")

Problem E statement

[dp]

https://codeforces.com/contest/598/problem/E

Solution

Quite classical dp problem, where dfs(n, m, k) is answer for size (n, m) and we need to get k cells. Then to get it w eneed to look at all vertical and horizontal cuts, and we take k1 from one part and k - k1 for another. However in python we need to spend some effort to get AC:

  1. Use a bit of pruning, consider only range k1 <= (k+1)//2.
  2. Use table dp for faster access.

Complexity

It is O(mn(m+n)*k^2) for time and O(mnk) for space.

Code

from collections import defaultdict
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

dp = [[[0 for k in range(51)] for j in range(31)] for i in range(31)]

def dfs(n, m, k):
    if dp[n][m][k] != 0 or k == 0 or k == n * m: return dp[n][m][k]
    ans = float("inf")
    for k1 in range((k + 1)//2):
        for m1 in range(1, m):
            ans = min(ans, dfs(n, m1, k1) + dfs(n, m - m1, k - k1) + n * n)
        for n1 in range(1, n):
            ans = min(ans, dfs(n1, m, k1) + dfs(n - n1, m, k - k1) + m * m)

    dp[n][m][k] = ans
    return ans

out = []
t = int(input())
for _ in range(t):
    n, m, k = [int(i) for i in input().split()]
    out += [dfs(n, m, k)]

sys.stdout.write(" ".join(map(str, out)) + "\n")

Problem F statement

[geometry, math, sort, line sweep]

https://codeforces.com/contest/598/problem/F

Solution

Let us first solve the case when given line have equation y = 0. Then what we need to do is to traverse points of our polygon one by one and check cases: if it lies above, we say that its characteristic is equal 1, if it lies on line, it is 0 and -1 in the opposite case. We have intersection with line y = 0 if we have different characteristics. What to do if we have another line? We just rotate everything in our plane, so line becomes equal to y = 0. Also when we rotate, we multiply all points by (p0*p0 + p1*p1)**0.5, so we work with good precision (if we multiply all points by 100, then we will have integer coordinates). Then we sort intersectoin points and do cumulative sum trick: contidion if t means that t != 0 and it means that

Complexity

It is O(n m log n) for time, because of sort and O(m + n) for space.

Code

I = lambda: [float(x) for x in input().split()]
n, m = [int(i) for i in input().split()]
V = [I() for _ in range(n)]
cmp = lambda x: (x >= 0) - (x <= 0)

for _ in range(m):
    x0, y0, x1, y1 = I()
    p0, p1 = x1 - x0, y1 - y0
    V3 = [((x - x0) * p0 + (y - y0) * p1, (y - y0) * p0 - (x - x0) * p1) for x, y in V]
    res = []

    for (v1x, v1y), (v2x, v2y) in zip(V3, V3[1:] + V3[:1]):
        if cmp(v1y) != cmp(v2y):
            res.append(((v2x * v1y - v1x * v2y) / (v1y - v2y), cmp(v2y) - cmp(v1y)))

    res.sort()

    t, w = 0, 0.
    for i in range(1, len(res)):
        t += res[i - 1][1]
        if t: w += res[i][0] - res[i-1][0]

    print(w / (p0 * p0 + p1 * p1) ** 0.5)