Предметный тур. Информатика. 3 этап

В задаче требуется для каждого из \(n\) устройств с начальными зарядами \(a_i\) и целевыми уровнями \(b_i\) определить номер первой из \(m\) операций, после которых заряд этого устройства достигнет или превысит \(b_i\). Каждая операция на отрезке \([l, r]\) добавляет линейно возрастающую последовательность (начальное значение \(x\), приращение \(y\)). Прямое применение каждой операции к каждому элементу отрезка и проверка всех устройств после каждой операции дают время \(\mathcal{O}(mn)\), что при \(n, m\leqslant10^5\) слишком медленно.

Чтобы обойти это, будем обрабатывать операции блоками по размеру \(S\) (например, \(S \approx 450\)). Внутри каждого блока операции накапливаются в разностных массивах с отложенными (ленивыми) обновлениями: один массив аккумулирует константную часть прибавок на отрезке, второй — коэффициент при индексе, а вспомогательный массив устраняет влияние линейного роста за пределами отрезка.

Пример программы-решения

Ниже представлено решение на языке Java.

import java.io.*;
import java.util.*;

public class Main {
    private static final int SZ = 450;

    static int n, m;
    static long[] a, b;
    static int[] ans;
    static long[] sumX, sumY, sub;
    static int[] l, r, x, y, num;
    static int k = 0;

    private static void doLazyUpdate() {
        for (int i = 1; i <= k; i++) {
            sumX[l[i]] += x[i];
            sumX[r[i] + 1] -= x[i];
            sumY[l[i] + 1] += y[i];
            sumY[r[i] + 1] -= y[i];
            sub[r[i] + 1] += 1L * y[i] * (r[i] - l[i]);
        }

        long add = 0;
        for (int i = 1; i <= n; i++) {
            sumX[i] += sumX[i - 1];
            long initialValue = a[i];
            a[i] += sumX[i];

            sumY[i] += sumY[i - 1];
            add += sumY[i] - sub[i];
            a[i] += add;

            if (ans[i] == -1 && a[i] >= b[i]) {
                long value = initialValue;
                for (int j = 1; j <= k; j++) {
                    if (l[j] > i || r[j] < i) continue;
                    value += x[j];
                    value += 1L * y[j] * (i - l[j]);
                    if (value >= b[i]) {
                        ans[i] = num[j];
                        break;
                    }
                }
            }

            sumX[i - 1] = 0;
            sumY[i - 1] = 0;
            sub[i - 1] = 0;
        }

        sumX[n] = 0;
        sumY[n] = 0;
        sub[n] = 0;

        k = 0;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        a = new long[n + 5];
        b = new long[n + 5];
        ans = new int[n + 5];
        sumX = new long[n + 5];
        sumY = new long[n + 5];
        sub = new long[n + 5];

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            b[i] = Long.parseLong(st.nextToken());
            ans[i] = (a[i] >= b[i] ? 0 : -1);
        }

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());

        l = new int[m + 5];
        r = new int[m + 5];
        x = new int[m + 5];
        y = new int[m + 5];
        num = new int[m + 5];

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            l[++k] = Integer.parseInt(st.nextToken());
            r[k] = Integer.parseInt(st.nextToken());
            x[k] = Integer.parseInt(st.nextToken());
            y[k] = Integer.parseInt(st.nextToken());
            num[k] = i;
            if (k == SZ) {
                doLazyUpdate();
            }
        }
        if (k > 0) {
            doLazyUpdate();
        }

        for (int i = 1; i <= n; i++) {
            out.print(ans[i] + (i < n ? " " : "\n"));
        }

        out.flush();
    }
}

В этой задаче необходимо найти площадь объединения двух кругов радиуса \(r\) с центрами в точках \((x_1, y_1)\) и \((x_2, y_2)\). Обозначим квадрат расстояния между центрами через \[d^2 = (x_1 - x_2)^2 + (y_1 - y_2)^2,\] а само расстояние через \(d = \sqrt{d^2}\). Если \(d \geqslant 2r\), круги не пересекаются и ответ равен \(2\pi r^2.\) Если \(d = 0\), круги полностью совпадают и ответ равен \(\pi r^2.\) В остальных случаях площадь пересечения двух одинаковых кругов задается формулой \[A_{\cap} \;=\; 2r^2\arccos\left(\frac{d}{2r}\right)\;-\;\frac{d}{2}\,\sqrt{4r^2 - d^2},\] и искомая площадь объединения равна \[2\pi r^2 \;-\; A_{\cap}.\]

