Problem A statement

[math, string]

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

Solution

Problem constraints allow us to use almost bruteforce. We need to solve in integer number equation p*x + q*y = n for given p, q, n. After we solve, carefully cut string into parts.

Complexity

It is O(n), because we need to cut our string in any case.

Code

n, p, q = [int(i) for i in input().split()]
s = input().rstrip()

def solve(s, p, q, n):
    for x in range(100):
        if n - p*x >= 0 and (n - p*x) % q == 0:
            y = (n - p*x)//q
            part1 = [s[i*p:i*p+p] for i in range(x)]
            part2 = [s[p*x + i*q: p*x + i*q + q] for i in range(y)]
            return part1 + part2
    return ["-1"]

ans = solve(s, p, q, n)
if ans[0][0] == "-":
    print(-1)
else:
    print(len(ans))
    for q in ans: print(q)

Problem B statement

[permutation, hash table]

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

Solution

All we need to do given original string reconstruct correct order, using dictionary. It is even simpler than problem A.

Complexity

Time complexity is O(n) as well as space complexity.

Code

n = int(input())
arr = [int(i) for i in input().split()]
d = {x: i for i, x in enumerate(arr)}
print(sum(abs(d[i+1]-d[i]) for i in range(1, n)))

Problem C statement

[stack, brackets]

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

Solution

It is almost classical stack problem, each time we have closing bracket, replace it with what we have in the top of our stack. Also deal with impossibility case as we do in classical brackets problem.

Complexity

It is O(n) for time and space.

Code

s = [i for i in input().rstrip()]
d = {"{": "}", "[": "]", "<": ">", "(": ")"}
 
def solve(s):
    ans, stack = 0, []
    for x in s:
        if x in d:
            stack += [x]
        else:
            if not stack or stack[-1] not in d: return "Impossible"
            if d[stack[-1]] != x:
                ans += 1
            stack.pop()
    return ans if not stack else "Impossible"
 
print(solve(s))

Problem D statement

[intervals, sort]

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

Solution

Here we use classical idea for intervals: we have two events: start of interval and end of interval. Then we sort these events and go from left to righ, each time checking taken is counter of how many intervals we have at the moment. However in python we need to use trick to get AC: instead of keeping pairs (start, -1) and (end, 1) we keep only numbers 2*start and 2*end + 1. It allows python to make faster sort.

Complexity

It is O(n log n).

Code

import sys
input = sys.stdin.buffer.readline

I = lambda: map(int, input().split())
n, k = I()
points = []
for _ in range(n):
    x, y = I()
    points += [2*x]
    points += [2*y+1]

taken = 0
ans = []

