It is easy to see that there is no way for even valued chips to move to odd positions without paying, and vice versa. Let's say there are E even valued chips and O odd valued chips. The answer is min(E, O).

def solve(N, A):
    count = [0, 0]
    for x in A:
        count[x & 1] += 1
    return min(count)

Since we want to know the minimum price in the future, lets iterate in reverse and keep track of it. When we are considering the i-th price, we already know the minimum price we saw.

def solve(N, A):
    ans = 0
    low = float('inf')
    for x in reversed(A):
        if x > low:
            ans += 1
        low = min(low, x)
    return ans

We write K = floor(N / M) numbers, the numbers are f(k) = k * M % 10 for k = 1, 2, ..., K. These numbers f(k) must repeat every 10 instances of k, that is f(k) = f(k+10). Let k = 10 * q + r. We write q numbers of f(0), f(1), ..., f(9); plus another r numbers f(1), f(2), ..., f(r).

def solve(N, M):
    K = N // M
    q, r = divmod(K, 10)
    ans = q * sum(k * M % 10 for k in range(10))
    ans += sum(k * M % 10 for k in range(1, r+1))
    return ans

For each number i in reverse order, lets see if all numbers could equal i. To do this, we maintain at each number, an int[] count[i] of how many numbers reached here by 0, 1, 2, ..., 18 divisions of 2. Then, for a number i with some count, we can calculate if K numbers could equal i in a greedy way: count[0] of them got here in 0 divisions, count[1] of them got here in 1 division, etc. and see how many divisions we need to find K numbers.

