June 14, 2018 2018 TCO Algorithm Round 2B Editorials

This is the second and last opportunity for competitors to earn a chance to advance to round 3 and win a T-shirt.
The writer of the problems and editorial of this round is [lg5293]

SubarrayAverages

In this problem, we are given an array, and we can replace any subarray with the average of the subarray values. We can do this operation arbitrarily many times, and want the final array to be as lexicographically small as possible.
A common way to start a problem that asks for lexicographically smallest is to minimize the first element, then minimize the second element, and so on…
So, let’s see if we can first solve the problem of trying to minimize the first element.
To do this, we will show that it is optimal to do an operation on a prefix of the array once.
Of course, if there is a sequence of operations, only the last one that touches the first element matters, so we can assume the last operation is a prefix of the array.
Also, if there is more than one operation, we can assume the second to last operation intersects with the last operation, and doesn’t touch the first element (otherwise, we could just ignore that second to last operation)
So, the final two steps looks like choosing subarray [a,b], then choosing the subarray [0,c], with 0 < a <= c. In addition, we can also assume c < b, otherwise, we can ignore the operation [a,b].
If this was optimal, we can show that replacing these two operations with [0,b] is a better choice.
This is true since all elements in [a,b] are now the same, so if including the elements [a,c] in our prefix [0,c] is good, then, it wouldn’t hurt to also include the elements [c+1,b] as well in our prefix.
Thus, we’ve shown that we can minimize the first element just by finding the best prefix.
We can then do this approach for each element in sequence in the array, leading to an O(n^2) algorithm.
Java code below:

import java.util.Arrays;
public class SubarrayAverages {
    public double[] findBest(int[] arr) {
        int start = 0;
        double[] ret = new double[arr.length];
        while (start < arr.length) {
            long a1 = arr[start], a2 = 1;
            long s1 = 0, s2 = 0;
            int id = start;
            for (int j = start; j < arr.length; j++) {
                s2++;
                s1 += arr[j];
                if (s1 * a2 < a1 * s2) {
                    a1 = s1;
                    a2 = s2;
                    id = j;
                }
            }
            for (int k = start; k <= id; k++) {
                ret[k] = a1 / (double)a2;
            }
            start = id+1;
        }
        return ret;
    }
}

LineColoring

In this problem, we have to color our a row of houses such that no two adjacent houses have the same color, and the cost of the coloring is minimized. Here, the cost of the coloring is equal to the sum of the maximum value of a house of each color used.
This problem suggests a dp approach, but there is seemingly no limit on the number of colors we can use. In addition, we also need to keep track of the maxima of each color, which could potentially be very intractable easily.
First, a key observation is that we never require more than three colors. This is true since each house is neighbors with at most two other houses, so we can only ever be locked out from using at most two different colors, so three colors is sufficient.
Next, another observation is that the maximum value house must have some color, so without loss of generality, let it be color 0.
Now, we can fix the maximum value that color 1 will get, and we can do dp to get the minimum maximum value for color 2. Each dp takes O(n) time, and there are O(n) values of the max value that color 1 will get, so the overall runtime is O(n^2)
Be careful with the case of only 1 house! (luckily, there is a sample for it)
Code in java:

import java.util.Arrays;
public class LineColoring {
    public int minCost(int[] x) {
        if (x.length == 1) return x[0];
        int max = 0;
        for (int y : x) max = Math.max(y, max);
        int min = 1 << 25;
        for (int second_max : x) {
            int[] dp = new int[3];
            for (int i = 0; i < x.length; i++) {
                int[] ndp = new int[3];
                Arrays.fill(ndp, 1 << 25);
                for (int prev = 0; prev < 3; prev++) {
                    if (x[i] <= max && prev != 0) {
                        ndp[0] = Math.min(ndp[0], dp[prev]);
                    }
                    if (x[i] <= second_max && prev != 1) {
                        ndp[1] = Math.min(ndp[1], dp[prev]);
                    }
                    if (prev != 2) {
                        ndp[2] = Math.min(ndp[2], dp[prev]);
                    }
                }
                ndp[2] = Math.max(ndp[2], x[i]);
                dp = ndp;
            }
            for (int w : dp) min = Math.min(min, w + second_max);
        }
        return min + max;
    }
}

SquareFreeSet