for x in sorted(points):
    event = -1 if x % 2 == 0 else 1
    if taken - event >= k and taken < k:
        start = x//2
    if taken == k and taken - event < k:
        ans += [str(start) + " " + str(x//2)]
    taken -= event

sys.stdout.buffer.write(
    (str(len(ans)) + '\n' + '\n'.join(ans)).encode('utf-8'))

Problem E statement

[permutation, dfs, combinatorics]

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

Solution

Let us look at loops representation of our permutation. It happens that if we have odd cycle of length x in p, then we have again cycle of length x in p^2. If we have even cycle of length x, then we will have cycles of length x//2, x//2 in p^2. This solves our problem: what we do:

  1. Create loop representation of or permutation.
  2. Check for each loop length how many loops with this length we have. If we have odd length, we are allowed to have as many as we want. From each of them we can reconstruct original loop. See 12345 -> 13524, so we put elements 135 on the odd indexes and the rest on even. If we have even length of loop, we only allowed to have even number of such loops. Then we combine each pair of them to one big loop.

Complexity

Time and space complexity is O(n). I think function perm_loop can be written with simple dfs which will make code shorter.

Code

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

def perm_loops(x, n): # from permutation create loops, permutation eg [1, 0, 4, 2, 3]
    V, ans = set(), []
    for i in range(n):
        if i in V: continue
        q = i
        ans += [[q]]
        V.add(i)
        while x[q] != i:
            ans[-1] += [x[q]]
            q = x[q]
            V.add(q)
    return ans

def loops_perm(loops, n):  # from loops create permutation
    ans = [0] * n
    for loop in loops:
        for x, y in zip(loop, loop[1:] + loop[:1]):
            ans[x] = y
    return ans

n = int(input())
arr = [int(i) - 1 for i in input().split()]
d_loops = defaultdict(list)

loops = perm_loops(arr, n)
for loop in loops:
    d_loops[len(loop)] += [tuple(loop)]

def solve(d_loops):
    ans = []
    for d in d_loops:
        if d % 2 == 1:
            for loop in d_loops[d]:
                tmp = [0]*d
                tmp[::2] = loop[:d//2+1]
                tmp[1::2] = loop[d//2+1:]
                ans += [tmp]
        else:
            if len(d_loops[d]) % 2 == 1:
                return []
            else:
                for i in range(len(d_loops[d])//2):
                    tmp = [0]*(2*d)
                    tmp[::2] = d_loops[d][2*i]
                    tmp[1::2] = d_loops[d][2*i+1]
                    ans += [tmp]
    return ans

ans = solve(d_loops)
if ans == []:
    print(-1)
else:
    out = loops_perm(ans, n)
    print(" ".join(str(i+1) for i in out))

Problem F statement

[dp, sort]

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

Solution

Notice, that we need to traverse numbers layer by layer, where by layer I mean equal numbers. Imagine, that we have two layers: x1 x2 ... xk

y1 y2 ... yl.

Then how we can reach number yi? It can be from any number xj, we have two options:

  1. Go xi -> y_{j-1} and then traverse all numbers in layer y by clockwise direction. Then what we keep in dp[yj] state is minimum cost to reach index yj and also we visited all numbers with the same value.
  2. Go xi -> y_{j-1} and then traverse all numbers in leyar y in counterclockwize direction.
  3. Also it can happen that there is only one number in y layer, in this case no need to traverse it.

So, finally, what we keep in dp[p]: It is 3 values: cost to reach this cell, such that we already visited all elements with the same value, second value is from where we go from previous layer and finally direction, it can be -1, 0, 1.

Also after we did dp, we need to restore answer. We look at last element and go back layer by layer. That is we first travere all layer and then go to element of previous layer.

Complexity

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

Code

from collections import defaultdict
I = lambda: list(map(int, input().split()))
n, s = I()
arr = I()
d, INF = defaultdict(list), -float("inf")
dp = [(float("inf"), 0, 0)] * n
for i, x in enumerate(arr): d[x] += [i]

keys = sorted(d.keys())
dist = lambda x, y: min(abs(x - y), n - abs(x - y))

for dx, dy in zip([INF] + keys, keys):
    lx = [s - 1] if dx == -float("inf") else d[dx]
    ly = d[dy]
    for x in lx:
        addon = dp[x][0] if dx != INF else 0
        if len(ly) > 1:
            for dr in (-1, 1):
                for y1, y2 in zip(*[ly, ly[1:] + ly[:1]][::dr]):
                    dp[y1] = min(dp[y1], (addon + dist(x, y2) + ((y1 - y2)*dr) % n, x, dr))
        else:
            y = ly[0]
            dp[y] = min(dp[y], (addon + dist(x, y), x, 0))

t = len(keys) - 1
val = min(dp[i] for i in range(n) if arr[i] == keys[t])
last = dp.index(val)
path = [last]

while t >= 0:
    _, prev, dr = dp[last]
    lvl = d[keys[t]]
    m = len(lvl)
    idx = lvl.index(last)
    for i in range(1, len(lvl)):
        path += [lvl[(idx - i * dr) % m]]
    path += [prev]
    last = prev
    t -= 1

path = path[::-1]

print(val[0])
for x, y in zip(path, path[1:]):
    c1 = (y - x) % n
    x = min((c1, "+"), (n - c1, "-"))
    print(x[1] + str(x[0]))