Алгоритм требует лишь константного числа операций (вычисление корня и арккосинуса) и работает за \(\mathcal{O}(1)\) времени, используя \(\mathcal{O}(1)\) памяти.

Пример программы-решения

Ниже представлено решение на языке Java.

import java.io.*;
import java.util.*;

public class light_is implements Runnable {
    private static final String FILENAME = "circleaning";
    
    File inFile = new File(FILENAME + ".in");
    PrintWriter out;
    BufferedReader in;

    private StringTokenizer st;

    light_is() {     
        try {
            in = new BufferedReader(new FileReader(inFile));
            st = new StringTokenizer(in.readLine());
            out = new PrintWriter(new File(FILENAME + ".out"));
        } catch (IOException e) {
            e.printStackTrace();
            System.exit(239);           
        }       
    }
    
    int nextInt() throws IOException {
        if (!st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return Integer.parseInt(st.nextToken());
    }
    
    
    public void run() {
        try {
            int x1 = nextInt();
            int y1 = nextInt();
            int x2 = nextInt();
            int y2 = nextInt();         
            int r = nextInt();            
            int d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
            
            double a;
            if (d > 4 * r * r) {
                a = 0;
            } else if (d == 0) {
                a = Math.PI / 2;
            } else {
                a = Math.acos(0.5 * Math.sqrt(d) / r); 
            }
                        
            out.println(2 * (Math.PI * r * r - 2 * (0.5 * a * r * r - 0.5 * (0.5 * Math.sqrt(d)) * (r * Math.sin(a)))));            
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            out.close();
        }
    }
    
    public static void main(String[] args) {
        new Thread(new light_is()).start();
    }

}

В этой задаче каждый шаблон квадрата размера \(2^h\times2^h\) представляем в виде трех «метрик»: во-первых, число полностью «внутренних» островов пыли, которые не касаются границы шаблона; во-вторых, массив маркировок компонент вдоль периметра (с обходом по часовой стрелке) — каждая граница разбивается на непрерывные отрезки «пыль» или «пусто»; в-третьих, число «открытых» компонент, которые доходят до границы.

При объединении четырех квадрантов в новый шаблон, размер которого вдвое больше, их просто склеивают по периметрам: по внутренним стыкам соседних квадрантов соединяют смежные «пылевые» отрезки (DSU по меткам на границе), одновременно уменьшая число внешних компонентов, которые слились друг с другом, и добавляя к «внутренним» тем, что замкнулись полностью внутри. Таким образом, на каждом шаге сведение четырех шаблонов к новому занимает время, пропорциональное суммарному числу сегментов на их границах.

В итоге главный шаблон Map строится за суммарное время \(\mathcal{O}\bigl(\sum_{\text{шаблоны}} \text{периметр}_i\bigr)\), что при ограничении числа правил до 200 и максимальном размере \(2^{16}\times2^{16}\) остается вполне приемлемо.

Пример программы-решения

Ниже представлено решение на языке Java.

import java.io.*;
import java.util.*;

public class map_as {

    Map<String, Pattern> patterns;

    class DSU {
        int n;
        int[] p;
        int[] r;

        public DSU(int n) {
            this.n = n;
            p = new int[n];
            r = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = i;
            }
        }

        public int get(int x) {
            if (p[x] != x) {
                p[x] = get(p[x]);
            }
            return p[x];
        }

        public void union(int x, int y) {
            x = get(x);
            y = get(y);
            if (r[x] == r[y]) {
                r[x]++;
            }
            if (r[x] > r[y]) {
                p[y] = x;
            } else {
                p[x] = y;
            }
        }
    }

    class Pattern {
        Pattern[] parts;

        int size;
        long inside;
        int ncol;
        int[] col;

        public Pattern(int w) {
            size = 1;
            inside = 0;

            if (w == 0) {
                ncol = 0;
                col = new int[1];
                col[0] = -1;
            } else {
                ncol = 1;
                col = new int[1];
                col[0] = 0;
            }
        }

