Problem A statement

[string, parser]

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

Solution

Just use python functionality to split string and then check if each part is integer.

Complexity

It is O(n) for time and space.

Code

s = input().rstrip()
 
parts = s.replace(";", ",").split(",")
a, b = [], []
for part in parts:
    if part.isdigit() and str(int(part)) == part:
        a += [part]
    else:
        b += [part]
 
print(",".join(a) if a else "-")
print(",".join(b) if b else "-")

Problem B statement

[binary search, two pointers]

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

Solution

First, sort array A, then for each element of element B use binary search. Another way is to use two pointers where we sort B as well.

Complexity

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

Code

from bisect import bisect
I = lambda: [int(x) for x in input().split()]

m, n = I()
A = sorted(I())
B = I()
ans = [bisect(A, b) for b in B]
print(" ".join(map(str, ans)) + "\n")

Problem C statement

[counter, string, palindrome]

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

Solution

First, we need to found all letters with odd frequency.

  1. If we have 0 of them, then we need to make 0 changes.
  2. If we have 1 of them, we need to make 0 changes.
  3. If we have 2 of them, say a and b, we need to make 1 changes to make it aa.
  4. If we have 3 of them, say a, b and c, we need to make 1 changes to make it aba.
  5. If we have 4 of them, say a, b, c, d, we need to make 2 changes to make it abba. Also if we have say 5 elements of a, we put aa` to even part. In the end we sort even part and deal with middle element.

Complexity

Time complexity is O(n log n), space complexity is O(n).

Code

from collections import Counter
 
s = input().rstrip()
cnt = Counter(s)
odd = []
even = []
for x in cnt:
    if cnt[x] % 2 == 1:
        odd += [x]
    even += [x] * (cnt[x]//2)
 
odd = sorted(odd)
mid = "" if len(odd) % 2 == 0 else odd[len(odd)//2]
for x in odd[:len(odd)//2]:
    even += x
 
half = "".join(sorted(even))
print(half + mid + half[::-1])

Problem D statement

[geometry, math]

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

Solution

All we need to do is bunch of formulae. However in python precision is not enough and one way to handle it is to use libarary Decimal to make better precision.

Complexity

It is O(1) if other languates, in python it depends on approximation

Code

from math import acos, pi, sin, cos, sqrt
I = lambda: [Decimal(int(x)) for x in input().split()]
from decimal import *

getcontext().prec = 100
eps = 2e-7

def _acos(x):
    if 1 - eps > abs(x) > eps:
        return Decimal(acos(x))
    if x < 0:
        return pi - _acos(-x)
    if abs(x) < eps:
        return Decimal(pi) / 2 - x - x ** 3 / 6 - x ** 5 * 3 / 40 - x ** 7 * 5 / 112
    else:
        t = Decimal(1) - x
        return (2 * t).sqrt() * (
                1 + t / 12 + t ** 2 * 3 / 160 + t ** 3 * 5 / 896 + t ** 4 * 35 / 18432 + t ** 5 * 63 / 90112)

x1, y1, r1 = I()
x2, y2, r2 = I()
x = ((x1 - x2)*(x1-x2) + (y1 - y2)*(y1-y2)).sqrt()

if r1 + r2 <= x:
    print(0)
elif r1 + x <= r2:
    print(r1 * r1 * Decimal(pi))
elif r2 + x <= r1:
    print(r2 * r2 * Decimal(pi))
else:
    c1 = (r2 * r2 + x * x - r1 * r1) / (2 * x * r2)
    c2 = (r1 * r1 + x * x - r2 * r2) / (2 * x * r1)
    print(r2 * r2 * (_acos(c1) - c1*(1-c1*c1).sqrt()) + r1 * r1 * (_acos(c2) - c2*(1-c2*c2).sqrt()))

Problem E statement

[graph, tree]

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

Solution

See Binarysearch 0507 problem, it uses the similar idea. We need to travese our tree with dfs and keep some data in each node about its subtree. When we merge two nodes, we always do it small to larger. What we keep in each node:

  1. c_t is Counter for each color.
  2. t_c is defaultdict, where for each frequency we keep set of nodes.
  3. ans is answer for this node, that is sum of all colors with the highest frequency.
  4. mx is the maximum frequency.

Then we add new color to our structure, we can do it just in O(1) time! We check how may nodes with color c we already have and update c_t and t_c. Also if new frequency is bigger than current one, we set ans = c. If it is the same, we update ans += c.

Also we need to use booster for dfs to get AC.

Complexity

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

Code

from collections import defaultdict, Counter
I = lambda: [int(x) for x in input().split()]
import io, os, sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

#### IMPORT BOOTSTRAP FOR RECURSION FROM TEMPLATES

class Node:
    def __init__(self, c):
        self.ans, self.mx = c, 1
        self.c_t = Counter([c])
        self.t_c = defaultdict(set)
        self.t_c[1] = {c}

    def merge(self, other):
        for c, t in other.c_t.items():
            self.add(c, t)

    def add(self, c, t):
        old_t = self.c_t[c]
        self.c_t[c] = new_t = old_t + t
        self.t_c[old_t].discard(c)
        self.t_c[new_t].add(c)
        if new_t == self.mx:
            self.ans += c
        elif new_t > self.mx:
            self.mx = new_t
            self.ans = c

    def __len__(self):
        return len(self.c_t)

    def __repr__(self):
        return str(self.ans)

@bootstrap
def dfs(par, node):
    c = color[node]
    ans_n = Node(c)

    for child in G[node]:
        if child == par: continue
        ans_c = yield dfs(node, child)
        if len(ans_n) < len(ans_c):
            ans_n, ans_c = ans_c, ans_n
        ans_n.merge(ans_c)
    out[node] = ans_n.ans
    yield ans_n

n = int(input())
color = I()
G = defaultdict(list)
out = [0]*n
for _ in range(n-1):
    a, b = I()
    G[a-1] += [b-1]
    G[b-1] += [a-1]

dfs(-1, 0)
sys.stdout.write(" ".join(map(str, out)) + "\n")

Remark

Notice, that what we can keep instead of t_c is sorted list of pairs (frequency, color), but then we will have O(n log^2) complexity, which is too big for python.

Problem F statement

[graph, graph algo, dfs, greedy]

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

Solution

What is asked in this problem is called chromatic number of graph. It can be proven that chromatic number of bipartite graph is equal to the biggest degree. However we also need to construct coloring as well. There are different time complexities algorithms and problem constraints allow ust to use quite simple one. The idea is to try to color edges if we can. If we not able to color some edge, it means that for current edge ab we have colors x and y, such that we have x in a but not in b and we have y in b but not in a. If x == y, it means that we can draw edge without conflicts. If x != y, it means that we have conflicts and we need to recolor some edges. Because of bipartite property we always can do it no more than in O(n) steps: we will look for the chain where colors of edges are change: x, y, x, y, ... and we never have conflicts and in one moment nodes will end.

Complexity

Time complexity is O(mn), space is O(n^2).

Code

import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
 
I = lambda: [int(x) for x in input().split()]
 
def dfs(x, y, z):
    if not x: return
    p[x][y], p[x][z] = p[x][z], p[x][y]
    dfs(p[x][z], z, y)
 
a, b, m = I()
d = [0]*(a+b+1)
u = [0]*(m+1)
v = [0]*(m+1)
 
for i in range(1, m + 1):
    x, y = I()
    u[i], v[i] = x, y + a
    d[v[i]] += 1; d[u[i]] += 1
 
s, ans = max(d), []
p = [[1] + [0]*s for _ in range(a+b+1)]
 
for i in range(1, m+1):
    x = p[u[i]].index(0)
    y = p[v[i]].index(0)
    p[u[i]][x], p[v[i]][y] = v[i], u[i]
    if x != y: dfs(v[i], x, y)
 
for i in range(1, m+1):
    for j in range(1, s+1):
        if p[u[i]][j] == v[i]:
            ans += [j]
            break
 
sys.stdout.write(str(s) + "\n" + " ".join(map(str, ans)) + "\n")

Remark

There are better time complexity algorithm, see wikipedia for names.