Problem A statement

[simulation]

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

Solution

Just simulate process carefully, we have several options here.

Complexity

Time complexity is O(h), it can be made O(1) with direct formulaes.

Code

I = lambda: [int(i) for i in input().split()]
h1, h2 = I()
a, b = I()

if h1 + 8 * a >= h2:
    print(0)
else:
    if b >= a:
        print(-1)
    else:
        h1 += (8 * a - 12 * b)
        i = 0
        while True:
            if i % 2 == 0:
                h1 += 12 * a
            else:
                h1 -= 12 * b
            if h1 >= h2:
                print(i//2 + 1)
                break
            i += 1

Problem B statement

[sort]

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

Solution

We can just sort and then put big elements on odd places and small on even places. Or we can do it in O(n) with one path.

Complexity

Code

I = lambda: [int(i) for i in input().split()]

n = int(input())
nums = I()
nums[:2] = sorted(nums[:2])
for i in range(1, n - 1):
    nums[i:i+2] = sorted(nums[i:i+2])[::(1-2*(i%2))]

print(" ".join(str(x) for x in nums))

Problem C statement

[greedy, accumulate]

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

Solution

The idea is the following: for every left end x find the smallest right end y, such that (x, y) are enemies. Then we go from the end and calculate cumulative minimums.

Complexity

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

Code

I = lambda: [int(i) for i in input().split()]
import sys
input = sys.stdin.readline

n, m = I()
arr = I()
P = {x - 1: i for i, x in enumerate(arr)}
ends = [n + 1]*n

for x in range(m):
    a, b = I()
    ap, bp = P[a-1], P[b-1]
    ap, bp = min(ap, bp), max(ap, bp)
    ends[ap] = min(bp + 1, ends[ap])

for x in range(n - 2, -1, -1):
    ends[x] = min(ends[x], ends[x + 1])

print(sum([ends[x] - x - 1 for x in range(n)]))

Problem D statement

[segment tree, binary indexed tree, sort]

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

Solution

One way to solve this problem is to use segment trees. First of all, let us create array in the form 4 3 3 1 2 1 2 4, where we have 1, ..., n repeated twice. Then the idea is the following: go from the left to the right and

  1. if we meet start of segment, save it
  2. if we meet end of segment, set start of this segment as 1 and calculate number of ones inside.

Complexity

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

Code

class SegmentTree:
    def __init__(self, n):
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.T = [0] * (2 * self.size - 1)
 
    def _set(self, i, v, x, lx, rx):
        if rx - lx == 1:
            self.T[x] = v
            return
        mx = (lx + rx) // 2
        if i < mx:
            self._set(i, v, 2 * x + 1, lx, mx)
        else:
            self._set(i, v, 2 * x + 2, mx, rx)
        self.T[x] = self.T[2 * x + 1] + self.T[2 * x + 2]
 
    def set(self, i, v):
        self._set(i, v, 0, 0, self.size)
 
    def _sum(self, l, r, x, lx, rx):
        if l >= rx or lx >= r:
            return 0
        if lx >= l and rx <= r:
            return self.T[x]
        mx = (lx + rx) // 2
        s1 = self._sum(l, r, 2 * x + 1, lx, mx)
        s2 = self._sum(l, r, 2 * x + 2, mx, rx)
        return s1 + s2
 
    def sum(self, l, r):
        return self._sum(l, r, 0, 0, self.size)
 
import io, os, sys
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
 
P = []
back = {}
n = int(input())
for i in range(n):
    x, y = [int(t) for t in input().split()]
    P += [x, y]
    back[x] = i
    back[y] = i
    
 
arr = [back[i] + 1 for i in sorted(P)]
 
ans = [0]*n
d = {}
STree = SegmentTree(2*n)
for i, num in enumerate(arr):
    if num not in d:
        d[num] = i
    else:
        start = d[num]
        ans[num-1] = STree.sum(start+1, i)
        STree.set(start, 1)
 
print(" ".join(str(x) for x in ans))

Problem E statement

[graph, graph algo, dfs]

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

Solution

Solution can be separated into 3 parts:

  1. Find all bridges in our graph, using Tarjan algorithm with dfs.
  2. Find any simple path from Pavel to trader, using simple dfs.
  3. Now, delete all bridges from our set of bridges, which we have in our path from Pavel to trader, call the set cleaned bridges. Create new graph, where we deleted all cleaned bridges. Then run dfs once again and check what edges can be reached in new graph: if any of these edges have artefact, return True, in the opposite case return False.

Complexity

It is (V + E), because we traverse our graph 3 times. May be we can decrease number of traversal, but it is fast enough to get AC. Also we need bootstrap for recursion to make it faster (or rewrite recursive dfs to iterative, which takes more time).

Code

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

n, m = I()
edges = {}
for _ in range(m):
    x, y, w = I()
    G[x-1] += [(y-1, w)]
    G[y-1] += [(x-1, w)]
    edges[x-1, y-1] = w

### IMPORT BOOTSTRAP FOR RECURSION

#### part 1: bridges
used, tin, fup = [0] * n, [-1] * n, [-1] * n
timer, br = [0], set()

@bootstrap
def dfs0(node, par=-1):
    used[node] = 1
    tin[node] = fup[node] = timer[0] + 1
    timer[0] += 1
    for child, _ in G[node]:
        if child == par: continue
        if used[child] == 1:
            fup[node] = min(fup[node], tin[child])
        else:
            yield dfs0(child, node)
            fup[node] = min(fup[node], fup[child])
            if fup[child] > tin[node]: br.add((node, child))
    yield

for i in range(n):
    if not used[i]: dfs0(i)

#### part 2: path from pavel to trader

V, par = set(), {}

@bootstrap
def dfs(node):
    V.add(node)
    for child, _ in G[node]:
        if child in V: continue
        par[child] = node
        yield dfs(child)
    yield

a, b = I()
dfs(a - 1)

path, last = [b - 1], b - 1
while last != a - 1:
    last = par[last]
    path += [last]

### part 3: new graph and dfs again

for x, y in zip(path, path[1:]):
    br.discard((x, y))
    br.discard((y, x))

G2 = defaultdict(list)
for x, y in edges:
    w = edges[x, y]
    if (x, y) in br or (y, x) in br: continue
    G2[x] += [(y, w)]
    G2[y] += [(x, w)]

ans = [False]

V2 = set()
@bootstrap
def dfs2(node):
    V2.add(node)
    for child, w in G2[node]:
        if w == 1: ans[0] = True
        if child in V2: continue
        yield dfs2(child)
    yield

dfs2(a - 1)
print("YES" if ans[0] else "NO")

Problem F statement

[math, sort]

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

Solution

The are two obsevations:

  1. We can assume that ants go through one another, then we can calculate positions of all antes, however we do not know which one is which.
  2. Relative positions of ants will not change. However we still have n possible options how ants can arrive.

  3. One way to understand the final order is to track for example 0-th ant. However we can evaluate shift with direct formula: for each ant we evaluate w = divmod(a[i] + t * dr, m) is number of full rotates it will make if it go through all other ants. It happen that shift is number of full rotates for all ants.

  4. Let sorted starting positions be p_1, ..., p_n.
  5. We can calculate final positions. Let them be q_1, ..., q_n (also sorted).
  6. Let’s calculate total (oriented) speed S of ants. It’s some number in [-n, n]. After multiplying it by t we will have total (oriented) movement.
  7. Let’s calculate offset O between starting and final position (q_1 - p_1) + ... + (q_n - p_n).
  8. Proposal: (S * t - O) is divisible by m. To prove it w eneed to recall how q_i was calculated.
  9. Let offset (S * t - O) / m. Then ant that was on p_1 position on start will be on position q_(1 + offset) on finish.

Complexity

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

Code

import sys
input = sys.stdin.readline
 
n, m, t = [int(i) for i in input().split()]
a, b, ans, cnt = [0]*n, [0]*n, [0]*n, 0
 
for i in range(n):
    x, ch = input().split()
    a[i] = int(x) - 1
    b[i] = (a[i], i)
    dr = 1 if ch == "R" else -1
    w, u = divmod(a[i] + t * dr, m)
    a[i], cnt = u, cnt + w
 
a, b = sorted(a), sorted(b)
for i in range(n):
    ans[b[i][1]] = a[(i + cnt) % n]+1
 
print(" ".join(str(x) for x in ans))