        public Pattern(Pattern[] parts) {
            this.parts = parts;

            int s = parts[0].size;
            size = s * 2;

            inside = 0;
            for (int i = 0; i < 4; i++) {
                inside += parts[i].inside;
            }

            int r = 4 * s - 4;
            if (r == 0) {
                r = 1;
            }

            int[] ost = new int[]{3 * s - 3, 0, s - 1, 2 * s - 2};
            int[] oen = new int[]{s % r, (2 * s - 1) % r, (3 * s - 2) % r, 1 % r};

            col = new int[4 * size - 4];
            boolean[] existc = new boolean[4 * r];
            int p = 0;
            int q = 0;
            for (int i = 0; i < 4 * size - 4; i++) {
                col[i] = parts[p].col[q];
                if (col[i] != -1) {
                    col[i] += p * r;
                    existc[col[i]] = true;
                }
                q = (q + 1) % r;
                if (q == oen[p]) {
                    p = (p + 1) % 4;
                    q = ost[p];
                }
            }

            DSU comps = new DSU(4 * r);
            for (int i = 0; i < 4 * size - 4; i++) {
                if (i % (size - 1) == s - 1) {
                    if (col[i] != -1 && col[(i + 1) % (4 * size - 4)] != -1) {
                        comps.union(col[i], col[(i + 1) % (4 * size - 4)]);
                    }
                }
            }

            for (int i = 0; i < 4; i++) {
                for (int j = oen[i] % r; j != (oen[i] + (s - 1)) % r; j = (j + 1) % r) {
                    int k = ((j - 2 * (j - (oen[i] - 1)) - (s - 1)) % r + r) % r;
                    int c1 = parts[i].col[j];
                    int c2 = parts[(i + 1) % 4].col[k];
                    if (c1 != -1) {
                        c1 += i * r;
                        existc[c1] = true;
                    }
                    if (c2 != -1) {
                        c2 += ((i + 1) % 4) * r;
                        existc[c2] = true;
                    }
                    if (c1 != -1 && c2 != -1) {
                        comps.union(c1, c2);
                    }
                }
            }

            int[] nc = new int[4 * r];
            Arrays.fill(nc, -1);
            ncol = 0;
            for (int i = 0; i < 4 * size - 4; i++) {
                if (col[i] != -1) {
                    int c = comps.get(col[i]);
                    if (nc[c] == -1) {
                        nc[c] = ncol++;
                    }
                    col[i] = nc[c];
                }
            }

            for (int i = 0; i < 4 * r; i++) {
                if (existc[i]) {
                    int c = comps.get(i);
                    if (nc[c] == -1) {
                        nc[c] = ncol;
                        inside++;
                    }
                }
            }
        }
    }

    public void run() throws IOException {
        Scanner in = new Scanner(new File("space.in"));
        PrintWriter out = new PrintWriter(new File("space.out"));

        patterns = new HashMap<String, Pattern>();

        Pattern one = new Pattern(1);
        patterns.put("1", one);
        Pattern zero = new Pattern(0);
        patterns.put("0", zero);

        while (in.hasNext()) {
            StringTokenizer st = new StringTokenizer(in.next(), "=,");
            String name = st.nextToken();
            Pattern[] pp = new Pattern[4];
            for (int i = 0; i < 4; i++) {
                String p = st.nextToken();
                pp[i] = patterns.get(p);
            }
            Pattern tmp = pp[2]; pp[2] = pp[3]; pp[3] = tmp;
            Pattern pat = new Pattern(pp);
            patterns.put(name, pat);
        }

        Pattern map = patterns.get("Map");
        out.println(map.inside + map.ncol);

        in.close();
        out.close();
    }

    public static void main(String[] arg) throws IOException {
        new map_as().run();
    }
}

В задаче вводится одномерная последовательность затрат \(a_1, \ldots, a_n\) и целый параметр \(k\). Требуется разбить эту последовательность на непрерывные подгруппы так, чтобы суммарная стоимость \[\sum_{\text{группа }[l..r]}\left(\sum_{i=l}^r a_i \;-\;\sum_{\substack{\text{минимальные}\\\lfloor (r-l+1)/k\rfloor\text{ элемента}}}a_j\right)\] была минимальна.