Afterwards, we divide the number i by 2, which increases the counts at count[i//2] appropriately.

LOGV = 19
MAXV = 200000
def solve(N, K, A):
    count = [[0] * LOGV for _ in xrange(MAXV + 1)]
    for x in A:
        count[x][0] += 1

    ans = float('inf')
    for i in xrange(MAXV, 0, -1):
        bns = 0
        todo = K
        for j, x in enumerate(count[i]):
            delta = min(todo, x)
            todo -= delta
            bns += delta * j

        if todo == 0 and bns < ans:
            ans = bns

        for j in xrange(LOGV - 1):
            count[i // 2][j + 1] += count[i][j]

    return ans

Its always possible. Consider the graph with nodes 'a', 'b', 'c' and all possible directed edges (even self edges). There are three types of edges: forward edges 'ab', 'bc', 'ca'; backward edges 'ba', 'cb', 'ac'; and repeat edges 'aa', 'bb', 'cc'. Our goal is to walk around this graph without touching the banned edges S or T.

Evidently, if we don't ban forward edges, we will answer 'abc' * N. If we don't ban backwards edges, we will say 'cba' * N. So lets say we ban a forward edge and a backwards edge. Without loss of generality, we could say the forward edge banned is 'ab'. Then the backwards edge is 'ba' or 'cb' or 'ac', and we have an answer 'b' * N + 'c' * N + 'a' * N.

from itertools import permutations

def solve(N, S, T):
    def check(cand):
        return S not in cand and T not in cand

    if check('abcabc'):
        return 'abc' * N
    if check('cbacba'):
        return 'abc' * N
    if check('bbccaa'):
        return 'b'*N + 'c'*N + 'a'*N
    if check('ccaabb'):
        return 'c'*N + 'a'*N + 'b'*N
    if check('aabbcc'):
        return 'a'*N + 'b'*N + 'c'*N

We have 2N — 2 inequalities S[P_i] <= S[P_{i+1}] and S[Q_i] <= S[Q_{i+1}]. For each inequality S[u] <= S[v], draw a directed edge from u to v. Notice if a path exists from u to v, it implies S[u] <= S[v] by transitivity. If a path exists from u to v and from v to u (ie., u and v are in the same strongly connected component), then S[u] <= S[v] and S[u] >= S[v], so the letters S[u] and S[v] must be equal.

We can use Kosaraju's algorithm to find the strongly connected components. If there are less than K strongly connected components, the task is impossible. Otherwise, we could greedily fill the answer.

def solve(N, K, P, Q):
    P = [x - 1 for x in P]
    Q = [x - 1 for x in Q]

    graph = collections.defaultdict(list)
    rgraph = collections.defaultdict(list)

    for i in xrange(N - 1):
        graph[P[i]].append(P[i+1])
        rgraph[P[i+1]].append(P[i])
        graph[Q[i]].append(Q[i+1])
        rgraph[Q[i+1]].append(Q[i])
    
    # first dfs of kosaraju's
    seen = [False] * N
    visited = []
    ENTER, EXIT = 0, 1

    for start in xrange(N):
        if not seen[start]:
            stack = [(start, EXIT), (start, ENTER)]
            while stack:
                node, cmd = stack.pop()
                if cmd == VISIT:
                    if not seen[node]:
                        seen[node] = True
                        for nei in graph[node]:
                            stack.append((nei, EXIT))
                            stack.append((nei, ENTER))
                else:
                    visited.append(node)

    # second dfs of kosaraju's
    component = [None] * N
    for start in reversed(visited):
        if component[start] is None:
            stack = [(start, start)]
            while stack:
                node, root = stack.pop()
                if component[node] is None:
                    component[node] = root
                    for nei in rgraph[node]:
                        stack.append((nei, root))
    
    color = 0
    ans = [None] * N
    for i in xrange(N - 1):
        x, y = P[i], P[i+1]
        if i == 0:
            ans[x] = color
            color += 1
        if component[x] == component[y]:
            ans[y] = ans[x]
        else:
            ans[y] = color
            color = min(color + 1, 25)

    return "".join(chr(x + ord('a')) for x in ans)

If S[u] <= S[v], draw a directed edge from u to v.

If x occurs before y in P, and x occurs after y in Q, then a path exists from both x to y and y to x, ie. x and y are in the same strongly connected component, so S[x] == S[y].

We can use the above fact to deduce when there may still be P[j] with j > i such that S[P[i]] == S[P[j]].

def solve(N, K, P, Q):
    Qindex = {v: i for i, v in enumerate(Q)}
    far = -1
    ans = [None] * N
    cur = 0
    for i, p in enumerate(P):
        far = max(far, Qindex[p])
        ans[p - 1] = cur
        if far == i:
            cur = min(25, cur + 1)

    if cur < K:
        return False
    return "".join(chr(x + ord('a')) for x in ans)

Sort the queries. Every time q increases, we can only add edges to the graph under consideration. Therefore, we only need to maintain the correct answer every time we add an edge to the graph.

Lets say the graph is a set of disjoint connected components, each component having s_i nodes (s for size). Then, the answer is sum_i (s_i choose 2), which we can write as (1/2)(sum_i (s_i)^2 — sum_i s_i) = (sum_i (s_i)^2 — N)/2. Thus, it is only necessary to maintain S_2 = sum_i (s_i)^2.

Whenever we add an edge, if it connects two disjoint components with sizes sx and sy, then S_2 gets increased by (sx + sy)^2 — sx^2 — sy^2 = 2 * sx * sy.

def solve(N, M, edges, queries):
    # edges are u, v, w with 0 <= u, v < N
    parent = range(N)
    size = [1] * N
    rank = [1] * N
    S2 = [N]

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        xr, yr = find(x), find(y)
        if xr == yr: return
        parent[yr] = xr
        if rank[xr] < rank[yr]:
            xr, yr = yr, xr
        if rank[xr] == rank[yr]:
            rank[xr] += 1
        sx, sy = size[xr], size[yr]
        size[xr] += sy
        S2[0] += 2 * sx * sy

    queries = sorted((q, i) for i, q in enumerate(queries))
    edges.sort(key = lambda e: e[2])
    i = 0
    ans = [None] * M

    for q, qi in queries:
        while i < len(edges) and edges[i][2] <= q:
            union(edges[i][0], edges[i][1])
            i += 1
        ans[qi] = (S2[0] - N) / 2
    return ans