In this problem, we are given a set of numbers, and we want to make this set square-free, that is, no two elements in this set have a product that is a perfect square.
First, two numbers x*y form a perfect square if there is an even number of each prime factor. Thus, for each number, it suffices to only know the parity of each prime factor.
Let f(x) be product of all prime factors of x that appear an odd number of times. Another equivalent definition is that f(x) is the minimum number such that x/f(x) is a perfect square.
We can show two numbers x,y form a perfect square if and only if f(x) = f(y).
Thus, this problem reduces to give a set of numbers, make all of their f values distinct.
This reduces to a minimum cost maximum matching problem on a bipartite graph, which can then be solved with min cost max flow. The number of nodes we may need to add may seem large at first, but we can notice we only care about the closest n+1 distinct values of f(x) from x, so this can help us limit the number of nodes.
There are n nodes on the left, and at most n^2 nodes on the right with n^2 total edges, and the runtime of mincost maxflow is about O(n^3 * log n) (for example, using this implementation: https://sites.google.com/site/indy256/algo/min_cost_flow_pot). You can see a tutorial for mincost maxflow here: https://www.topcoder.com/community/data-science/data-science-tutorials/minimum-cost-flow-part-one-key-concepts/
Java code below:

import java.util.*;
public class SquareFreeSet {
    public HashMap<Integer, Integer> id;
    public int idx;
    public int[] f;
    public boolean insert(int q) {
        if (q <= 0) return false;
        q = f[q];
        if (id.containsKey(q)) return false;
        id.put(q, idx++);
        return true;
    }
    public int findCost(int[] x) {
        f = new int[1111111];
        for (int i = 0; i < f.length; i++) {
            f[i] = i;
        }
        for (int r = 2; r * r <= f.length; r++) {
            int num = r * r;
            for (int j = num; j < f.length; j += num) {
                f[j] = f[j/num];
            }
        }
        id = new HashMap<>();
        for (int p : x) {
            int off = 0;
            HashSet seen = new HashSet<>();
            while (seen.size() <= x.length+1) {
                seen.add(get(p+off));
                seen.add(get(p-off));
                off++;
            }
        }
        int nnodes = x.length + id.size() + 2;
        List[] graph = new List[nnodes];
        for (int i = 0; i < nnodes; i++) graph[i] = new ArrayList<>();
        for (int i = 0; i < x.length; i++) {
            int off = 0;
            HashSet seen = new HashSet<>();
            while (seen.size() <= x.length+1) { int n1 = get(x[i]+off); int n2 = get(x[i]-off); if (n1 >= 0) addEdge(graph, i, n1+x.length, 1, off);
                if (n2 >= 0) addEdge(graph, i, n2+x.length, 1, off);
                seen.add(n1); seen.add(n2);
                off++;
            }
        }
        for (int i = 0; i < x.length; i++) addEdge(graph, nnodes-1, i, 1, 0);
        for (int i = 0; i < id.size(); i++) addEdge(graph, i+x.length, nnodes-2, 1, 0);
        return minCostFlow(graph, nnodes-1, nnodes-2, x.length)[1];
    }
    public static void addEdge(List[] graph, int s, int t, int cap, int cost) {
        graph[s].add(new Edge(t, cap, cost, graph[t].size()));
        graph[t].add(new Edge(s, 0, -cost, graph[s].size() - 1));
    }
    public static int[] minCostFlow(List[] graph, int s, int t, int maxf) {
        int n = graph.length;
        int[] prio = new int[n];
        int[] curflow = new int[n];
        int[] prevedge = new int[n];
        int[] prevnode = new int[n];
        int[] pot = new int[n];
        int flow = 0;
        int flowCost = 0;
        while (flow < maxf) {
            PriorityQueue q = new PriorityQueue<>();
            q.add((long) s);
            Arrays.fill(prio, Integer.MAX_VALUE);
            prio[s] = 0;
            boolean[] finished = new boolean[n];
            curflow[s] = Integer.MAX_VALUE;
            while (!finished[t] && !q.isEmpty()) {
                long cur = q.remove();
                int u = (int) (cur & 0xFFFF_FFFFL);
                int priou = (int) (cur >>> 32);
                if (priou != prio[u])
                    continue;
                finished[u] = true;
                for (int i = 0; i < graph[u].size(); i++) { Edge e = graph[u].get(i); if (e.f >= e.cap)
                        continue;
                    int v = e.to;
                    int nprio = prio[u] + e.cost + pot[u] - pot[v];
                    if (prio[v] > nprio) {
                        prio[v] = nprio;
                        q.add(((long) nprio << 32) + v);
                        prevnode[v] = u;
                        prevedge[v] = i;
                        curflow[v] = Math.min(curflow[u], e.cap - e.f);
                    }
                }
            }
            if (prio[t] == Integer.MAX_VALUE)
                break;
            for (int i = 0; i < n; i++)
                if (finished[i])
                    pot[i] += prio[i] - prio[t];
            int df = Math.min(curflow[t], maxf - flow);
            flow += df;
            for (int v = t; v != s; v = prevnode[v]) {
                Edge e = graph[prevnode[v]].get(prevedge[v]);
                e.f += df;
                graph[v].get(e.rev).f -= df;
                flowCost += df * e.cost;
            }
        }
        return new int[]{flow, flowCost};
    }
    public static class Edge {
        public int to, f, cap, cost, rev;
        Edge(int to, int cap, int cost, int rev) {
            this.to = to;
            this.cap = cap;
            this.cost = cost;
            this.rev = rev;
        }
    }
}