Опишем оптимальное разбиение динамическим программированием по префиксам. Обозначим \[S[i]=\sum_{j=1}^i a_j, \qquad m(i, j)=\min_{\,i\leqslant t\leqslant j}a_t.\] Тогда для \(i < k\) очевидно \(dp[i]=S[i]\), а для \(i\geqslant k\) получаем \[dp[i] =\min\left\{ dp[i-1]+a_i,\; dp[i-k]+\bigl(S[i]-S[i-k]\bigr)-m(i-k+1, i) \right\}.\]

Будем поддерживать на скользящем окне длины \(k\) минимум и префиксные суммы.

Пример программы-решения

Ниже представлено решение на языке Java.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        long[] a = new long[n + 1];
        long[] dp = new long[n + 1];
        long[] mn = new long[n + 1];
        long[] sum = new long[n + 1];
        TreeMap<Long, Integer> s = new TreeMap<>();
        st = new StringTokenizer(reader.readLine());
        for (int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(st.nextToken());
            s.put(a[i], s.getOrDefault(a[i], 0) + 1);
            if (i > k) {
                long x = a[i - k];
                int c = s.get(x);
                if (c == 1) {
                    s.remove(x);
                } else {
                    s.put(x, c - 1);
                }
            }
            if (i >= k) {
                mn[i] = s.firstKey();
            }
        }
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + a[i];
            sum[i] = sum[i - 1] + a[i];
            if (i >= k) {
                long candidate = dp[i - k] + sum[i] - sum[i - k] - mn[i];
                if (candidate < dp[i]) {
                    dp[i] = candidate;
                }
            }
        }
        System.out.println(dp[n]);
    }
}

Задача сводится к подсчету количества ориентированных ациклических графов (DAG) на \(n\) пронумерованных вершинах. Вершины соответствуют пинам, а ориентированное ребро \(u\to v\) моделирует одностороннюю цепочку от \(u\) к \(v\). Условие «сигнал не может вернуться на тот же пин» эквивалентно отсутствию ориентированных циклов. Две микросхемы различны, если существует пара пинов, для которой наличие пути отличается, — значит, нужно посчитать именно число DAG, а не их транзитивных замыканий.

Классическая формула включений–исключений для количества пронумерованных DAG имеет вид \[A_0=1,\qquad A_n=\sum_{k=1}^{n}(-1)^{k-1}\binom{n}{k}\,2^{k(n-k)}\,A_{\,n-k}\quad(n\geqslant1).\] Выбирается \(k\) «ранних» вершин, запрещаются циклы внутри них, а все ребра из этих \(k\) во внешние \(n-k\) вершины задаются произвольно (\(2^{k(n-k)}\) вариантов); знак \((-1)^{k-1}\) появляется из принципа включений-исключений.

Решение данной задачи сводится к эффективной реализации данного рекуррентного соотношения с условиями ограничений по времени и памяти.

Пример программы-решения

Ниже представлено решение на языке Java.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = Integer.parseInt(br.readLine());
        n++;
        final long MOD = 1000000007;
        long[] a = new long[n + 1];
        long[] pow2 = new long[n + 1];
        long[] cpow = new long[n + 1];
        long[][] c = new long[2][n + 1];
        int f = 0;
        int ff = 1;

        pow2[0] = 1;
        a[0] = 1;
        a[1] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (pow2[i - 1] * 2) % MOD;
            cpow[i] = 1;
        }
        c[1][0] = 1;
        c[1][1] = 1;
        cpow[0] = 1;

        for (int i = 2; i < n; i++) {
            c[f][0] = 1;
            for (int j = 1; j < i; j++) {
                c[f][j] = c[ff][j] + c[ff][j - 1];
                if (c[f][j] > MOD) {
                    c[f][j] -= MOD;
                }
                cpow[j] = (cpow[j] * pow2[j]) % MOD;
            }
            c[f][i] = 1;

            for (int k = 1; k <= i; k++) {
                long tmp = a[i - k] * c[f][k] % MOD;
                tmp = tmp * cpow[k] % MOD;
                if ((k & 1) == 1) {
                    a[i] = (a[i] + tmp) % MOD;
                } else {
                    a[i] = (a[i] - tmp + MOD) % MOD;
                }
            }
            f = 1 - f;
            ff = 1 - ff;
        }

        out.println(a[n - 1]);
        out.flush();
    }
}